演算法/距離近似值

在空間和其他搜尋演算法中，以及在計算機遊戲物理引擎中，計算距離很常見。然而，常見的歐幾里德距離需要計算平方根，這在 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