Closest point to another point on a spherical coordinate system

Question

I have a database that I populate with specific locations of my choice. For each location, I will provide a longitude and latitude.

I want to get the geoIP (the longitude and latitude for a given IP matched in a database like maxmind.com) of a visitor to my website. Using the geoIP, I want to find the closest location to the visitor from my locations database table.

I've been spending a lot of time trying to figure out how to accomplish this in an efficient manner; I don't want the process to be expensive for every visitor. The process doesn't have to be precise, just precise enough. If it gives a user Sacramento instead of San Francisco, which would have been more correct, that's okay. Just as long as the degree of error is small enough that it wont bother a majority of users. What wouldn't be okay is if the algorithm gave a location completely off and irrelevant from where they are, say like Chicago (when they live in California).

So with that said, what are some solutions?

Here are some of my ideas:

1

Use the pythagorean theorem to find the distances between two points in a plane. The only problem is that the earth is not on a planar coordinate system, but rather a spherical one. So, I'll need a way to convert geolocation data (long. and lat.) into X and Y coordinates. Then I could run a SQL query that finds the record with the shortest distance which is calculated using: sqrt(abs(locationX - geoIpX)^2 + abs(locationY - geoIpY)^2)

I'm not sure if this is a plausible solution. If it is, then please smooth out the rough edges for me so I can implement it.

2

Figure out an algorithm that uses the differences in longitudes and latitudes. For example, first find the locations that has the closest longitude to the geoIP's longitude, then find the location out of that set that has the closest latitude to the geoIP's latitude. The only issue with the algorithm just described is that the margin of error can potentially be huge. For example, say a city in California is 3 degrees longitude away from the geoIP, but a city in Canada's longitude is 2 degrees away, what will happen is that this longitude line would be used to find the closest latitude, which may be only the city in Canada. Despite the fact that the latitude in Canada is many more degrees further than the latitude in the city in California, the user will be presented with data relevant to a Canadian instead of a Californian, which would be too much of an error. However, maybe there are some modifications to this algorithm that may fix this?

afterword

Thanks for reading. All solutions and help are highly appreciated! :)

Answer 1

You want the Haversine formula. Since that calculation involves trigonometry functions, it tends to be kind of costly.

You might consider copying part of your data to a companion technology that supports built-in geolocation searches. MySQL isn't so good at this type of search, but some other tools are.

For example, Sphinx Search has support for geo distance searches:

• http://sphinxsearch.com/blog/2013/07/02/geo-distances-with-sphinx/

---

MySQL does support spatial indexes, but only in MyISAM tables. There are many reasons to avoid using MyISAM tables.

Answer 2

You can use Haversine formula. http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

For optimizing search you can provide max , min coordinates For max min coords youy can use a server side function to process or you can use stored proceduire to calculate those Example for max min coords :

$minLng = $lng-($distance/(abs(cos(rad2deg($lat))*69)));
$maxLng = $lng+($distance/(abs(cos(rad2deg($lat))*69)));
$minLat = $lat-($distance/69);
$maxLat = $lat+($distance/69);

Mysql +php :

$select = "3956 * 2 * ASIN(SQRT(POWER(SIN((initial.pin_lat - " . $destination.lat . ") * pi()/180 / 2), 2) +COS(" .
        "initial.pin_lat * pi()/180) * COS(" . $destination.lat . " * pi()/180) *POWER(SIN((" .
        "initial.pin_lng - " . $destination.long . ") * pi()/180 / 2),2))) as distance_to_destination";

Then use this distance_to_destination in having clause or use the select in where clause

to narrow down the search

$where =         $destination.long." between "
        . $minLng . " and " . $maxLng . " and ".$destination.lat." between " . $minLat . " and "
        . $maxLat . " having distance < " . $prefered_distance 

Answer 3

mysql is as good as other databases. you can use the spatial index. I have written a php class solving spatial index with a monster curve. You can download my Hilbert curve package at phpclasses. it also uses mercantor projection and I'm using it very successful. other database have native support but you can do it in some hours yourself.