So finden Sie konvexe Hülle in einem dreidimensionalen Raum

Question

Gegeben eine Reihe von Punkten S (x, y, z). Wie finde ich die convex hull dieser Punkte?

Ich habe versucht, den Algorithmus von here zu verstehen, konnte aber nicht viel bekommen.

Dort heißt es:

Erstes Projekt alle Punkte auf der xy-Ebene und eine Kante finden, die auf jeden Fall auf dem Rumpf ist durch den Punkt Auswahl mit höchsten Y-Koordinate und dann eine Iteration zu tun Geschenkverpackung, um den anderen Endpunkt der Kante zu bestimmen. Dies ist der erste Teil des unvollständigen Rumpfes. Wir bauen dann den Rumpf iterativ. Betrachte diese erste Kante. Finde nun einen anderen Punkt, um die erste dreieckige Fläche des Rumpfes zu bilden. Wir tun dies, indem wir den Punkt so auswählen, dass alle anderen Punkte rechts von diesem Dreieck liegen, wenn wir ihn angemessen betrachten (genau wie beim Geschenkumschlag-Algorithmus, bei dem wir eine Kante so gewählt haben, dass alle anderen Punkte rechts davon liegen diese Kante). Jetzt gibt es drei Kanten im Rumpf; Um fortzufahren, wählen wir einen von ihnen willkürlich aus und scannen erneut durch alle Punkte, um einen anderen Punkt zu finden, um ein neues Dreieck mit dieser Kante zu bauen, und wiederholen dies, bis keine Kanten mehr übrig sind. (Wenn wir eine neue dreieckige Fläche erstellen, fügen wir dem Pool zwei Kanten hinzu; wir müssen jedoch zuerst prüfen, ob sie bereits zur Hülle hinzugefügt wurden, in welchem ​​Fall wir sie ignorieren.) Es gibt O (n) Flächen, und jede Iteration benötigt O (n) Zeit, da wir alle verbleibenden Punkte scannen müssen, was O (n2) ergibt.

Kann jemand es klarer erklären oder einen einfacheren alternativen Ansatz vorschlagen.

Answer 1

Ich würde vorschlagen, zuerst versuchen Sie einen einfacheren Ansatz wie schnellen Rumpf. (Btw, die Reihenfolge für die Geschenkverpackung ist O (nh) nicht O (n2), wobei h Punkte auf der Hülle und die Reihenfolge der schnellen Hülle ist O (n log n)).

Unter normalen Umständen funktioniert die schnelle Hülle sehr gut, aber die Verarbeitung wird in der Regel bei hoher Symmetrie oder Punkten, die auf dem Umfang eines Kreises liegen, langsam. Quickhull den folgenden Stufen aufgeschlüsselt werden:

1. Die Punkte mit minimalen und maximalen Koordinaten x, diejenigen gebunden sind Teil der konvex zu sein.

2. Verwenden Sie die durch die beiden Punkte gebildete Linie, um die Menge in zwei Teilmengen von Punkten zu teilen, die rekursiv verarbeitet werden.

3. den Punkt bestimmen, an einer Seite der Linie, mit dem maximalen Abstand von der Linie. Die beiden zuvor gefundenen Punkte bilden zusammen mit diesem ein Dreieck.

4. Die innerhalb dieses Dreiecks liegenden Punkte dürfen nicht Teil der konvexen Hülle sein und können daher in den nächsten Schritten ignoriert werden.

5. Wiederholen Sie die vorherigen zwei Schritte auf den zwei Linien, die durch das Dreieck gebildet werden (nicht die Anfangslinie).

6. Halten Sie sich auf so weiter tun, bis keine mehr Punkte übrig bleiben werden, hat die Rekursion zu Ende zu kommen und die ausgewählten Punkte die konvexe Hülle bilden.

Siehe this impementaion und Erklärung für 3D-konvexe Hülle Quickhull Algorithmus.

Geschenkverpackung Algorithmus:

Jarvis Match-Algorithmus ist wie ein Stück Schnur um die Punkte gewickelt wird. Es beginnt mit der Berechnung des linken Punktes l, da wir wissen, dass der linke Punkt ein konvexer Rumpfknoten sein muss. Dieser Prozess benötigt eine lineare Zeit. Dann führt der Algorithmus eine Reihe von Schwenkschritten durch, um jeden nachfolgenden konvexen Rumpfscheitel bis zum nächsten zu finden Vertex ist der ursprüngliche Punkt ganz links. Der Algorithmus findet den sukzessiven konvexen Rumpfscheitel wie folgt: Der Scheitel, der unmittelbar auf einen Punkt p folgt, ist der Punkt, der am weitesten rechts von jemandem zu sein scheint, der bei p steht und die anderen Punkte betrachtet. Mit anderen Worten, wenn q der Scheitelpunkt ist, der p folgt, und r irgendein anderer Eingabepunkt ist, dann ist das Tripel p, q, r entgegen dem Uhrzeigersinn. Wir können jeden aufeinanderfolgenden Knoten in linearer Zeit finden, indem wir eine Reihe von O (n) Tests im Gegenuhrzeigersinn durchführen.

Da der Algorithmus O (n) Zeit für jeden konvexen Rumpfscheitel ausgibt, ist die Worst-Case-Laufzeit O (n2). Wenn die konvexe Hülle jedoch sehr wenige Ecken hat, ist Jarvis 'Marsch extrem schnell. Eine bessere Möglichkeit, die Laufzeit zu schreiben, ist O (nh), wobei h die Anzahl der konvexen Rumpfscheitelpunkte ist. Im schlimmsten Fall ist h = n, und wir bekommen unsere alte O (n2) Zeit gebunden, aber im besten Fall ist h = 3, und der Algorithmus benötigt nur O (n) Zeit. Dies ist ein so genannter ausgabeempfindlicher Algorithmus, je kleiner die Ausgabe, desto schneller der Algorithmus.

Das folgende Bild sollten Sie mehr Idee geben

Answer 2

die konvexe Hülle 3D-Implementierung ist nicht einfach, aber viele Algorithmen implementiert wurden, und der Code ist weit verbreitet. Am oberen Ende der Qualität und Zeit Investition zu verwenden ist CGAL. Am unteren Ende auf beiden Maßnahmen ist my own C code:
         
Dazwischen gibt es Code alle über das Internet, einschließlich this implementation of QuickHull.

Answer 3

GPL C++ Code für die Suche nach 3D-konvexen Hüllen ist bei http://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gz und eine Beschreibung des O (n log (n)) Algorithmus bei http://www.newtonapples.net/NewtonAppleWrapper.html