查找矩阵中的区域..？

Question

可以说我有一个非常大的矩阵，10000x10000元素的值都是'0'。假设有一些'1'的大巢穴。这些区域甚至可能连接起来，但每周通过'1'的'管道'连接。

我想得到一个算法，很快（如果有必要，脏）发现'1'的这些'嵌套'。在这里它不应该'分开'两个每周连接的'巢'。

任何想法我应该如何做这样的算法？

Answer 1

也许寻路算法像A*（或者更简单的东西像BFS或DFS）在这种情况下可以工作..

您可以：通过查找小巢

• 搜索的起点为您搜索（忽略管道）..所以至少一个1的3×3块
• 那么你应该从那里通过1的路径查找，直到你在矩阵内结束你的“连接组件”（诗意许可证）
• 重复从nother小1的块

Answer 2

我会说这取决于如何数据是需要的。如果给出两点，你需要检查它们是否在1的相同块中，我认为@杰克的答案是最好的。如果你对最初的块有一些了解，也是如此，因为你可以将它们用作算法的起点。

如果你没有任何其他信息，这些也许一会是一种可能性：

如果给一个点，你希望找到在同一组中所有元素，一个flood fill将是适当的。然后，您可以在找到它时缓存每个嵌套，并且当您先获取另一个嵌套时，看看它是否位于已知的嵌套中，并且如果不是执行填充以找到此嵌套，请将其添加到缓存中。

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

如果您可以处理概率效应，请确保您使用具有非常低查找成本的集合实现，如散列表或Bloom filter。

Answer 3

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