arrays - 二维数组邻域算法

Question

我有一个像这样的二维数组：

0,1,0,0,1
1,0,1,0,1
0,1,1,0,1
0,1,0,1,1
1,1,0,0,1

如果我们提取所有 1 的坐标，我们得到：

(height,width)
1,2
1,5
2,1
... 

所以现在我想找到由相邻的 1（不是对角线）创建的区域。为了做到这一点，我需要找到一种方法来检查邻居的邻居。我一直在考虑使用两个数组并将一个邻居的邻居交换到另一个，但这不是一种非常有效的方法，尤其是在处理大数组时。这个问题有更好的解决方案吗？

谢谢

Answer 1

有很多这样的方法，它们被称为连通分量标记。以下是其中一些不太老的（不分先后）：

1. RISC架构的光速标签, 2009
2. 优化两遍连通分量标记算法, 2009
3. 使用轮廓跟踪技术的线性时间组件标记算法，2004

第二种方法在文献中被称为“Wu's algorithm”（它们实际上是指较旧的论文，但那里提出的算法相同），被认为是该任务最快的方法之一。使用洪水填充当然是您想要使用的最后一种方法，因为与其中任何一种方法相比，它都非常慢。该 Wu 算法是一种基于路径压缩的 union-find 数据结构的二次标注，相对容易实现。由于本文涉及 8 连接，因此我将包含用于处理 4 连接的示例代码（您的问题与此有关）。

union-find 结构的代码取自论文中的原样，但您会在您阅读的有关此数据结构的每篇文章中找到类似的代码。

def set_root(e, index, root):
    # Set all nodes to point to a new root.
    while e[index] < index:
        e[index], index = root, e[index]
    e[index] = root

def find_root(e, index):
    # Find the root of the tree from node index.
    root = index
    while e[root] < root:
        root = e[root]
    return root

def union(e, i, j):
    # Combine two trees containing node i and j.
    # Return the root of the union.
    root = find_root(e, i)
    if i != j:
        root_j = find_root(e, j)
        if root > root_j:
            root = root_j
        set_root(e, j, root)
    set_root(e, i, root)
    return root

def flatten_label(e):
    # Flatten the Union-Find tree and relabel the components.
    label = 1
    for i in xrange(1, len(e)):
        if e[i] < i:
            e[i] = e[e[i]]
        else:
            e[i] = label
            label += 1

为简单起见，我假设数组在顶部和左侧填充了零。

def scan(a, width, height): # 4-connected
    l = [[0 for _ in xrange(width)] for _ in xrange(height)]

    p = [0] # Parent array.
    label = 1
    # Assumption: 'a' has been padded with zeroes (bottom and right parts
    # does not require padding).
    for y in xrange(1, height):
        for x in xrange(1, width):
            if a[y][x] == 0:
                continue

            # Decision tree for 4-connectivity.
            if a[y - 1][x]: # b
                if a[y][x - 1]: # d
                    l[y][x] = union(p, l[y - 1][x], l[y][x - 1])
                else:
                    l[y][x] = l[y - 1][x]
            elif a[y][x - 1]: # d
                l[y][x] = l[y][x - 1]
            else:
                # new label
                l[y][x] = label
                p.append(label)
                label += 1

    return l, p

a所以最初你有一个传递给这个函数的数组scan。这是第一次贴标签。要解析标签，您只需调用flatten_label(p). 然后第二个标签传递是微不足道的：

for y in xrange(height):
    for x in xrange(width):
        l[y][x] = p[l[y][x]]

现在您的 4 连接组件已被标记，并max(p)给出了您拥有的组件数量。如果您按照此代码阅读本文，您应该可以轻松理解它。语法来自 Python，如果您对它的含义有任何疑问，请随时提问。

Answer 2

如果我对您的问题的理解是正确的，您可以使用Floodfill来解决问题。