我知道這可能是重複的，但它似乎是'最近的一對點'算法的變體。最近的一對點算法變化
給定一組的在單位正方形Ñ點（X，Y）以及距離d，找到所有一對點，使得它們之間的距離爲至多d。
對於大否蠻力方法不是一個選項。除了「橫掃線」和「分而治之」的方法之外，還有更簡單的解決方案嗎？這些點是無向圖的邊，我需要遍歷它並說出它是否連接（我已經使用DFS，但是當N = 100萬時，它永遠不會結束！）。
歡迎任何僞代碼，意見或想法， 謝謝！
編輯：我發現這對塞奇威克書（我看代碼現在）：
計劃3.18使用鏈表的二維數組通過改善計劃3.7的運行時間當N足夠大時約爲1/d2的因子。它將單位 平方分成一個相同大小的小方格。然後，對於每個正方形，它建立一個所有落入該正方形的點的鏈接列表。二維陣列提供了立即訪問接近給定點的一組點的能力;鏈接列表提供了靈活性來存儲它們可能掉落的點，而不必事先知道每個網格廣場有多少點。
我們確實在尋找位於中心（x，y）和半徑d的圓內的點。
包圍的方形圓是中心（x，y）和邊2d的正方形。這個廣場的任何一點都不需要檢查，它已經結束了。所以，如果abs（xa - x）> d或abs（ya -yb）> d，那麼a（xa，ya）就出來了。
與圍成的正方形相同圓是中心（x，y）和對角線2d的正方形。如果abs（xa-x）<（d * 1.412）或abs（ya -yb）<（xa，ya）中的任意一點不需要檢查， d * 1.412）。
這兩個簡單的規則加起來就減少了很多要檢查的點數。如果我們用x對點進行排序，過濾可能的點，按照它們的y進行排序，我們會找到我們真正需要計算全部距離的點。
對於任何給定的點，您可以使用曼哈頓距離（x-delta加y-delta）啓發式篩選出大多數不在距離「d」內的點 - 過濾掉曼哈頓距離爲大於（sqrt（2）* d），然後對其餘點進行昂貴且精確的距離測試。
如果一個點的座標是[x，y]，則可以消除x座標小於（xd）或x座標大於（x + d）的所有點，以及y座標小於比（yd）或者其y座標大於（y + d）。這應該大大減少您需要執行的兩兩比較的次數。 – 2013-04-05 18:17:41
將點放入桶中。假設您在100x100座標網格中，您將創建大約200個存儲桶：x-座標爲0 <= x <1的點的存儲桶，x-座標爲1 <= x <2的點的存儲桶，另外還有100個桶用於Y座標。現在假設你的d = 5，並且你有一個點[10,20]，你將把x座標桶中的所有點從5到15，並將它們與y座標桶中的點相交15到25. – 2013-04-05 18:30:09
一定要留意角落的情況，你可能會想要從4到16的X桶和從14到26的Y桶只是爲了安全起見。 – 2013-04-05 18:31:10
嗯......它看起來正是我需要的東西。我如何選擇網格大小？謝謝！ – Fernando 2013-04-05 14:50:57