So finden konvexen Hülle in einem 3 dimensionalen Raum
Da eine Reihe von Punkten S (x, y, z)
. Wie finden Sie die convex hull
dieser Punkte ?
Ich habe versucht, das Verständnis des Algorithmus von hierkonnten aber nicht viel.
Er sagt:
Erste Projekt alle Punkte auf der xy-Ebene, und finden Sie eine Kante, die ist definitiv auf dem Rumpf durch die Auswahl der Punkt mit der höchsten y-Koordinate und dann einer iteration von Geschenkpapier, um zu bestimmen, den anderen Endpunkt der Kante. Dies ist der erste Teil der unvollständige Rumpf. Wir bauen den Rumpf iterativ. Betrachten Sie diese erste Kante; jetzt finden ein weiterer Punkt, um die erste dreieckige Fläche des Rumpfes. Wir tun dies durch die Kommissionierung der Punkt, das alle anderen Punkte liegen rechts von diesem Dreieck, als angemessen angesehen (so wie in der gift-wrapping-Algorithmus, in dem wir nahm einen Rand, so dass alle anderen Punkte legen, auf die Rechte Seite, Flanke). Jetzt gibt es drei Kanten im Rumpf; um fortzufahren, wählen wir eine von Ihnen willkürlich, und wieder Scannen durch alle Punkte zu finden, ein weiterer Punkt, zu bauen ein neues Dreieck mit dieser Kante, und wiederholen Sie dies, bis keine Kanten übrig. (Wenn wir es schaffen, ein neues dreieckiges Gesicht, fügen wir die zwei Kanten an den pool, aber wir müssen zunächst prüfen, ob Sie bereits Hinzugefügt, um den Rumpf, in dem Fall, dass wir Sie ignorieren.) Es gibt O(n) Gesichter, und jeder iteration in O(n) Zeit, da müssen wir Scannen alle übrigen Punkte, die Angabe O(n2).
Kann mir jemand erklären in klarer Weise oder schlagen eine einfachere alternative Ansatz.
InformationsquelleAutor der Frage Ninja420 | 2013-08-24
Du musst angemeldet sein, um einen Kommentar abzugeben.
Umsetzung der 3D konvexe Hülle ist nicht einfach, aber viele algorithmen wurden implementiert und der code ist allgemein verfügbar. Im high-end-Qualität und Zeit-Investition zu nutzen, ist CGAL. Am unteren Ende auf beiden Maßnahmen ist meine eigenen C-code:
In zwischen gibt es code alle über das Internet, einschließlich diese implementation von QuickHull.
InformationsquelleAutor der Antwort Joseph O'Rourke
Ich würde vorschlagen, zuerst versuchen, ein einfacher Ansatz wie quick hull. (Btw, den Auftrag für die Geschenkverpackung ist in O(nh) nicht O(n2), wobei h der Punkte auf den Rumpf und die Reihenfolge der schnelle Rumpf ist O(n log n)).
Unter durchschnittlichen Umständen den schnellen Rumpf funktioniert ganz gut, aber die Verarbeitung wird in der Regel langsam in Fällen mit hoher Symmetrie oder Punkte liegen auf dem Umfang eines Kreises. Schnelle Rumpf unterteilt werden können die folgenden Schritte:
Finden Sie die Punkte mit der minimalen und maximalen x-Koordinaten, diese sind
gebunden zu sein, ein Teil der konvex.
Verwenden Sie die Linie, gebildet durch die beiden Punkte teilen den Satz in zwei
Teilmengen der Punkte, die bearbeitet werden rekursiv.
Bestimmen Sie den Punkt, auf der einen Seite der Linie mit der maximalen
Abstand von der Linie. Die beiden Punkte gefunden, bevor Sie zusammen mit diesem
eine form eines Dreiecks.
Die Punkte liegen im inneren des Dreiecks kann nicht Teil der
konvexe Hülle und kann daher ignoriert werden in den nächsten Schritten.
Wiederholen Sie die vorherigen zwei Schritte auf die beiden Linien gebildet, die von der
Dreieck (nicht die erste Zeile).
Tut immer so weiter, bis keine Punkte mehr übrig sind, die Rekursion hat
zu einem Ende kommen und die Punkte ausgewählt, bilden die konvexe Hülle.
Sehen diese impementaion und Erklärung für 3d konvexe Hülle mittels quick-hull-Algorithmus.
Gift-wrapping-Algorithmus:
Jarvis-match-Algorithmus ist wie wickeln Sie ein Stück Schnur um die Punkte. Es beginnt mit der Berechnung der äußerste linke Punkt l, da wir wissen, dass der linke Punkt muss eine konvexe Hülle vertex.Dieser Prozess dauert lineare Zeit.Der Algorithmus hat eine Reihe von drehbar gelagerten Schritte zu finden, jeder der aufeinanderfolgenden konvexen Hülle vertex bis zum nächsten Eckpunkt ist der ursprüngliche Punkt ganz Links wieder.
Den Algorithmus finden, der die aufeinanderfolgenden konvexen Hülle vertex wie folgt: der Eckpunkt sofort nach einem Punkt p ist der Punkt, erscheint die am weitesten rechts zu jemanden, der sich bei p und im Blick auf die anderen Punkte. In anderen Worten, wenn q ist der Scheitelpunkt folgenden p und r ist jede andere Eingabe Punkt, dann die triple p, q, r ist gegen den Uhrzeigersinn. Wir finden jedes der aufeinander folgenden vertex in linearer Zeit durchführen, indem Sie eine Reihe von O(n) gegen den Uhrzeigersinn tests.
Da der Algorithmus verbringt O(n) Zeit für jedes konvexe Hülle vertex, die worst-case-Laufzeit ist O(n2). Allerdings, wenn die konvexe Hülle hat sehr wenige Eckpunkte, Jarvis ' s march ist extrem schnell. Eine bessere Art und Weise zu schreiben, ist die Laufzeit O(nh), wobei h die Anzahl der konvexen Hülle liegen. Im schlimmsten Fall h = n, und wir bekommen unser altes O(n2) Zeit gebunden, sondern im besten Fall h = 3, und der Algorithmus braucht nur O(n) Zeit. Dies ist eine so genannte output-sensitiven Algorithmus, je kleiner die Ausgabe, desto schneller ist der Algorithmus.
Soll das folgende Bild geben Ihnen mehr Ahnung
InformationsquelleAutor der Antwort Aditya
GPL C++ - code für die Suche nach 3D konvexe Hülle ist erhältlich bei http://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gz und eine Beschreibung des O(n log(n)) - Algorithmus unter http://www.newtonapples.net/NewtonAppleWrapper.html
InformationsquelleAutor der Antwort David