Python : remplir un objet creux

Question

J'écris un script pour calculer le volume de n'importe quel objet 3D de forme aléatoire. Je me fiche de savoir si l'objet est creux ou non j'ai besoin de calculer son volume total. Le modèle de données que j'ai est une table 3D (histogramme de pixels) avec des uns et des zéros. les uns sont évidemment là où se trouve l'objet et les zéros là où nous n'avons rien. pour calculer le volume d'un objet bien rempli c'est aussi simple que d'additionner tous les pixels qui contiennent un et de multiplier par le volume du pixel. En revanche, la principale difficulté demeure lorsque nous avons un objet creux, nous avons donc des zéros entourés de uns. Par conséquent, l'application de la méthode simple que j'ai décrite ici n'est plus valable. Ce que nous devons faire, c'est remplir toute la surface de l'objet avec des uns. Voici un exemple en 2D pour que vous puissiez comprendre ce que je veux dire.

une table 2D :

0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 1 0 0 0 
0 0 1 1 0 0 0 1 1 1 0 0 
0 0 0 1 0 0 1 0 0 0 0 0 
0 0 1 0 0 0 0 1 0 0 0 0 
0 0 1 0 0 0 0 1 0 0 0 0 
0 0 1 1 1 1 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 

Je dois le transformer en ceci

0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 1 1 0 0 0 
0 0 1 1 1 1 1 1 1 1 0 0
0 0 0 1 1 1 1 0 0 0 0 0 
0 0 1 1 1 1 1 1 0 0 0 0 
0 0 1 1 1 1 1 1 0 0 0 0 
0 0 1 1 1 1 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0

Answer 1

Si vous utilisez scipy vous pouvez le faire en une seule ligne avec binary_fill_holes . Et cela fonctionne en n-dimensions. Avec votre exemple :

import numpy as np
from scipy import ndimage
shape=np.array([
    [0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,1,1,1,1,1,1,0,0,0],
    [0,0,1,1,0,0,0,1,1,1,0,0],
    [0,0,0,1,0,0,1,0,0,0,0,0],
    [0,0,1,0,0,0,0,1,0,0,0,0],
    [0,0,1,0,0,0,0,1,0,0,0,0],
    [0,0,1,1,1,1,1,1,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0]
    ])
shape[ndimage.binary_fill_holes(shape)] = 1
#Output:
[[0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 1 1 1 1 1 1 0 0 0]
 [0 0 1 1 1 1 1 1 1 1 0 0]
 [0 0 0 1 1 1 1 0 0 0 0 0]
 [0 0 1 1 1 1 1 1 0 0 0 0]
 [0 0 1 1 1 1 1 1 0 0 0 0]
 [0 0 1 1 1 1 1 1 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0]]

Answer 2

Une norme remblai de crue doit être extensible à trois dimensions. De Wikipedia, la version 2-d dans les grandes lignes :

1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return.

Remarquez qu'à l'étape 3, vous gardez la trace de toutes les cellules adjacentes. Si vous changez cela pour trouver toutes les cellules adjacentes en 3-d et que vous exécutez comme précédemment, cela devrait fonctionner correctement.

Answer 3

matrix=[
    [0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,1,1,1,1,1,1,0,0,0],
    [0,0,1,1,0,0,0,1,1,1,0,0],
    [0,0,0,1,0,0,1,0,0,0,0,0],
    [0,0,1,0,0,0,0,1,0,0,0,0],
    [0,0,1,0,0,0,0,1,0,0,0,0],
    [0,0,1,1,1,1,1,1,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0]
    ]

def fill (x,y):
    global matrix
    if ( x==len (matrix)
             or y==len (matrix[0])
             or x==-1
             or y==-1
             or matrix[x][y]==1 ):
            return
    else:
        matrix[x][y]=1
        fill (x+1,y)
        fill (x-1,y)
        fill (x,y+1)
        fill (x,y-1)

fill (4,4)

for i in matrix:
    print i

Answer 4

Pas intuitif et difficile à lire, mais compact :

matrix = [[0, 0, 0, 0, 0, 0],
          [0, 0, 1, 0, 1, 0],
          [0, 1, 0, 0, 0, 1],
          [0, 0, 0, 0, 0, 0]]

ranges = [1 in m and range(m.index(1), len(m)-list(reversed(m)).index(1)) or None for m in matrix]
result = [[ranges[j] is not None and i in ranges[j] and 1 or 0 for i,a in enumerate(m)] for j,m in enumerate(matrix)]

result
[[0, 0, 0, 0, 0, 0],
 [0, 0, 1, 1, 1, 0],
 [0, 1, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 0]]

Answer 5

En supposant que vous parlez de quelque chose comme le remplissage d'un voxel pourquoi ne pouvez-vous pas simplement faire quelque chose comme ceci (prenez-le comme exemple de pseudocode pour le cas simplifié de la 2D, car je ne sais pas quelle structure de données vous utilisez - peut-être une numpy.array ? - Je ne prends donc qu'une hypothétique "liste de listes en tant que matrice" et je ne prends pas en considération le problème de la modification d'un itérable en le parcourant, etc :)

for i, row in enumerate(matrix):
    last_filled_voxel_j = false
    for j, voxel in enumerate(row):
        if voxel:
            if last_filled_voxel != false:
                fill_matrix(matrix, i, last_filled_voxel_j, j)
            last_filled_voxel_j = j

...en supposant que fill_matrix(matrix, row, column_start, column_end) remplit juste la rangée de voxels entre et n'incluant pas column_start y column_end .

Je suppose que ce n'est probablement pas la réponse que vous cherchez, mais pouvez-vous développer ce qui est différent de ce que j'ai pseudo-codé avant que vous ayez réellement besoin de faire afin que nous puissions être plus utiles ?