MySQL Great Circle Distance (Haversine formula)
From Google Code FAQ - Creating a Store Locator with PHP, MySQL & Google Maps:
Here's the SQL statement that will find the closest 20 locations that are within a radius of 25 miles to the 37, -122 coordinate. It calculates the distance based on the latitude/longitude of that row and the target latitude/longitude, and then asks for only rows where the distance value is less than 25, orders the whole query by distance, and limits it to 20 results. To search by kilometers instead of miles, replace 3959 with 6371.
SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) )
* cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin(radians(lat)) ) ) AS distance
FROM markers
HAVING distance < 25
ORDER BY distance
LIMIT 0 , 20;
Join operation in Haversine formula
Any operation you do here which operates on all rows will be slow with that many records.
What you need to do is take advantage of index's. To use an index it must be a simple query and NOT the result of a function (as it is currently).
What you are doing by doing a radius search is making a circle around a point, By using some trig before the circle is made we can come up with the following
where S1 is the largest square inside, and S2 is the smallest square outside.
Now we can work out the dimensions of these two squares and anything OUTSIDE of S2 is hit by and index, and anything INSIDE of S1 is hit by an index, leaving only the small area inside which now needs to be looked up using the slow method.
If you need the distance from the point ignore the S1 sections (as everything inside of the circle needs the haversine function) as a note here, while everything inside of the circle needs it, not every point is within the distance, so both WHERE
clauses are still needed
So lets calculate these points using the unit circle
function getS1S2($latitude, $longitude, $kilometer)
{
$radiusOfEarthKM = 6371;
$latitudeRadians = deg2rad($latitude);
$longitudeRadians = deg2rad($longitude);
$distance = $kilometer / $radiusOfEarthKM;
$deltaLongitude = asin(sin($distance) / cos($latitudeRadians));
$bounds = new \stdClass();
// these are the outer bounds of the circle (S2)
$bounds->minLat = rad2deg($latitudeRadians - $distance);
$bounds->maxLat = rad2deg($latitudeRadians + $distance);
$bounds->minLong = rad2deg($longitudeRadians - $deltaLongitude);
$bounds->maxLong = rad2deg($longitudeRadians + $deltaLongitude);
// and these are the inner bounds (S1)
$bounds->innerMinLat = rad2deg($latitudeRadians + $distance * cos(5 * M_PI_4));
$bounds->innerMaxLat = rad2deg($latitudeRadians + $distance * sin(M_PI_4));
$bounds->innerMinLong = rad2deg($longitudeRadians + $deltaLongitude * sin(5 * M_PI_4));
$bounds->innerMaxLong = rad2deg($longitudeRadians + $deltaLongitude * cos(M_PI_4));
return $bounds;
}
Now your query becomes
SELECT
*
FROM
`places`
HAVING p.nlatitude BETWEEN {$bounds->minLat}
AND {$bounds->maxLat}
AND p.nlongitude BETWEEN {$bounds->minLong}
AND {$bounds->maxLong}
AND (
(
p.nlatitude BETWEEN {$bounds->innerMinLat}
AND {$bounds->innerMaxLat}
AND p.nlongitude BETWEEN {$bounds->innerMinLong}
AND {$bounds->innerMaxLong}
)
OR (
6371 * ACOS(
COS(RADIANS({ $lat })) * COS(RADIANS(`latitude`)) * COS(
RADIANS(`longitude`) - RADIANS({ $lon })
) + SIN(RADIANS({ $lat })) * SIN(RADIANS(`latitude`))
)
)
)) <= {$radius}
ORDER BY distance ASC
IMPORTANT
The above has text for readability, Please ensure these values are escaped correctly / preferably parameterized
This then can take advantage of the index, and allow the join to happen in a faster time
Adding the join this becomes
SELECT
*
FROM
`places` p
INNER JOIN my_friends f ON f.id = p.id
WHERE p.latitude BETWEEN {$bounds->minLat}
AND {$bounds->maxLat}
AND p.longitude BETWEEN {$bounds->minLong}
AND {$bounds->maxLong}
AND (
(
p.latitude BETWEEN {$bounds->innerMinLat}
AND {$bounds->innerMaxLat}
AND p.longitude BETWEEN {$bounds->innerMinLong}
AND {$bounds->innerMaxLong}
)
OR (
6371 * ACOS(
COS(RADIANS({ $lat })) * COS(RADIANS(`latitude`)) * COS(
RADIANS(`longitude`) - RADIANS({ $lon })
) + SIN(RADIANS({ $lat })) * SIN(RADIANS(`latitude`))
)
)
) <= {$radius}
AND f.personal_id = {$personal_id}
ORDER BY distance ASC
IMPORTANT
The above has text for readability, Please ensure these values are escaped correctly / preferably parameterized
Assuming you have the correct indexes this query should remain fast and allow you to do the join.
Looking at the code above im not sure where personal_id
comes from so have left as it is
if you need the distance from the query, you can remove the S1 square
(
p.latitude BETWEEN {$bounds->innerMinLat}
AND {$bounds->innerMaxLat}
AND p.longitude BETWEEN {$bounds->innerMinLong}
AND {$bounds->innerMaxLong}
)
and move the second part of that OR
6371 * ACOS(
COS(RADIANS({ $lat })) * COS(RADIANS(`latitude`)) * COS(
RADIANS(`longitude`) - RADIANS({ $lon })
) + SIN(RADIANS({ $lat })) * SIN(RADIANS(`latitude`))
)
back to the select, which still makes use of S2.
I would also make sure to remove the "magic number" in the query 6371 is the radius of the earth in Kilometer
Haversine formula on a Firebird database
For anyone having a similar issue, here was my solution for Firebird that returns all zips codes within a certain mile radius of a Lat/long (Great Circle) in one query.
select zipcode from(
SELECT zipcode, ( 3959 * acos( cos( 38.6285426/57.2958 ) * cos( lat/57.2958 )
* cos( lon/57.2958 - -86.05296039999999/57.2958 ) + sin( 38.6285426/57.2958 ) * sin(lat/57.2958) ) ) AS distance
FROM zip_codes)
where distance < 20
ORDER BY distance
haversine formula php / mysql
not sure but :
$R = 6371; // radius of Earth in KM
$lat = '46.98025235521883'; // lat of center point
$lon = '-110.390625'; // longitude of center point
$distance = 1000; // radius in KM of the circle drawn
$rad = $distance / $R; // angular radius for query
$query = '';
// rough cut to exclude results that aren't close
$radR = rad2deg($rad/$R);
$max_lat = $lat + radR;
$min_lat = $lat - radR;
$radR = rad2deg($rad/$R/cos(deg2rad($lat)));
$max_lon = $lon + radR;
$min_lon = $lon - radR;
// this part works just fine!
$query .= '(latitude > ' . $min_lat . ' AND latitude < ' . $max_lat . ')';
$query .= ' AND (longitude > ' . $min_lon . ' AND longitude < ' . $max_lon . ')';
// refining query -- this part returns no results
$query .= ' AND acos(sin('.deg2rad($lat).') * sin(radians(latitude)) + cos('.deg2rad($lat).') * cos(radians(latitude)) *
cos(radians(longitude) - ('.deg2rad($lon).'))) <= '.$rad;
Related Topics
Dompdf Not Rendering Images from the Server But Is Rendering from External Source
Php Fatal Error: Uncaught Pdoexception: Could Not Find Driver
How to Set Current Date as Default Value of an Input
I Have Three Columns, I Want to Combine Them All in One Main_Table
Add Space After Every 4Th Character
Laravel: Products,Categories and Subcategories! (Relation Ships)
Remove License Check from Script Code in Codeigniter
How to Throw an Error Message If Username Is Already Registered
How to Get Foreach Loop Variable Outside of Loop
How to Get Next Id of Autogenerated Field in Laravel for Specific Table
Sql Get an Id from a Column Where Ids Separated by Commas
How to Submit Multiple PHP Forms While Each Form Has Its Own Submit Button
Detect a Quotation in a String
How to Remove a Directory That Is Not Empty
How to Change the Background Color of Dropdown List in Select Tag