스택 오버플로를 방지하기 위해 범용 플러드 채우기 알고리즘을 최적화하는 방법은 무엇입니까?

Question

플러드 채우기 알고리즘의 일반적인 구현은 스택 오버플로로 실행됩니다.이를 최적화 할 수있는 방법이 있습니까? 이 알고리즘을 사용하여 건물 모델 내에서 구별되는 보이드 영역을 찾습니다. 그런 다음이 모델을 복셀화하여 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 

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 

출력은 : 당신이 먼저 데이터를 0 & 1을 반대로 할 필요가 있으므로

[[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()는 연결된 모든 초를 찾습니다.