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

Schreibe einen Kommentar