Intro

This is not a battle between flat geometry and spherical geometry to calculate distances between points. This falls somewhere between a rant, my thoughts on the subject, and how we can improve proximity based applications to return relevant results.

Proximity is the state of being accurately close to something. In our case we have an individual trying to find the closest fast-food location while driving (I know you shouldn’t be using your phone when driving, but let’s make an exception). An app uses the individual’s location, its latitude and longitude, to determine the closest burger shack. The nearest five locations are sent back and our individual is on their way to grubbing down.

The biggest problem I have noticed with location based recommendations, is that they fail to take into consideration the distance between two points on a map (arc length) versus the distance between two points while driving (linear). The distance is NOT the same. By simply calculating the two points a map, the distance will tend to be much shorter because there are no streets, directions, or obstacles. While driving there are factors such as speed, traffic, and one-way streets to take into consideration.

Imagine driving on a road with an app’s suggested location on your left hand side over the freeway but the shortest path to this location is to go down the road for 3 miles then another 3 miles back, when the closest location is actually 4 miles down the road.

Flat Geometry

Lets examine this by first calculating the distance between two points while driving. My starting location is in a parking lot at 37.3879242, -121.9821091. To get to the nearest IN-N-Out burger (37.3610039,-122.0248489), I have to drive down a street which takes me out of the way, then get on the freeway, and make a couple more turns. The shortest possible path according to Google Maps is 5.1 miles [1].

Spherical Geometry

Now we compute this using the Haversine Forumla, a commonly used spherical formula in navigation, to find the distance between two points on a sphere. For the sake of brevity, the result is 2.996 miles [2]. The first downfall is the precession of the Earth’s radius; it is rounded to 3961 miles, which is optimized for locations around 39 degrees from the equator (roughly the latitude of Washington DC, USA). A more precise number is difficult to calculate because the Earth is not perfectly spherical, so no single value serves as an exact radius. I think that locations in a radius are most useful when they simply act as a reference, not as a directive.

The Difference

Comparing the two results, the difference between them is huge…at 2.104 miles. And this is only for locations within a radius of 10 miles. The distance between two points in a radius of 50 miles would be increasingly less accurate when driving because the number of required turns would increase. We can think of all these turns as the sum of the two shorter sides of triangles (not hypotenuse). While using spherical geometry is a straight shot because there are no extra deltas (it’s the hypotenuse).

Then again computing the latter is significantly easier and faster than the prior. Tools such as MongoDB’s geospacial queries [3] makes distance calculation easy and flexible but lack one thing, the shortest path. The most optimal solution would be combining spherical geometry with a shortest path algorithm such as Dijkstras [4] to determine to nearest location the with shortest route. While the shortest path is not necessary for all use cases, it matters the most when you are driving to your destination.

Just remember, “Fast is fine, but accuracy is everything.”

[1] http://goo.gl/maps/Vc67E
[2] http://andrew.hedges.name/experiments/haversine/
[3] http://docs.mongodb.org/manual/core/geospatial-indexes/#geospatial-indexes-distance-calculation
[4] http://en.wikipedia.org/wiki/Dijkstra’s_algorithm