確定給定半徑算法內的點

我不確定這是支持我的問題的數學概念。 ^^確定給定半徑算法內的點

假設我們有PointA作爲參考。問題是在給定的半徑範圍內找到PointA周圍的點（使用座標）。我的方法是計算每個點的距離（畢達哥拉斯），然後與給定的半徑進行比較。我敢肯定，這會讓人感到複雜。

你可能會建議什麼算法？一個示例代碼來指出事情將不勝感激。謝謝。

2010-10-15 jeff

你想要一個函數返回距給定座標對小於一定距離的整數座標對嗎？或者你有一組浮動的物體，你想知道哪些是在半徑內？ – 2010-10-15 04:09:38

你可能想看看這個SO回答：http://stackoverflow.com/questions/1318595/which-data-structure-is-appropriate-to-query-all-points-within-distance-d-from-p – 2010-10-15 04:10:25

如果你的積分沒有編入索引，那實際上是一個最佳算法。有個點，並且它將花費O（ n）時間搜索所有它們，在沒有任何其他索引的情況下。

一個微優化是跳過sqrt操作，並將座標變換的平方和與所需半徑的平方進行比較。

如果您打算針對同一數據集進行多個查詢，則可以使用各種需要一些時間才能計算的索引方案（O（n log n）），但要加快查找速度（ O（m + log n），其中m是找到的點數。）

kd-trees可能是從那裏開始的地方。

來源

2010-10-15 04:23:34 Anonymous

我想補充一點，如果您確信座標都小於sqrt（DBL_MAX），那麼您只能跳過sqrt操作，這通常是這種情況。計算歐幾里得距離的數值穩定方式不會溢出，除非產生的距離溢出。 – 2010-10-15 06:29:54

@匿名我知道這是一個古老的問題..但你會如何索引這些點？謝謝。 – RegUser 2015-06-19 14:38:05

我會先在圓圈周圍創建一個盒子，然後首先測試盒子裏是否有東西。那麼你可能總是避免計算sqrt和square。拾取框（說一個在左側）的一個邊緣並計算其x值：

xMin = xOrigin - radius

然後任何satifies

xTest < xMin

可以忽略不計。對所有四面重複類似的事情。測試失敗的那一刻，然後停止在這一點上工作。不要做不必要的計算。

這告訴你一個點很接近但不一定在半徑內。接着計算：

abs(sqr(xOrigin - xTest) - sqr(yOrigin - yTest))

如果小於半徑*半徑（你預先計算，以避免使用平方根），那麼你有半徑範圍內的點。

這是我第一次預先構建數據時可以得出的最好結果。

來源

2010-10-15 04:38:47

這裏唯一的複雜性就是距離的計算。只需篩選並簡化計算，您就是最佳選擇。

如果您的 '中心' 是A（X，Y），則對任意點B（X1，Y1）考慮：

1 /如果B是B點的您的要求的距離d之內，那麼它遵循即x-x1 < d和y-y1 < d。首先檢查這些條件以過濾任何'低掛水果'排除。 2 /不是計算距離，而是計算距離的平方，並將其與最大允許距離的平方（應明顯預先計算和參考，而不是每次重新計算）進行比較。這意味着不必爲每個點計算平方根。

這些都是非常小的優化，但假設點未排序和隨機這是最好的，你會得到。

來源

2010-10-15 04:45:09

最佳答案取決於尺寸的數量。我假設你在二維或三維空間工作。

一個簡單的方法是製作一個單元格大小均勻的網格，比如r。然後將所有點分別存儲到其各自的單元格

每個查詢點只與少數幾個單元相交，比如說9個。然後您只需要檢查相交單元。

更有效的方法是構建四叉樹或KD樹（除2D，四叉樹或KD樹之外，還有很多其他選項）。

檢查圓形矩形交集對於層次結構是必需的，但是這在KD-Tree最近鄰算法中描述（您只需稍微修改它）。

如果您真的關注性能，可以構建多個網格（移位或旋轉），並始終選擇最靠近該點的單元格，以便搜索限於最少的單元格數。

來源

2016-02-13 21:59:38 Libor

確定給定半徑算法內的點

回答

相關問題