我有一个包含 boolean 值的二维矩阵，它更新频率很高。我想在矩阵中选择一个二维索引 {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 就足够了。
最佳答案
如果矩阵一直在更新，那么就不需要建立一些辅助结构，比如距离变换、Voronoy 图等。
您可以像从查询点传播的 BFS(面包优先搜索)一样执行搜索。与通常的 BFS 的唯一区别是欧氏度量。因此，您可以生成按 (u^2+v^2) 排序的 (u, v) 对，并检查按 (+-u,+ -v),(+-v,+-u) 组合(当 u 或 v 为零时四分，否则八分)
关于algorithm - 在二维 boolean 矩阵中找到最接近的 "true"元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40659324/