我正在製作一個簡單的遊戲，並且偶然發現了這個問題。假設2D空間中有幾個點。我想要的是讓點彼此靠近以某種方式相互作用。找到另一點的某個半徑內的所有點
讓我扔的圖片在這裏爲更好地理解這一問題： 
現在，問題不是關於計算距離。我知道該怎麼做。
起初我有大約10分，我可以簡單地檢查每一個組合，但正如你可以假設的那樣，隨着積分數量的增加，這是非常低效的。如果我總共有一百萬分，但所有這些分數彼此之間會很疏遠呢？
我試圖找到一個合適的數據結構或一種方法來看待這個問題，所以每個點只能介意他們的周圍而不是整個空間。有沒有已知的算法？我不完全知道如何命名這個問題，所以我可以谷歌到我想要的。
如果你不知道這種已知的algorighm，所有的想法都非常受歡迎。
你還是得通過每個環節的重複，但有兩個優化，可以執行：
1）您可以通過檢查X1 <半徑，如果消除明顯的要點y1 <半徑（就像布倫特已經在另一個答案中提到的那樣）。
2）不計算距離，您可以計算距離的平方並將其與允許半徑的平方進行比較。這樣可以避免執行昂貴的平方根計算。
這可能是您要獲得的最佳表現。
我認爲我可以通過保持2堆來非常好地利用優化編號1：一個按'x'排序，另一個按'y'協調排序。當分數移動時，heapsort調用應該非常便宜，因爲這些協調只會在每次迭代時略微改變。在玩完這一點之後，我會回來的（沒有電影引用的意圖）。 – Saraph
如果您可以通過x和y值對這些點進行排序，那麼您可以快速選出位於中心點框內的那些點（二進制搜索？）：x + - r，y + - 河一旦你有了這個點的子集，那麼你可以使用距離公式來看它們是否在半徑範圍內。
實際上，這種方法可能有效......但如果這個盒子裏有一百萬分之多呢？您將使用距離公式檢查的點數最小化，但運行時沒有保證範圍或改進 – adao7000
我不認爲有任何方法可以對保存每個點的二維點進行排序靠近鄰居。例如，如果你按x排序然後用y排序，你可能會得到一個類似'[（0,0），（1，999），（2,0）]''的數組。 （我想你可以根據參考點的歐氏距離進行排序，但是隨後你又回到了以O（n）運行時間開始的位置）。因此，您可以將搜索範圍縮小到帶有附近x座標或y座標的點，但不能同時包含這兩個點。 – Kevin
@Kevin你可以有兩個索引，一個用於'x'和一個用於'y'，然後找到兩者的交集（就像SQL中的JOIN子句）。即使有一百萬分，那也只是幾兆字節的存儲空間。 –
這看起來像是一個最近鄰居問題。你應該使用kd樹來存儲點。
空間分割是你想要的.. https://en.wikipedia.org/wiki/Quadtree
這是一個range searching問題。更具體地說 - 二維圓形範圍報告的問題。
從"Solving Query-Retrieval Problems by Compacting Voronoi Diagrams" [Aggarwal, Hansen, Leighton, 1990]報價：
- 輸入：在歐幾里得平面E 2的n個點A組的P
- 查詢：查找包含在E 2盤與P的所有點半徑r以q爲中心。
最好的結果在"Optimal Halfspace Range Reporting in Three Dimensions" [Afshani, Chan, 2009]獲得。他們的方法需要O（n）空間數據結構，它支持O（log n + k）最差情況下的查詢。該結構可以通過在O（n log n）期望時間內運行的隨機算法進行預處理。 （n是輸入點的數量，k是輸出點的數量）。
CGAL庫支持循環範圍搜索查詢。見here。
我不知道如果是最好的主意，但它總比沒有好。將二維空間存儲在此結構中：array（array（bool）），如果有一個點，則爲true;如果沒有，則爲false。因此，當你想在半徑內找到點時，你不必評估整個矩陣，只需評估半徑範圍內的位置 –
https://en.wikipedia.org/wiki/K-d_tree – amit
@pablito。這實際上是我的第一個想法之一。仍然不太喜歡檢查你周圍的每個像素的想法。 – Saraph