计算两点之间地理距离的更快方法 [英] Quicker way to calculate geographic distance between two points

问题描述

我从互联网上的某个地方借用了以下方法(不记得在哪里).但它做了一个直接的过程，找到两个 gps 点之间的距离.它工作得很好，只是它可能有点慢，因为我在数百万个点上运行它.我想知道是否有人知道一种计算成本更低的方法.

I borrowed the following method from somewhere on the internet (Can't remember where). But its doing a straight forward process, finding the distance between two gps points. It works just fine, except that it may be a little slow, as I'm running it across millions of points. I was wondering if anyone knows an approach that would be computationally less expensive.

准确度需要在正确"的一般范围内，但不需要 100% 准确.

The accuracy needs to be in the general area of 'correct' but doesn't need to be 100% 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;
  }
}

P.s 我确实找到了许多其他相关问题，但它们并没有真正关注我的速度问题.

P.s I did indeed find a number of other relevant questions, but they don't really focus on my speed concern.

推荐答案

如果您不介意忽略地球的轻微扁圆度(无论如何您发布的 Haversine 代码就是这样做的)，请考虑预先转换您的所有球面(lat/long) 坐标转换为 3D 单位长度笛卡尔坐标，每个:

If you don't mind ignoring the slight oblateness of the Earth (and your posted Haversine code does just that anyway) consider pre-converting all of your spherical (lat/long) coordinates into 3D unit-length cartesian coordinates first, per:

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

那么笛卡尔坐标 p1 和 p2 之间的球面距离就是:

Then your spherical distance between cartesian coordinates p1 and p2 is simply:

r * acos(p1 . p2)

由于 p1 和 p2 将具有单位长度，因此每对减少到四次乘法、两次加法和一次反三角运算.

Since p1 and p2 will have unit length this reduces to four multiplications, two additions and one inverse trig operation per pair.

另请注意，点积的计算是优化的理想候选者，例如通过 GPU、MMX 扩展、矢量库等.

Also note that the calculation of dot products is an ideal candidate for optimisation, e.g. via GPU, MMX extensions, vector libraries, etc.

此外，如果您的意图是按距离排序对，可能会忽略更远的对，您可以推迟等式中昂贵的 r*acos() 部分通过仅根据点积值对列表进行排序，因为对于所有有效输入(即范围 [-1, 1])，可以保证:

Furthermore, if your intent is to order the pairs by distance, potentially ignoring more distant pairs, you can defer the expensive r*acos() part of the equation by sorting the list just on the dot product value since for all valid inputs (i.e. the range [-1, 1]) it's guaranteed that:

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

然后，您只需获取您真正感兴趣的值的 acos().

You then just take the acos() of the values you're actually interested in.

Re:使用 acos() 的潜在不准确之处，只有当您使用单精度 float 变量时，这些才真正重要.使用具有 16 位有效数字的 double 应该可以使您的距离精确到一米或更小.

Re: the potential inaccuracies with using acos(), those are really only significant if you're using single-precision float variables. Using a double with 16 significant digits should get you distances accurate to within one metre or less.

这篇关于计算两点之间地理距离的更快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！