algorithm - Efficiently filling empty cells in 3D matrix -

algorithm - Efficiently filling empty cells in 3D matrix -

i have 3d "cubical" matrix, cells filled , others empty. closed part enclosed filled cells represents hollow shape. example, matrix have cells filled in such way form surface of hollow sphere. now, want efficient way fill interior of sphere: if cell c0 surrounded in directions filled cells (filled cell in direction need not immediate neighbour of c0), fill c0.

a naive way next :-

for each cell, scan in +x, -x, +y, -y, +z, -z direction, , see if encounter filled cell in each , every direction.

if filled cell encountered in each , every direction, fill cell (as part of interior of shape).

if reach end of grid in 1 direction without encountering filled cell, cell under consideration not interior shape, , should remain unfilled.

the complexity of above approach o(n^4), dimension of 3d grid n*n*n.

an optimization follows :-

if unfilled cell c[x][y][z], encountered 1 filled cell each in 6 directions, not c[x][y][z] needs filled, guaranteed cells scanned (i.e. {in +x direction, cells c[x][y][z], c[x+1][y][z], c[x+2][y][z], ..., till first filled cell}, -x, +y, -y, +z, -z direction) must part of interior of shape, , hence must filled.

another follows :-

if unfilled cell c[x][y][z], not encounter filled cell in, say, +x direction, not c[x][y][z] remain unfilled, guaranteed cells scanned (i.e. in +x direction, cells c[x][y][z], c[x+1][y][z], c[x+2][y][z], ..., till end of grid) must part of exterior , hence, must remain unfilled.

can suggest more efficient approach problem? simple optimizations above, might not cut down order of time complexity, welcome.

you dealing 3d flood fill. see detailed wikipedia article http://en.m.wikipedia.org/wiki/flood_fill

algorithm data-structures matrix