-1

フラッド フィル アルゴリズムの一般的な実装でスタック オーバーフローが発生しました。これを最適化する方法はありますか? このアルゴリズムを使用して、建物モデル内の明確なボイド ゾーンを見つけています。これらのモデルをボクセル化し、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

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 を逆にする必要があります。

于 2012-09-11T01:29:39.093 に答える