How to Efficiently Find the Closest Locations Nearby a Given Location

How to efficiently find the closest locations nearby a given location

Option 1:
Do the calculation on the database by switching to a database that supports GeoIP.

Option 2:
Do the calculation on the database: you're using MySQL, so the following stored procedure should help

CREATE FUNCTION distance (latA double, lonA double, latB double, LonB double)
    RETURNS double DETERMINISTIC
BEGIN
    SET @RlatA = radians(latA);
    SET @RlonA = radians(lonA);
    SET @RlatB = radians(latB);
    SET @RlonB = radians(LonB);
    SET @deltaLat = @RlatA - @RlatB;
    SET @deltaLon = @RlonA - @RlonB;
    SET @d = SIN(@deltaLat/2) * SIN(@deltaLat/2) +
    COS(@RlatA) * COS(@RlatB) * SIN(@deltaLon/2)*SIN(@deltaLon/2);
    RETURN 2 * ASIN(SQRT(@d)) * 6371.01;
END//

EDIT

If you have an index on latitude and longitude in your database, you can reduce the number of calculations that need to be calculated by working out an initial bounding box in PHP ($minLat, $maxLat, $minLong and $maxLong), and limiting the rows to a subset of your entries based on that (WHERE latitude BETWEEN $minLat AND $maxLat AND longitude BETWEEN $minLong AND $maxLong). Then MySQL only needs to execute the distance calculation for that subset of rows.

FURTHER EDIT (as an explanation for the previous edit)

If you're simply using the SQL statement provided by Jonathon (or a stored procedure to calculate the distance) then SQL still has to look through every record in your database, and to calculate the distance for every record in your database before it can decide whether to return that row or discard it.

Because the calculation is relatively slow to execute, it would be better if you could reduce the set of rows that need to be calculated, eliminating rows that will clearly fall outside of the required distance, so that we're only executing the expensive calculation for a smaller number of rows.

If you consider that what you're doing is basically drawing a circle on a map, centred on your initial point, and with a radius of distance; then the formula simply identifies which rows fall within that circle... but it still has to checking every single row.

Using a bounding box is like drawing a square on the map first with the left, right, top and bottom edges at the appropriate distance from our centre point. Our circle will then be drawn within that box, with the Northmost, Eastmost, Southmost and Westmost points on the circle touching the borders of the box. Some rows will fall outside that box, so SQL doesn't even bother trying to calculate the distance for those rows. It only calculates the distance for those rows that fall within the bounding box to see if they fall within the circle as well.

Within PHP, we can use a very simple calculation that works out the minimum and maximum latitude and longitude based on our distance, then set those values in the WHERE clause of your SQL statement. This is effectively our box, and anything that falls outside of that is automatically discarded without any need to actually calculate its distance.

There's a good explanation of this (with PHP code) on the Movable Type website that should be essential reading for anybody planning to do any GeoPositioning work in PHP.

Efficiently finding the closest coordinate pair from a set in Python

Using a k-dimensional tree:

>>> from scipy import spatial
>>> airports = [(10,10),(20,20),(30,30),(40,40)]
>>> tree = spatial.KDTree(airports)
>>> tree.query([(21,21)])
(array([ 1.41421356]), array([1]))

Where 1.41421356 is the distance between the queried point and the nearest neighbour and 1 is the index of the neighbour.

See: http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.query.html#scipy.spatial.KDTree.query

How does Find Nearest Locations work?

A lot of geospatial frameworks will help you out with this. In the geospatial world, a zip code is just a "polygon", which is just an area on a map which defines clear boundaries (not a polygon in the math sense). In SQL 2008 spatial, for example, you can create a new polygon based on your original polygon. So you can dynamically create a polygon that is your zip code extended by a certain distance at every point. It takes the funky shape of the zip code into account. With an address, It’s easy, because you just create a polygon, which is a circle around the one point. You can then do queries give you all points within the new polygon that you created in either method.

A lot of these sites are basically just doing this. They give you all points within a 5 mile extended polygon, and then maybe a 10 mile extended polygon, and so on and so forth. They are not actually calculating distance. Most ma stuff on the web is not sophisticated at all.

You can see some basic examples here to get the general idea of what I'm talking about.

Find the closest locations to a given address

I use the Yahoo Geo Planet API to identify the place corresponding to the search term the user entered. This normally matches multiple places, so you have to present them back to the user to get them to pick the right one. Then, once you know the right place, and it's lat longs, which the Yahoo API provides, you can use the haversine formula to get the closest businesses to the users location. There's a good example in the answer to this question.

Algorithm to calculate nearest location based on longitude & latitude

There is a Distance Matrix API. This API allows you to calculate distances between some given positions.

You can do this also by your own with a haversine formula

How to find nearest location by latitude and longitude?

try this

     SELECT * , (3956 * 2 * ASIN(SQRT( POWER(SIN(( $lat - LatOnTable) *  pi()/180 / 2), 2) +COS( $lat * pi()/180) * COS(LatOnTable * pi()/180) * POWER(SIN(( $long - LongOnTable) * pi()/180 / 2), 2) ))) as distance  
from yourTable  
having  distance <= 10 
order by distance

substitute LatOnTable with the latitude table column name , and longOnTable with you longitude column name in your table .

---

Related Topics