最近空闲单元格的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网格数据结构

回答

相关问题