算法/距离近似值

在空间和其他搜索算法中，以及在计算机游戏物理引擎中，计算距离很常见。然而，常见的欧几里德距离需要计算平方根，这在 CPU 上通常是一个相对繁重的操作。

您不需要平方根来比较距离

给定 (x1, y1) 和 (x2, y2)，哪个点更靠近原点，根据欧几里德距离？您可能会想计算两个欧几里德距离，然后进行比较

d1 = sqrt(x1^2 + y1^2)
d2 = sqrt(x2^2 + y2^2)
return d1 > d2

但这些平方根的计算通常很繁重，而且更重要的是，您根本不需要计算它们。请改为执行以下操作

dd1 = x1^2 + y1^2
dd2 = x2^2 + y2^2
return dd1 > dd2

结果完全相同（因为正平方根是一个严格单调函数）。但是，这只能用于比较距离，而不能用于计算单个值，而有时您需要这样做。因此，我们来看看近似值。

欧几里德距离的近似值

出租车/曼哈顿/L1

在资源非常紧张的情况下，w:出租车距离是最容易计算的一种。

给定两点 (x1, y1) 和 (x2, y2)，

dx=|x1-x2|

(w:绝对值)

dy=|y1-y2|

d=dx+dy

(出租车距离)

请注意，您也可以将其用作“第一遍”，因为它永远不会低于欧几里德距离。您可以检查数据点是否在一个特定的边界框内，作为检查它们是否在您真正感兴趣的边界球内的第一遍。事实上，如果您进一步发展这个想法，您最终会得到一个高效的空间数据结构，例如w:Kd-tree。

但是，请注意，出租车距离不是w:各向同性 - 如果您在一个欧几里德空间中，出租车距离会随着您“网格”的对齐方式而发生很大变化。如果您将其作为欧几里德距离的直接替代品，这会导致很大的差异。八边形距离近似值有助于消除一些有问题的角落，从而获得更好的各向同性

八边形

基于八边形边界的二维距离的快速近似值可以按如下方式计算。

给定两点 $(p_{x},p_{y})$ 和 $(q_{x},q_{y})$ ，设 $dx=|p_{x}-q_{x}|$ (w:绝对值) 和 $dy=|p_{y}-q_{y}|$ 。如果 $dy>dx$ ，近似距离为 $0.41dx+0.941246dy$ 。

几年前，我开发了一种类似的距离近似算法，使用三个项而不是两个项，这比使用两个项更准确，并且由于它使用 2 的幂作为分母，因此系数可以在没有除法硬件的情况下实现。公式是：1007/1024 max(|x|,|y|) + 441/1024 min(|x|,|y|) - if ( max(|x|.|y|)<16min(|x|,|y|), 40/1024 max(|x|,|y|), 0 )。此外，当硬件非常有限时，也可以在不使用乘法或除法的情况下实现距离近似：((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) + ( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 )。这与前面介绍的 2 系数最小最大算法类似，但系数为 123/128 和 51/128。我在 http://web.oroboro.com:90/rafael/docserv.php/index/programming/article/distance 上有一篇文章关于它 - Rafael

(看来那篇文章已经转移到 http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml ?)

(本节的来源)

顶部，章节：1，2，3，4，5，6，7，8，9，A