使用兩個座標之間的距離來處理最有效的方法是什麼？

我有2063個位置存儲在一個MySQL表中。在我的一個過程中，我需要根據距離給定源點有多遠來排除某些結果。問題是，我需要一次篩選幾百個，也許幾千個結果。使用兩個座標之間的距離來處理最有效的方法是什麼？

那麼做距離數學的最好方法是什麼？我應該在運行時間做它

1. Find all points connecting to my point of origin 
2. loops through the connecting points 
3. calculate the distance between the point of origin and the connecting point 
4. exclude the connecting point if the distance if too great

或者我應該創建一個查找表，每個點和每個點之間的距離已經計算出來。我可以避免重複行，因爲p1和p2之間的距離與p2和p1之間的距離相同，但是仍然會導致表中有幾百萬行。

或者..還有更好的方法嗎？

來源

2009-05-26 gargantuan

嘗試靜態查找表...生成的可執行文件的大小應該是有趣的：d〜2063！ * 8個字節（對於每個結果的浮點數） – workmad3 2009-05-26 13:12:48

您可以使用MySQL的空間擴展來計算距離，甚至在數據上創建R-tree索引以優化某個範圍內點的查找。

了MySQL空間擴展的文檔的詳細信息： http://dev.mysql.com/doc/refman/5.1-maria/en/spatial-extensions.html

來源

2009-05-26 13:07:10

如何：

 
1. Loop through all points: 
    2. If abs(a-b) < distance && abs(a-b) < distance then: 
    3. Do the fancy distance calculation between a and b.

即假設大多數點將在您感興趣的距離定義的「框」之外，您可以用步驟2快速篩選出大多數點，並且只計算實際距離以獲得更少的點數。

來源

2009-05-26 13:10:58 Makis

+1假設您的意思是在計算真實距離之前計算dx && dy kenny 2009-05-26 13:15:54

由於您的數據位於mysql表中，因此您確實需要SQL可以幫助您的解決方案。

我會假設每個位置都有一個x和y座標。將它們作爲單獨的條目存儲在表中。

您可以快速縮小您的搜索範圍到一個以您的興趣點爲中心的框。如

WHERE X > (MyPosX - Range) AND X < MyPosX + Range) 
AND Y > (MyPosY - Range) AND Y < MyPosY + Range)

一旦你有一個更小的集合有可能在範圍之內的項目，你可以用一個更迭代的方法

編輯：避免平方根計算的工作出實際距離時雖然這些都很貴。例如，而不是

sqrt(x*x + y*y) < distance

嘗試

(x*x + y*y) < distance*distance  
// distance*distance is a constant and can be calculated once

來源

2009-05-26 13:13:42

使用兩個座標之間的距離來處理最有效的方法是什麼？

回答

相關問題