Flutung eines 3-dimensionalen Polygons

Question

Hier ist ein Problem für Sie ;)

Ich habe ein 3-dimensionales Feld, das mit 1en und 0en gefüllt ist. Die 1en repräsentieren 3-dimensionale komplexe Polygone (keine einfachen Polygone). Nur die Ränder der Polygone haben den Wert 1, das Innere ist mit 0en gefüllt. Hier ist nun das Problem:

Ich brauche einen schnellen Algorithmus, um diese Polygone mit 1en aufzufüllen. Die Arrays haben normalerweise eine Größe von ca. 512x512x100.

Vielen Dank im Voraus!

Hier ist ein Beispiel in 2d:

0000111110000
0000100010000
0000100010000
0000111110000

sollte dazu führen, dass

0000111110000
0000111110000
0000111110000
0000111110000

---

Ist dies die richtige 3-dimensionale Lösung für den @Mikolas-Algorithmus?

    void scan_polygon(int frames, int rows, int cols, char data[][][], char result[][][]){
for(int f=0; f < frames; ++f)
for(int r=0; r<rows; ++r)
for(int s = 0, c=0; c<cols-1; ++c)
{
    s ^= s ? ( data[f][r][c] && !data[f][r][c+1]) :
             (!data[f][r][c] &&  data[f][r][c-1]);

    result[f][r][c] = s;
}

for(int f=0; f < frames; ++f)
for(int c=0; c<cols; ++c)
for(int s = 0, r=0; r<rows-1; ++r)
{
    s ^= s ? ( data[f][r][c] && !data[f][r+1][c]) :
             (!data[f][r][c] &&  data[f][r-1][c]);

    result[f][r][c] &= s;
}

}

Mit freundlichen Grüßen,

stef

Answer 1

Sie können dies in einer einzigen for-Schleife tun, wenn Sie davon ausgehen, dass Ihr Polygon vielfältig ist. Beginnen Sie einfach in der oberen linken Ecke und verfolgen Sie die Parität, wenn Sie eine Kante überqueren.

Eine einfache 2D-Version (mit hinzugefügtem Transpositionsfall):

void scan_polygon(int rows, int cols, char** data, char** result)
{
    for(int r=0; r<rows; ++r)
    for(int s = 0, c=0; c<cols-1; ++c)
    {
        s ^= s ? ( data[r][c] && !data[r][c+1]) :
                 (!data[r][c] &&  data[r][c-1]);

        result[r][c] = s;
    }

    for(int c=0; c<cols; ++c)
    for(int s = 0, r=0; r<rows-1; ++r)
    {
        s ^= s ? ( data[r][c] && !data[r+1][c]) :
                 (!data[r][c] &&  data[r-1][c]);

        result[r][c] &= s;
    }
}

Dies kann zum Beispiel der Fall sein, wenn ein Pixel oder ein Rand entlang einer Scanlinie herausragt:

00000000000000000000        
00000000*11111111111   <--- Whoops!
000000*111*000000000
00000*11111*00000000

Um dies zu beheben, können Sie den Vorgang einfach an einem transponierten Array wiederholen und dann alle Ergebnisse UND-verknüpfen. Ein ähnlicher Ansatz wurde von Sud et al. zur Voxelisierung von Meshes auf der GPU verwendet. Er ist nicht fehlerfrei, da man Konfigurationen mit mehreren nicht-verzweigten Scheitelpunkten haben kann, bei denen sich die verrauschten Kegel von ihnen schneiden, aber wenn man garantieren kann, dass das nicht passiert (oder wenn es nur selten passiert), ist es eine der einfachsten Methoden, die ich kenne, um ein schnelles Ergebnis zu erhalten.

EDIT: Geänderte Lösung, um zu zeigen, wie AND die Arrays wieder zusammen, nachdem Sie die Iteration.

Answer 2

Ich denke, dass in diesem Fall ein Standard-Flutungskonzept angewendet werden könnte:

active_cells = [seed]
while active_cells:
    new_active_cells = []
    for cell in active_cells:
        for nh in neighbor(cell):
            if not filled(nh):
                fill(nh)
                new_active_cells.append(nh)
    active_cells = new_active_cells

Wenn man sich nicht sicher ist, ob das Innere oder das Äußere miteinander verbunden sind (und es daher nicht möglich ist, einen einzigen "Keim" zu finden), kann man alle Zellen durchlaufen und, sobald man eine Zelle mit einer Null findet, den obigen floodfill-Code aufrufen, um die verbundene Komponente zu berechnen. Wiederholt man dies für andere Zellen, die eine Null aufweisen, erhält man am Ende alle zusammenhängenden Regionen, in die die Flächen den Raum aufteilen.

Damit der obige Code funktioniert, ist es natürlich erforderlich, dass die Flächen in Bezug auf die gewählte Konnektivität dicht sind.