A quick way to calculate the geographic distance between two points

Question

I borrowed the following method somewhere on the Internet (I don’t remember where). But he does a straightforward process by finding the distance between two gps points. It works fine, except it can be a little slow as I run it through millions of points. I was wondering if anyone knows an approach that would be less costly.

Accuracy should be “correct” in the general area, but should not be 100% more accurate.

private double distFrom(double lat1, double lng1, double lat2, double lng2) { double earthRadius = 3958.75; double dLat = Math.toRadians(lat2-lat1); double dLng = Math.toRadians(lng2-lng1); double a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * Math.sin(dLng/2) * Math.sin(dLng/2); double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); return earthRadius * c; } } 

Ps I really found a number of other relevant questions, but they really do not focus on my speed.

Answer 1

If you don’t mind ignoring the slight flattening of the Earth (and your hosted Haversine code does this anyway), consider converting all your spherical (lat / long) coordinates to a 3D unit of length of Cartesian coordinates, per:

http://en.wikipedia.org/wiki/Spherical_coordinate_system

Then your spherical distance between the Cartesian coordinates p1 and p2 simple:

 r * acos(p1 . p2) 

Since p1 and p2 will have a unit of length, this will be reduced to four multiplications, two additions and one inverse operation of three pairs.

Also note that point product computation is an ideal candidate for optimization, for example. via GPU, MMX extensions, vector libraries, etc.

In addition, if your intention is to arrange pairs by distance, potentially ignoring more distant pairs, you can defer the expensive part of the r*acos() equation by sorting the list only by the value of the point of sale, since for all valid inputs (i.e. E. range [-1, 1] ), he guaranteed that:

 acos(x) < acos(y) if x > y 

Then you just take acos() values ​​that you are really interested in.

Re: potential inaccuracies using acos() , this is really significant if you use variables with the same float precision. Using a double with 16 significant digits should give you the distance with an accuracy of one meter or less.

Answer 2

That haversine algorithm will provide you with a decent level of accuracy.

If these are really “millions” of points, perhaps implement the cache of calculations you did ... if you run into two coordinates, both of which are close enough to a pair whose distance you have already calculated, then use the cached value?

Or try caching some of the intermediate steps, for example. degree of conversion of radians.

Answer 3

If you sacrifice accuracy, you can make some improvements. As far as I remember, sin(x) approximately equal to x for small x . It also looks like you are calculating the same things several times, for example: Math.sin(dLat/2) (which may actually be close to dLat/2 , as mentioned above).

However, if you do millions of these operations, I would be somewhere else.

• Is your algorithm optimal? Maybe you do too many simple calculations?

• If the points come from the database, can you perform the calculations as stored procedures on the server side of the database?

• If you are looking for the closest points, can you somehow index them?

• Do geospatial indexes help you?

Answer 4

You can try the law of cosines for spherical trigonometry:

 a = sin(lat1) * sin(lat2) b = cos(lat1) * cos(lat2) * cos(lon2 - lon1) c = arccos(a + b) d = R * c 

But it will be inaccurate for short distances (and probably only a little faster).

There is a full discussion here . However, the haversine formula is the most correct way, so there may not be as many that you can do aside from what others have suggested. @ Alnitak's answer may work, but spherical transformations to Cartesian ones are not necessarily fast.