使用網格劃分的2D中的最近鄰居搜索

Question

我在一組中具有相當大的一組2D點（~20000），並且對於x-y平面中的每個點想要確定來自該組的哪一點最接近。 （實際上，這些點是不同類型的，我只想知道哪種類型最接近，而xy平面是位圖，比如說640x480）。

從this answer到問題「All k nearest neighbors in 2D, C++」我的想法是做一個網格。我創建了n * m個C++向量，並將這些點放入向量中，具體取決於它落入哪個bin。這個想法是，你只需要檢查倉內點的距離，而不是所有的點。如果垃圾箱中沒有點，則以螺旋方式繼續相鄰垃圾箱。

不幸的是，我只看過奧利查爾斯沃思的評論算賬：

不只是相鄰的，不幸的是（考慮到在細胞點的兩個 向東可能比點更接近直接在單元格東北部，例如： ;這個問題在更高維度上變得更糟）。 另外，如果相鄰單元碰巧有少於10個點的話呢？在實踐中，你需要「螺旋形」。

幸運的是，我已經有不斷上升的代碼想通了（一個不錯的C++ version here，並有在同一個問題的其他版本）。但我還是留下的問題：

• 如果我發現小區內的打擊，有可能是在相鄰的小區更近的命中（黃色是我的探頭，紅色的是錯誤的選擇，綠色實際的最近點）：

  

• 如果我發現相鄰小區一擊，有可能是在細胞內命中2步之遙，爲奧利查爾斯沃思說：

  

• 但更糟糕的是，如果我在兩步之外的單元格中發現命中，那麼三步之外的命中仍然可能更接近命中！這意味着我不得不考慮所有的細胞與DX，DY = -3 ... 3，或49細胞！

  

現在，在實踐中，這不會經常發生，因爲我可以選擇我的窗口尺寸使細胞充滿足夠。不過，我想得到一個正確的結果，而不是遍歷所有點。

那麼，我該如何找出何時停止「螺旋」或搜索？我聽說有多個重疊網格的方法，但我不太明白。是否有可能挽救這種網格技術？

Answer 1

由於位圖的尺寸不是很大，並且您想要計算的每個(x,y)的最近點，所以可以使用動態編程。

設V[i][j]是從(i,j)到該集合中的最近點的距離，但考慮僅中的一組是在「矩形」的點[（1，1），（I，J）。

然後V[i][j] = 0如果有一個點(i, j)，或V[i][j] = min(V[i'][j'] + dist((i, j), (i', j')))其中(i', j')是(i,j)的三個鄰居之一：

即

• (i - 1, j)
• (i, j - 1)
• (i - 1, j - 1)

這會給你最小的距離，但只限於「左上方」的矩形。我們對「右上」，「左下」和「右下」方向也是這樣，然後取最小值。

複雜性是O（飛機的大小），這是最佳的。

Answer 2

一個解決方案是構建具有不同網格大小的多個分區。

假設你創建的水平1,2,4,8分區，..

現在，搜索網格尺寸1點（你是在9個方格基本搜索）。如果搜索區域中有一個點，並且到該點的距離小於1，則停止。否則，轉到下一個網格大小。

您需要構建的網格數量大約是創建一個分區級別的兩倍。

Answer 3

對於您的任務通常使用Point Quadtree，特別是當點不均勻分佈時。

要保存主內存，您可以使用使用存儲桶的PM或PMR-Quadtree。

您可以在您的細胞中進行搜索，並在最壞的情況下搜索細胞周圍的所有四元組細胞。您可以使用k-d tree。

Answer 4

一個解決方案我嘗試

• 首先做一個網格，這樣你的平均說每盒1（如果你想要更大的掃描更多）點。
• 選擇中心框。以循環方式繼續選擇鄰居框，直到找到至少一個鄰居。此時你可以選擇1或9左右的盒子
• 選擇一層相鄰的盒子
• 現在你有一個相當小的點列表，通常不超過10個，你可以衝入距離公式找到最近的鄰居。

由於每個盒子平均有1個點，所以您將主要選擇9個盒子並比較9個距離。可根據數據集屬性調整網格大小以獲得更好的結果。另外，如果你的數據有很多方差，你可以嘗試2級網格（或者更多），所以如果選擇工作並在單個查詢中返回超過50個點，則開始下一個網格搜索大小的1/10 ...