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

问题描述

我从互联网上的某个地方借用了以下方法（不记得在哪里）。但它做了一个简单的过程，找到两个gps点之间的距离。它工作得很好，只不过它可能有点慢，因为我在数百万个点上运行它。
我想知道是否有人知道一个计算上会更便宜的方法。

准确性需要在'正确'的一般区域，但是' t需要100％准确。

pre $ code> private double distFrom
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））;
返回earthRadius * c;
}
}

我的确发现了一些其他相关问题，但他们并没有真正关注我的速度问题。如果你不介意忽略地球的轻微扁率（和你发布的Haversine代码一样），那么考虑首先将所有球面（经纬/长）坐标预先转换为3D 单位长度笛卡尔坐标：

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

blockquote>

然后，您的笛卡尔坐标 p1 和 p2 之间的球面距离是简单地说：

  r * acos（p1。p2）
   p1 和 p2 将具有单位长度，四个乘法，两个加法和一个反向触发操作。
 
 
另外请注意，点积计算是理想的候选优化，例如通过GPU，MMX扩展，矢量库等。
 
 
另外，如果你的意图是按照距离排列 ，那么可能会忽略更远的距离对，您可以通过对点列产品值进行排序来推迟等式中昂贵的 r * acos（）部分，因为对于所有有效输入（即范围 y 
  

然后您只需 acos（）
$ b

Re：使用 acos（）的潜在不准确性，如果您使用的是单精度 float 变量，那么这些实际上只有重要意义。使用16位有效数字的 double 应该使距离精确到1米以内。

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.

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 I did indeed find a number of other relevant questions, but they don't really focus on my speed concern.

解决方案

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

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

r * acos(p1 . p2)

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

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

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

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

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屋！