实际上,当Sinnott发布
haversine公式时,计算精度受到限制。如今,
JavaScript(以及大多数现代计算机
和语言)使用IEEE 754 64位
浮点数,这些浮点数提供了15个重要的精度数字。以这种精度,余弦公式(cos c = cos a cos b + sin a sin b cos C)的简单
球面定律
给出了良好的条件结果,其结果小至
大约1米。在大多数情况下,使用
更简单的余弦定律或使用更精确的椭圆形Vincenty公式
代替hasrsine可能是值得的! (请注意以下关于球形模型精度的限制
的注意事项。)
来源:http://www.movable-type.co.uk/scripts/latlong.html


为什么更优选余弦定律是什么原因? >

评论

余弦定律如何“优先”?我们可以通过两种方式回答此问题:对于计算机和程序员。对于计算机,haversine公式使用的trig函数较少,但需要两个平方根。为了提高计算效率,这是一个麻烦。对于程序员来说,haversine公式会更长一些。但是,余弦公式定律要求具有ACos实现,这种实现比ATan实现的频率要低一些。此外,要编写防弹代码,您必须检查ACos不会失败。仅仅出于这个原因,我们应该更喜欢haversine。

我刚刚在Python中实现了Haversine和余弦。在这台计算机上,haversine需要3.3μs,而余弦需要2.2μs,如果您需要执行很多操作,这是非常重要的

感谢大家的一些有益的观察和信息。我希望将问题中引用的文本更新为更加客观和有用的内容。

@ChrisV,感谢您的更新!我将其移至评论中,因为它不能直接回答问题,感谢您的出色网站。

#1 楼

该问题由“条件良好”一词表示。这是计算机算术而非数学的问题。
参数x接近0的余弦函数大约等于1-x ^ 2/2。
双精度浮点的精度约为15个十进制数字。

点(2)和(3)表示,当x约为1米或10 ^ -7弧度(点1)时,几乎所有精度都会丢失:1-(10 ^ -7)^ 2 = 1-10 ^ -14是一种计算,其中15个有效数字中的前14个数字全部取消,只剩下一个数字来表示结果。翻转此位置(这就是反余弦“ acos”的作用)意味着无法以任何有意义的精度来计算对应于米长度距离的角度的acos。 (在某些糟糕的情况下,精度损失会给出一个甚至未定义acos的值,因此代码将崩溃并且不给出答案,无意义的答案或使机器崩溃。)类似的考虑因素建议您应避免使用反余弦值如果涉及的距离小于几百米,则取决于您愿意损失多少精度。

acos在幼稚的余弦定律公式中的作用是转换角度远处。在haversine公式中,atan2发挥了这一作用。小角度x的切线近似等于x本身。因此,近似于该数的数的反正切值基本上在精度上没有损失。这就是为什么Haversine公式虽然在数学上等效于余弦公式,但在小距离(大约1米或更短距离)上要优越得多。

这是两个公式的比较在地球上使用100个随机点对(使用Mathematica的双精度计算)。



您可以看到,对于小于约0.5米的距离,这两个公式会发散。在0.5米以上,他们倾向于达成共识。为了显示它们之间的接近程度,下一个图显示了余弦定律的比率:正弦结果对另外100个随机点对的分布,它们的纬度和经度之间的随机差异最大为5米。

这表明,当距离超过5-10米时,余弦公式的法则可以精确到3-4位小数。精度的小数位数增加了两倍;因此,在50-100米(一个数量级)上,您可以获得5-6 dp的精度(两个数量级);在500-1000米处,您会得到7-8 dp等。

评论


是否有一些便宜的测试-例如三角洲纬度> .1 ||经度> 0.1来动态选择余弦(对于大)还是正弦(对于小距离)?为了获得最佳性能和良好的精度。

–已退出-Anony-Mousse
13年3月20日在15:10

@ Anony-Mousse对于世界四分之一的距离,这两个公式都可能相差百分之一的十分之几,所以到那时我们就不会在精度上大惊小怪了!因此,任何能够将近点(几百米)与几乎完全相反的点(约2000万米)之间的所有东西区分开的测试就足够了。

– hu
13年3月20日在15:16

atan2是否比asin更具数字优势?我看到了基准测试,其中atan2比asin慢2-3倍,我们也需要第二个sqrt。

–埃里希·舒伯特(Erich Schubert)
17年4月13日在22:27

@Erich我还没有研究差异,但是请注意,asin与acos本质上是相同的,因此对于某些值(在这种情况下,对于1和-1附近的参数)来说,它们也遭受相同的精度损失。原则上,atan2不存在该问题。

– hu
17年4月13日在22:31

那会是很远的距离吗?然后将其与上面@ Anony-Mousse的建议结合起来似乎很有趣。

–埃里希·舒伯特(Erich Schubert)
17年4月13日在22:55

#2 楼

一个历史脚注:

Haversine是一种避免在
计算中出现较大舍入误差的方法,例如
x小。就hasversine而言,我们有

1 - cos(x)


即使x很小,也可以精确计算2 * sin(x / 2)^ 2。 br />在过去,haversine公式具有
避免加法的另一项优点(这需要进行对数查找,加法,
和对数查找)。据说仅需乘以的三角算术公式为“对数形式”。

如今,使用haversine公式有些不合时宜。
角度x可能用sin(x)cos(x)表示(x
可能没有明确知道)。在那种情况下,通过
haversine公式计算1 - cos(x)需要反正切(获取角度x),减半
(获取x/2),正弦(获取sin(x/2)),平方(获取sin(x/2)^2) )和
最后加倍。使用评估


1 - cos(x) = 2*sin(x/2)^2
           = 2*haversin(x)


更好,因为它不需要三角函数的评估。 (显然,只有在cos(x) > 0时才使用
右侧;否则,可以直接使用
1 - cos(x)。)

#3 楼

余弦公式可以在一行中实现:

  Distance = acos(SIN(lat1)*SIN(lat2)+COS(lat1)*COS(lat2)*COS(lon2-lon1))*6371


Haversine公式有多行: >在数学上,它们是相同的,所以唯一的区别是实用性之一。

评论


虽然原始的Haversine没有使用与计算机相关的atan2公式,但是没有什么可以阻止一个将上面的4行重写为一个公式。

– Arjan
2011年1月8日14:51

@Arjan,是的,但是效率很低,因为您需要计算两次。该公式必须同时包含Sqrt(a)和Sqrt(1-a),这是至关重要的,因为尽管其中一个对于很小或非常大的距离在数值上都是不稳定的,但另一个不会:这就是使此方法起作用的原因。

– hu
2011年1月9日在17:39

的确,@ whuber,但我仍然怀疑行数是否会让我选择另一行。 (就像您已经在回答中解释了您一样,有很多重要的理由支持您。)

– Arjan
2011年1月9日在20:38

@Arjan我同意。一个人的首要任务应该是为编程任务编写足够的代码。之后,我要说清楚:可读性,可维护性和素养的文档。在这种情况下,计算代码行数是没有意义的。

– hu
2011年1月9日在21:16

atan2(sqrt(a),sqrt(1-a))与inin(sqrt(a))相同

–user102008
2011年12月7日在2:11