在距離另一點一定距離的二維網格上查找所有點的算法

我在二維網格（x，y）上有一些點，我需要找到距離該點n距離的所有點。我測量距離的方式是使用兩點之間的距離公式。有人知道怎麼做嗎？在距離另一點一定距離的二維網格上查找所有點的算法

編輯：僅供參考，我正在嘗試做的是編寫一些AI路徑查找，以便在使用基於網格的位置的系統中與目標保持一定的距離。目前，我正在使用A *路徑查找，但我不確定這是否重要或有所作爲，因爲我對此有所瞭解。

來源

2011-12-31 Shenjoku

你要的是範圍或正是距離內的點？ – nycdan 2011-12-31 20:24:56

理想的解決方案是所有的點都精確地或在距離的某個誤差範圍內。 – Shenjoku 2011-12-31 20:26:58

這裏是我會做：

首先篩選出進一步比x或y d的所有點。這些肯定在半徑D的圓外。這是一個非常簡單的計算，它可以快速消除大量的工作。這是一個外部邊界框優化。
您還可以使用內部邊界框優化。如果這些點在x或y上比D * sqrt（2）/ 2更接近，那麼它們肯定在半徑D的圓內。這比計算距離公式還便宜。
然後你有一個候選點的數量較少可能是在半徑D的圓內。對於這些，使用距離公式。請記住，如果d = SQRT（ΔX +ΔY），則d 2 ⁼ΔX +ΔY。
因此，您可以跳過計算平方根的成本。

所以僞代碼，你可以做到以下幾點：

for each point 
begin 
    if test 1 indicates the point is outside the outer bounding box, 
    then skip this point 

    if test 2 indicates the point is inside the inner bounding box, 
    then keep this point 

    if test 3 indicates the point is inside the radius of the circle, 
    then keep this point 
end

來源

2011-12-31 20:24:36

您可以使用空間索引進一步優化算法。如果點數真的很高，這將是真實的。如果點數不是那麼大，那麼構建空間索引的成本可能就不值得。 – 2011-12-31 20:29:18

網格不是很大。我認爲目前世界規劃的規模只會在256x256左右。 – Shenjoku 2011-12-31 20:41:45

好吧，首先我要過濾在距離內都有X和Y距離的點，然後使用內邊界框檢查過濾這些點？不知道如何使用第二部分。 – Shenjoku 2011-12-31 21:55:19

此問題被稱爲範圍查詢。蠻力解決方案與您所描述的一樣：計算所有點距參考點的距離並返回距離小於所需範圍值的距離。

蠻力算法是O（N^2）。但是，有更高效的算法可以使用spatial indexes來降低算法的複雜性和距離計算的次數。例如，您可以使用R-Tree來索引您的要點。

來源

2011-12-31 20:23:40

其所謂的最近鄰搜索。更多在http://en.wikipedia.org/wiki/Nearest_neighbor_search

有開放的圖書館。我用了一個爲C寫的並推薦它：http://www.cs.umd.edu/~mount/ANN/。 ANN表示近似最近鄰，但是，您可以關閉近似值並找到最近的鄰居。

來源

2011-12-31 20:26:34

有趣的東西，但我認爲這對我目前的工作來說太重了。儘管如此，我會在後面記住它。 – Shenjoku 2011-12-31 23:50:05

這不會使用距離公式，但如果您正在尋找距離正好n的點，也許您可以使用sin/cos？

僞代碼：

for degrees in range(360): 
    x = cos(degrees) * n 
    y = sin(degrees) * n 
    print x, y

這將打印每一個點n遠在360倍的增量。

來源

2011-12-31 20:27:42 Michael0x2a

Java實現：

public static Set<Point> findNearbyPoints(Set<Point> pts, Point centerPt, double radius) { 
    Set<Point> nearbyPtsSet = new HashSet<Point>(); 
    double innerBound = radius * (Math.sqrt(2.0)/2.0); 
    double radiusSq = radius * radius; 
    for (Point pt : pts) { 
     double xDist = Math.abs(centerPt.x - pt.x); 
     double yDist = Math.abs(centerPt.y - pt.y); 
     if (xDist > radius || yDist > radius) 
      continue; 
     if (xDist > innerBound || yDist > innerBound) 
      continue; 
     if (distSq(centerPt, pt) < radiusSq) 
      nearbyPtsSet.add(pt); 
    } 
    return nearbyPtsSet; 
}

來源

2012-07-15 20:05:47 zc22

在距離另一點一定距離的二維網格上查找所有點的算法

回答

相關問題