-1

Flood-fill算法的通用实现遇到堆栈溢出，有什么办法可以优化吗？我正在使用此算法在建筑模型中找到不同的空隙区域。我对这些模型进行体素化，然后解析通过简化版本的 0 和 1 表示的体素化结果。0 和 1 表示体素是否存在。0 存在，1 不存在。然后我必须找到连接 0 的不同子集，换句话说，就是 3D 建筑物内的连接空隙空间。

示例 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
4

1 回答 1

1

You can use scipy.ndimage.label to do this quickly:

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

the output is:

[[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() finds all connected 1s, so you need to reverse 0 & 1 for your data first.

于 2012-09-11T01:29:39.093 回答