algorithm - 在二维布尔矩阵中找到最接近的“真实”元素？

Question

我有一个带有布尔值的二维矩阵，它的更新频率很高。我想在矩阵中选择一个二维索引 {x, y}，并在表中找到最近的“真”元素，而不需要遍历所有元素（矩阵很大）。

例如，如果我有矩阵：

0000100
0100000
0000100
0100001

我选择一个坐标{x1, y1}，例如 {4, 3}，我想返回最接近的“真”值的位置，在本例中为 {5, 3}。使用标准毕达哥拉斯方程测量元素之间的距离：

distance = sqrt(distX * distX + distY * distY)哪里distX = x1 - x和distY = y1 - y。

我可以遍历矩阵中的所有元素并保留一个“真实”值列表并选择具有最短距离结果的那个，但它的效率极低。我可以使用什么算法来减少搜索时间？

详细信息：矩阵大小为 1920x1080，每帧大约进行 25 次查询。整个矩阵每帧更新一次。我正在努力保持合理的帧率，超过 7fps 就足够了。

Answer 1

如果矩阵一直在更新，那么就不需要构建一些辅助结构，如距离变换、Voronoy 图等。

您可以像从查询点传播的 BFS（面包优先搜索）一样执行搜索。与通常 BFS 的唯一区别是欧几里得度量。因此，您可以生成(u, v)按顺序排列的对(u^2+v^2)并检查按组合移动的对称点（或为零(+-u,+-v),(+-v,+-u)时为四个点，否则为八个点）uv

Answer 2

您可以使用像四叉树这样的树数据结构（请参阅https://en.wikipedia.org/wiki/Quadtree）来存储值为“true”的所有位置。通过这种方式，应该可以快速迭代给定位置附近的所有“真实”值。此外，如果位置的值发生变化，树可以在对数时间内更新。