The closest GPS coordinate based on distance from a given point

Question

I have a list of GPS locations in a MySQL server database. The user will enter the GPS coordinate in the application, and he should get the nearest GPS coordinate.

I do not mind that the calculation of distances is based on "crow flight" or something else. It must be fast enough to search thousands of GPS locations.

I prefer the solution in C #, otherwise I will try to get the logic and apply myself.

Answer 1

There is one question about searching in MySQL / long distance in Need help in optimizing lat / Lon geoinformation for mysql

To calculate the distance in C #, most sites use the Haversin formula - here is the C # implementation - http://www.storm-consultancy.com/blog/development/code-snippets/the-haversine-formula-in-c-and-sql / - it also has SQL (MS SQL).

/// <summary> /// Returns the distance in miles or kilometers of any two /// latitude / longitude points. /// </summary> /// <param name="pos1">Location 1</param> /// <param name="pos2">Location 2</param> /// <param name="unit">Miles or Kilometers</param> /// <returns>Distance in the requested unit</returns> public double HaversineDistance(LatLng pos1, LatLng pos2, DistanceUnit unit) { double R = (unit == DistanceUnit.Miles) ? 3960 : 6371; var lat = (pos2.Latitude - pos1.Latitude).ToRadians(); var lng = (pos2.Longitude - pos1.Longitude).ToRadians(); var h1 = Math.Sin(lat / 2) * Math.Sin(lat / 2) + Math.Cos(pos1.Latitude.ToRadians()) * Math.Cos(pos2.Latitude.ToRadians()) * Math.Sin(lng / 2) * Math.Sin(lng / 2); var h2 = 2 * Math.Asin(Math.Min(1, Math.Sqrt(h1))); return R * h2; } public enum DistanceUnit { Miles, Kilometers }; 

For most queries ... you are probably well sharing work between C # and SQL

• use MySQL to select "closed" lat / lng points, for example. let's say where lat and lng are within 1.0 of your target.
• then use C # to calculate a more accurate distance and choose the "best."

If you used MS SQL 2008, I would recommend using MS SQL geography types because they have built-in optimized indexing and calculation functions. I see that MySQL also has some extensions - http://dev.mysql.com/tech-resources/articles/4.1/gis-with-mysql.html - but I have no experience with them.

Answer 2

What you are trying to do is called nearest neighbor lookups, and there are many good data structures that can speed up similar searches. For example, you can look in kd-trees, since they can give the expected sublinear time (O (? Radic; n) in two dimensions) queries for a point in the data set closest to some arbitrary test point. They are also surprisingly easy to implement if you prefer writing a modified binary search tree.

Answer 3

Note that when working with spherical geometry, our Euclidean geometry is not entirely accurate (a ^ 2 + b ^ 2 = c ^ 2), but for small subparticles of the earth it can be quite approximate.

Otherwise: http://en.wikipedia.org/wiki/Great-circle_distance

Answer 4

If you have the coordinates of the data stored in the database, you can query the database directly, especially if there is a large amount of data. However, for this you need specific database support (normal indexes do not help). I know that MSSQL supports geographic data , I have not tested MySQL, but the online documentation seems to suggest that there is similar support. Once you create the database with spatial support, you will get results with a simple query.