我有一个 1024x1024 的数组,二进制值 0 或 1,由噪声算法生成。1 总是成群结队。 可视化它,它就像一个由 0 组成的平面和由 1 组成的岛屿。
我想将 1 的每个岛提取到一个新列表中(我碰巧使用的是 C#,但任何容器都可以)。如果一个岛的 3x3 邻域中没有一个与另一个岛重叠,则该岛被认为是独立的。
这听起来像是一个常见问题,但我不知道要搜索的任何候选算法的名称。
我目前正在通过检查每个点及其接触的邻居来进行蛮力操作。
有什么更快的方法吗?
谢谢
最佳答案
Flood-Fill每个“1”得到它所属的“岛”。对所有 1 重复。复杂度与矩阵的大小成线性关系。
一个高效的伪代码可以是:
1. set <- new Set
2. for each cell (i,j) in matrix, if matrix[i][j] == 1:
2.1. set.add(i,j)
3. while set is not empty:
3.1. island <- floodFill(i,j) // start flood fill from i,j
3.2. set.removeAll(island) //remove already found 1's
3.3. yield island
关于arrays - 如何从二维数组中提取聚集数据?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27764957/