如何优化通用泛洪填充算法以防止堆栈溢出

Question

洪水填充算法的通用实现会遇到堆栈溢出，有什么方法可以优化吗？我使用这个算法在建筑模型中找到不同的空隙区域。我对这些模型进行体素化，然后解析通过0和1的简化版本表示的体素化结果。0和1表示体素是否存在。0存在，1不存在。然后，我必须找到连通0的不同子集，换句话说，三维建筑中的连通空隙。

存储在列表中的示例2D输入数据，3D将是列表中的多个条目。（Z，Y，X）=（0，4，9）

11000111
11000000
10001110
10111110

维基百科提出了几种补救措施，但我不知道如何实施。这是现有的算法，我已经为密度更大的数据设置了"sys.setrecursionlimit（10000）"。这对一些人来说很好，但对于密度更大的房间（Z，Y，X）=（50，46，22），因为建筑模型变得更复杂，有数百个房间，我会收到堆栈溢出消息

递归函数中会发生错误堆栈溢出：

File "ZoneFinding3D_Baselined.py", line 104, in findZero
if (0 <= row < row_len) and (0 <= col < col_len) and (0 <= z < height_len) and (col, row, z) not in walked:
MemoryError: Stack overflow

代码：

    def findZero(subset_in, col, row, z, height_len, col_len, row_len, layers3D, walked, output):
    if (0 <= row < row_len) and (0 <= col < col_len) and (0 <= z < height_len) and (col, row, z) not in walked:
        walked.append((col, row, z))
        if layers3D[z][row][col] == 0: #layers3D is in format (z, row, col) which is the actual hierarchy of input data, Z, Y, X
            if subset_in is not None:
                subset = subset_in
            else:
                subset = []
            subset.append((col, row, z))
            findZero(subset, col+1, row, z,  height_len, col_len, row_len, layers3D, walked, output)
            findZero(subset, col, row+1, z,  height_len, col_len, row_len, layers3D, walked, output)
            findZero(subset, col-1, row, z,  height_len, col_len, row_len, layers3D, walked, output)
            findZero(subset, col, row-1, z,  height_len, col_len, row_len, layers3D, walked, output)
            findZero(subset, col, row, z+1,  height_len, col_len, row_len, layers3D, walked, output)
            findZero(subset, col, row, z-1,  height_len, col_len, row_len, layers3D, walked, output)
            if subset_in is None:
                output.append(subset)
def checkThrough(layers3D, gridSizes):
    walked = []
    output = []
    countX=0; countY=0; countZ=0
    for z in range(0, gridSizes[2]):
        for row in range (countY, countY+gridSizes[1]):
            for col in range (0, gridSizes[0]):
                col_len = gridSizes[0]
                row_len = gridSizes[1]
                height_len = gridSizes[2]
                if (col, row, z) not in walked: #walked takes format of (col, row, z), modified from (z, row, col)
                    findZero(None, col, row, z, height_len, col_len, row_len, layers3D, walked, output)
    return output

Answer 1

您可以使用scipy.ndimage.label快速执行此操作：

import numpy as np
from scipy.ndimage import label
a = np.random.randint(0, 2, (4, 6))
b = label(a)
print a
print b

输出为：

[[1 0 1 1 0 0]
 [1 0 0 0 0 0]
 [1 1 0 0 0 1]
 [0 1 1 0 1 1]]
(array([[1, 0, 2, 2, 0, 0],
       [1, 0, 0, 0, 0, 0],
       [1, 1, 0, 0, 0, 3],
       [0, 1, 1, 0, 3, 3]]), 3)

label()查找所有连接的1，因此需要反转0&1首先用于您的数据。