matrix - 在矩阵中查找区域..？

Question

假设我有一个非常大的矩阵，其中包含 10000x10000 个元素，所有元素的值都为“0”。可以说有一些“1”的大“巢”。这些区域甚至可能被连接起来，但每周都会被一个“1”的“管道”连接起来。

我想得到一个算法，它很快（如果必要的话很脏）找到这些“1”的“巢”。在这里，它不应该“分割”两个每周连接的“巢穴”。

知道我应该如何做这样的算法吗？

Answer 1

在这种情况下，也许像A*这样的寻路算法（或者像 BFS 或 DFS 这样更简单的算法）可能会起作用。

你可以：

• 通过查找小巢（忽略管道）来搜索搜索的起点。所以至少有一个 3x3 的 1 块
• 那么你应该从那里通过 1 进行寻路，直到你在矩阵内结束你的“连接组件”（诗意许可证）
• 从另一个小 1 的块开始重复

Answer 2

1. 将矩阵变成黑白位图
2. 缩放矩阵，使大小为 N 的嵌套变为单个像素（因此，如果您寻找 10x10 的嵌套，则缩放 N=10 倍）。
3. 使用输出的剩余像素来定位巢。使用中心坐标（乘以上面的因子）在矩阵中定位相同的嵌套。
4. 使用低通滤波器去除所有连接巢穴的“管道”。
5. 使用位图上的对比度过滤器找到嵌套的边界。
6. 创建一个不包含嵌套的位图（即，将嵌套的所有像素设置为 0）。
7. 使用扩大单个像素的过滤器来扩大巢的轮廓。
8. 按位AND输出 7 和 5 以获得所有管道的连接点。
9. 按照管道查看它们如何连接巢穴

Answer 3

我会说这取决于如何需要数据。如果给定两点，您需要检查它们是否在同一块 1 中，我认为@Jack 的答案是最好的。如果您对块的初始位置有所了解，这也是正确的，因为您可以将它们用作算法的起点。

如果您没有任何其他信息，也许其中之一是可能的：

如果给定一个点，您希望找到同一块中的所有元素，则适合使用泛洪填充。然后你可以缓存你找到的每个巢，当你得到另一个点时，首先看看它是否在一个已知的巢中，如果它没有做一个洪水填充来找到这个巢，然后将它添加到缓存中。

作为一个实现细节，当您遍历矩阵时，每一行都应该有前一行上存在的嵌套集。然后，您只需要针对这些嵌套而不是完整集合检查新点，以确定新点是否在已知集合中。

如果可以处理概率效应，请确保使用查找成本非常低的集合实现，例如哈希表或可能的 Bloom 过滤器。