二维阵列邻接算法

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"(他们实际上指的是一篇更早的论文，但那里提出的算法是相同的)，并且被认为是该任务最快的方法之一。使用洪水填充当然是你最不想使用的方法之一，因为与这些方法相比，它非常缓慢。该算法是一种基于并查找数据结构和路径压缩的两遍标记算法，相对容易实现。由于本文涉及8连通性，因此我包含了处理4连通性的示例代码(您的问题是关于4连通性的)。

并查找结构的代码取自论文，但您将在阅读的关于该数据结构的几乎所有文本中找到类似的代码。

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

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

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

如果我对你问题的理解是正确的，你可以使用填充物来解决这个问题。