在 2D 布尔矩阵中找到最近的 "true" 元素？
Find closest "true" element in 2D boolean matrix?
我有一个包含布尔值的二维矩阵，它的更新频率很高。我想在矩阵中选择一个二维索引 {x, y}，并在 table 中找到最近的元素 "true"，而无需遍历所有元素（矩阵很大）。
例如，如果我有矩阵：
0000100
0100000
0000100
0100001
并且我选择一个坐标 {x1, y1} 例如 {4, 3}，我想返回最近的 "true" 值的位置，在本例中是 {5, 3}。元素之间的距离使用标准毕达哥拉斯方程测量：
distance = sqrt(distX * distX + distY * distY) 其中 distX = x1 - x 和 distY = y1 - y.
我可以遍历矩阵中的所有元素并保留 "true" 值和 select 具有最短距离结果的列表，但效率极低。我可以使用什么算法来减少搜索时间？
详情： 矩阵大小为1920x1080，每帧大约进行25次查询。整个矩阵每帧更新一次。我试图保持合理的帧率，超过 7fps 就足够了。
如果矩阵一直在更新，那么就不需要建立一些辅助结构，比如距离变换，Voronoy图等
您可以像从查询点传播的 BFS（面包优先搜索）一样执行搜索。与通常的 BFS 的唯一区别是欧氏度量。因此，您可以生成按 (u^2+v^2) 排序的 (u, v) 对，并检查按 (+-u,+-v),(+-v,+-u) 组合移动的对称点（当 u 或 v 为零时为四点，否则为八点)
您可以使用像四叉树这样的树数据结构（参见 https://en.wikipedia.org/wiki/Quadtree）来存储值为 "true" 的所有位置。通过这种方式，应该可以快速迭代给定位置附近的所有 "true" 值。此外，如果位置的值发生变化，树可以以对数时间更新。
我有一个包含布尔值的二维矩阵，它的更新频率很高。我想在矩阵中选择一个二维索引 {x, y}，并在 table 中找到最近的元素 "true"，而无需遍历所有元素（矩阵很大）。
例如，如果我有矩阵：
0000100
0100000
0000100
0100001
并且我选择一个坐标 {x1, y1} 例如 {4, 3}，我想返回最近的 "true" 值的位置，在本例中是 {5, 3}。元素之间的距离使用标准毕达哥拉斯方程测量：
distance = sqrt(distX * distX + distY * distY) 其中 distX = x1 - x 和 distY = y1 - y.
我可以遍历矩阵中的所有元素并保留 "true" 值和 select 具有最短距离结果的列表，但效率极低。我可以使用什么算法来减少搜索时间？
详情： 矩阵大小为1920x1080，每帧大约进行25次查询。整个矩阵每帧更新一次。我试图保持合理的帧率，超过 7fps 就足够了。
如果矩阵一直在更新，那么就不需要建立一些辅助结构，比如距离变换，Voronoy图等
您可以像从查询点传播的 BFS（面包优先搜索）一样执行搜索。与通常的 BFS 的唯一区别是欧氏度量。因此，您可以生成按 (u^2+v^2) 排序的 (u, v) 对，并检查按 (+-u,+-v),(+-v,+-u) 组合移动的对称点（当 u 或 v 为零时为四点，否则为八点)
您可以使用像四叉树这样的树数据结构（参见 https://en.wikipedia.org/wiki/Quadtree）来存储值为 "true" 的所有位置。通过这种方式，应该可以快速迭代给定位置附近的所有 "true" 值。此外，如果位置的值发生变化，树可以以对数时间更新。