最近空閒單元格的2D網格數據結構

考慮一個2000 x 2000 2D布爾數組。將100,000個元素設置爲true，其餘爲false。給定一個單元格（x1，y1），我們需要找到最接近的單元格（x2，y2）（曼哈頓距離：abs（x1-x2）+ abs（y1-y2）），這是錯誤的。要做到這一點最近空閒單元格的2D網格數據結構

一種方法是：

for (int dist = 0; true; dist++) 
    for ((x2,y2) in all cells dist away from (x1,y1)) 
     if (!array[x2,y2]) 
      return (x2,y2);

在最壞的情況下，我們必須找到一個免費通過前100,000個細胞進行迭代。

是否有我們可以使用的數據結構，而不是使用我們可以更快地執行此搜索的2D數組？

來源

2012-06-26 Andrew Tomazos

數組是否會被更新？你會做很多搜索嗎？ –

數組是否爲常量，並且您有很多疑問？或者它是每個數組問題的一個查詢？如果只打算使用一次，那麼創建聰明的數據結構確實沒有意義。 – amit

對不起，是的，數據會發生變化 - 一旦找到一個單元格，它就會被標記爲真。 –

如果數據是恆定的，並且您有許多查詢：
您可能想要使用k-d tree，並查找最近的鄰居。爲每個元素插入(i,j)，例如arr[i][j] = false。標準kd樹採用歐氏距離，但我認爲一個可以修改它使用曼哈頓距離而不是..

如果數據被用於一個查詢：
您將需要至少Omega(n*m) OPS讀取數據和將它插入到任何數據結構中 - 因此毫無意義 - 建議的解決方案將僅勝過任何數據結構的構建。

來源

2012-06-26 08:39:35 amit

由於[三角不等式]（http://en.wikipedia.org/wiki），典型的kd-tree算法適用於任何[度量]（http://en.wikipedia.org/wiki/Metric_%28mathematics%29）/Triangle_inequality）。 – salva

您可能會想要查看Region QuadTree。這裏最初整個圖像被建模爲根，因爲圖像包含全部0（假設）。然後，當設置特定像素時，首先將圖像分成4個象限，將不包括像素的3個象限留作葉子。剩下的象限再次細分等等。這是達到，直到我們有4個點離開其中一個設置。這種表示將有助於在搜索過程中排除整個區域，搜索時間可以優化爲O（log n）

來源

2012-06-26 13:04:48 PermanentGuest

最近空閒單元格的2D網格數據結構

回答

相關問題