Effizientes Auffüllen leerer Zellen in 3D-Matrix

Question

Ich habe eine "würfelförmige" 3D-Matrix, in der einige Zellen gefüllt und andere leer sind. Ein geschlossenes von gefüllten Zellen umschlossenes Gebiet repräsentiert eine hohle Form. Zum Beispiel könnten die Zellen in der Matrix so gefüllt sein, dass sie gemeinsam die Oberfläche einer hohlen Kugel bilden. Jetzt möchte ich eine effiziente Möglichkeit finden, um das Innere dieser Kugel zu füllen: Wenn eine Zelle C0 in alle Richtungen von gefüllten Zellen umgeben ist (die gefüllte Zelle in dieser Richtung muss kein unmittelbarer Nachbar von C0 sein), dann fülle C0.

Ein naiver Weg wäre der folgende :-

Für jede Zelle scannen Sie in die Richtungen +X, -X, +Y, -Y, +Z, -Z und prüfen, ob Sie in jede Richtung auf eine gefüllte Zelle treffen.

Wenn in jede Richtung eine gefüllte Zelle erreicht wird, dann füllen Sie diese Zelle (da sie Teil des Inneren einer Form ist).

Wenn Sie das Ende des Rasters auch nur in einer Richtung erreichen, ohne auf eine gefüllte Zelle zu treffen, bleibt die betrachtete Zelle nicht im Inneren einer Form, und sollte unfilled bleiben.

Die Komplexität des obigen Ansatzes beträgt O(n^4), wobei die Dimension des 3D-Gitters n*n*n ist.

Eine Optimierung könnte wie folgt sein :-

Wenn für eine unfilled-Zelle C[x][y][z], wir auf jede Richtung eine gefüllte Zelle treffen, dann muss nicht nur C[x][y][z] gefüllt werden, es ist auch garantiert, dass alle Zellen, die wir gerade gescannt haben (d.h. {in +X-Richtung, alle Zellen C[x][y][z], C[x+1][y][z], C[x+2][y][z], ..., bis zur ersten gefüllten Zelle}, ähnlich für -X, +Y, -Y, +Z, -Z-Richtung) Teil des Inneren einer Form sein müssen und daher gefüllt werden müssen.

Ein weiterer Ansatz könnte wie folgt sein :-

Wenn für eine unfilled-Zelle C[x][y][z] in, sagen wir, +X-Richtung keine gefüllte Zelle erreicht wird, wird nicht nur C[x][y][z] unfilled bleiben, es ist auch garantiert, dass alle Zellen, die wir gerade gescannt haben (d.h. in +X-Richtung, alle Zellen C[x][y][z], C[x+1][y][z], C[x+2][y][z], ..., bis zum Ende des Gitters) Teil des Äußeren sein müssen und daher unfilled bleiben müssen.

Kann jemand einen effizienteren Ansatz für dieses Problem vorschlagen? Selbst einfache Optimierungen wie oben, die die Ordnung der Zeitkomplexität nicht reduzieren, sind willkommen.

Answer 1

Du beschäftigst dich mit 3D Flood Fill. Siehe detaillierten Wikipedia-Artikel http://en.m.wikipedia.org/wiki/Flood_fill

Answer 2

Ok, da dies eine geschlossene hohle Form ist, können wir einfach eine BFS oder DFS verwenden, um das Problem zu lösen.

BFS:

Beginnend mit einer leeren Warteschlange füge zur Warteschlange jede Zelle hinzu, die innerhalb der hohlen Form liegt. Vom Anfang der Warteschlange aus wird eine Zelle entnommen, diese Zelle wird gefüllt und dann werden die 6 benachbarten Zellen überprüft. Wenn diese Nachbarzelle nicht gefüllt ist, wird sie zur Warteschlange hinzugefügt, ansonsten wird sie ignoriert. Dieser Prozess wird fortgesetzt, bis die Warteschlange leer ist.

Das übrige Problem besteht darin, eine Zelle innerhalb der hohlen Form zu finden. Ein Trick besteht darin, die Zelle im Eckpunkt der Form zu finden, die mindestens drei gefüllte Nachbarn hat.

Die Zeitkomplexität beträgt O(Anzahl der zu füllenden Zellen * 6 Richtungen, die überprüft werden müssen).

Tipp zur Bewegung in 6 Richtungen:

int[] x = {0,0,0,0,1,-1};
int[] y = {0,0,1,-1,0,0};
int[] z = {1,-1,0,0,0,0};

Point p = // Punkt im Raum mit drei Dimensionen x, y, z

for(int i = 0; i < 6; i++){
     int a = p.x + x[i];
     int b = p.y + y[i];
     int c = p.z + z[i];
}

Answer 3

Für jede Zelle scannen Sie in Richtung +X, -X, +Y, -Y, +Z, -Z und prüfen, ob Sie in jeder Richtung auf eine gefüllte Zelle stoßen.

Wenn in jeder Richtung eine gefüllte Zelle erreicht wird, füllen Sie diese Zelle (da sie Teil des Inneren einer Form ist).

Die obige Aussage ist falsch, es sei denn, Sie beschäftigen sich nur mit konvexen Hüllen. Das folgende Bild zeigt, dass der betreffende Punkt nicht in der blauen Form eingeschlossen ist, aber dennoch in allen (x, y, z) Richtungen schneiden wird.

Um den allgemeinen Fall des Auffindens von ausgehöhlten Formen zu behandeln, können Sie alle Zellen zu einem Set hinzufügen. Beginnen Sie dann an einer Randzelle. Die Zelle am Rand gehört zu einer ausgehöhlten Form, wenn sie gefüllt ist, ansonsten gehört sie zu einer Hintergrundform (nicht gefüllt).

Dann, ähnlich wie in der Antwort von @Pham Trung, können Sie in alle Richtungen nach außen traversieren, bis Sie alle Zellen durchlaufen haben, die sich innerhalb der Form befinden, wobei die farbigen Zellen an den Grenzen ignoriert werden. Wählen Sie eine andere Zelle an der Grenze der vorherigen Form und starten Sie den Vorgang erneut, bis alle Zellen durchlaufen sind.

Am Ende werden alle Zellen entweder als Teil einer ausgehöhlten Form oder des Hintergrunds gekennzeichnet sein.

Answer 4

Nur für die Vollständigkeit, noch zwei weitere. Je nach vielen Faktoren kann sich das Ergebnis unterschieden.

1. Finde die Oberfläche

Wenn Sie es mit einer großen Anzahl von Voxeln zu tun haben, wäre eine Optimierungsmöglichkeit, die Grenzfläche des Hohlraums zu finden. Dies kann wie in der Antwort von Pham Trung geschehen, indem nur Zellen akzeptiert werden, die mindestens einen ihrer 6 Nachbarn gefüllt haben.

Nachdem die Grenzfläche bestimmt wurde, kann sie zeilenweise mit 1D-Füllungen gefüllt werden, da die Richtungen "innen" und "außen" bekannt sind.

Diese Methode hält die Größe des Satzes viel kleiner, wenn Sie eine große Anzahl von Voxeln haben (wächst mit n^2 anstelle von n^3). Das Suchen von Sets ist normalerweise sehr schnell, aber wenn das Set nicht in den RAM passt, verlangsamen sie sich erheblich.

2. Auf 2D schneiden

Eine weitere Möglichkeit wäre, die Form in 2D-Scheiben zu schneiden und die resultierenden Hohlräume schichtweise zu verbinden. Dann müssen immer nur zwei Scheiben gleichzeitig im Speicher gehalten werden.

Die grundlegende Idee besteht darin, jeder separaten verbundenen 2D-Region einen eigenen Bezeichner zuzuweisen und dann ihre Verbindungen zu den bereits bekannten Regionen in der benachbarten Schicht zu finden. Nachdem alle Schichten bearbeitet wurden, bleiben verbundene 3D-Regionen zurück.

Die Herausforderung besteht darin, den besten Algorithmus zu finden, um die 2D-Regionen in benachbarten Schichten zu verbinden. Es scheint, dass diese Methode mit einfachen Formen (wenige getrennte Regionen in den 2D-Scheiben) schnell ist, aber mit komplexen Formen ("Wurmlöcher im Baum") langsam ist. Außerdem wird ein schneller Algorithmus benötigt, um einen einzelnen gemeinsamen Punkt in zwei Sets zu finden. (D.h. es ist keine vollständige Satzüberschneidung erforderlich, nur die Information, ob die Sätze mindestens einen gemeinsamen Punkt haben oder nicht.)

Wenn Ihre Sets wieder vernünftiger Größe sind, ist der triviale Algorithmus, den Pham Trung beschrieben hat, wahrscheinlich die beste Wahl.