2D konvexe Hülle auf einer 3D Ebene

icewater

Moin,

ich habe eine Punktwolke im R^3, dessen Punkte alle auf einer Ebene liegen.
Nun möchte ich die konvexe Hülle dieser Punkte bestimmen.

Ich habe bereits einen Algo nach Andrew im 2D implementiert (C++).
http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
Allerdings funktioniert der Algorithmus natürlich nicht im 3D.

Ich habe jetzt zwei Möglichkeiten. Entweder ich bekomme den Algo so manipuliert, dass er auch im 3D geht, oder ich muss alle Punkte auf die xy Ebene rotieren, damit bei allen die z-Koord 0 ist.

Das mit dem Algo manipulieren würde ich als sehr schön ansehen, allerdings scheitert es schon an einer Lexikographen Ordnung für 3 Dimensionen. Und ob die Funktion cross im 3D genauso funktioniert wie im 2D, bin ich mir auch nicht so sicher.
(!?)

Also bleibt mir wohl nur das Rotieren der Punkte übrig.
Allerdings bin ich mir da noch nicht so sicher, wie ich zu der richtigen Lösung komme.

Meine bisherige Idee wäre, den Winkel zwischen der Normalen der gegebenen Ebene und der Normalen der xy-Ebene bestimmen
und dann jeden Punkt um diesen Winkel drehen.

Doch wie geschieht das Drehen?
Ich setzte den Winkel in die Drehmatrix R ein
und multipliziere jeden Punkt mit R?
Welchen Einheitsvektor brauche ich dann um die Drehmatrix zu bilden?

Fragen über Fragen. wäre super wenn mir einer einen Tipp geben könnte

VG

Stell Dir vor, du würdest die Punkte auf die Ebene "rotieren", das würde doch aber nichts anderes bedeuten als dass Du die Punkte in einem Koordinatensystem darstellen möchtest, dessen x1-x2-Achsen in der Ebene der Punkte liegen.
Um die Punkte in dieses Koordinatensystem zu projizieren, brauchst Du sie also nur per Skalarprodukt mit den x1-x2-Vektoren zu multiplizieren, falls diese ein orthogonales System bilden.
Jetzt kommt es darauf an, ob Du x1 und x2 schon vorgegeben hast. Wenn nicht, dann zieh zwei unterschiedliche Punkte voneinander ab, schon hast Du eine Achse. Die zweite Achse bildest Du dann beispielsweise, indem Du eine weitere nicht-kolinieare Achse bildest und zweimal ein Kreuzprodukt anwendest, oder irgendwie anders, vielleicht hast Du ja die Normale der Ebene gegeben, ich weiß es nicht.

Wie dem auch sei, wenn Du nun x1 und x2 orthogonal gegeben hast, beschränkt sich die Veränderung des Algos darauf, dass Du, anstatt die Koordinaten der Punkte direkt zu vergleichen, einfach die Ergebnisse der Skalarprodukte der Punkte mit den entsprechenden Basisvektoren vergleichst.

otze

Ich würde da ganz anders ran gehen: berechne doch einfach für jden diner Punkte die 2D-Koordinate auf der Ebene.

Dafür musst du deine Ebene umformulieren, sodass du sie anhand von 2 orthogonalen Richtungsvektoren u_1 und u_2 sowie eines Punktes x_0 definierst. Das kannst du zum Beispiel machen, indem du 3 beliebige Punkte deiner Menge nimmst (x_0, x_1 und x_2) und dann eine gram schmidt orthonormalisierung der differenzvektoren machst:

w_1 = x_1-x0
u_1 = w_1/ ||w_1||
w_2 = (x_2-x_0) - <x_2-x_0,u_1>*u_1
u_2 = w_2/ ||w_2||

wobei <x,y> das Skalarprodukt ist.
Nun erstellst du die 2x3 Matrix U mit Zeilen u_1 und u_2 und kannst nun jeden deiner Punkte x auf der Ebene darstellen als:

x_Ebene = U(x-x_0)

zurück nach 3D kommst du dann mit

x = U^T x_Ebene +x_0

Otze beschreibt praktisch, was ich sagte, wohl etwas besser. Wichtig anzumerken ist, dass es auf die Skalierung des Koordinatensystems nicht ankommt, um die Ordnung einzuhalten, eine Parallelverschiebung ist auch nicht nötig, Matrizen schon gar nicht.

icewater

Ok super. Damit bekomme ich es bestimmt umgesetzt.
Danke für die Antworten.

otze

Vorschlager schrieb:

Otze beschreibt praktisch, was ich sagte, wohl etwas besser. Wichtig anzumerken ist, dass es auf die Skalierung des Koordinatensystems nicht ankommt, um die Ordnung einzuhalten, eine Parallelverschiebung ist auch nicht nötig, Matrizen schon gar nicht.

1. Für die Orthogonalisierung von u_2 musst du irgendwann die Norm von u_1 berechnen.
2. Wenn du nicht normalisierst, dann kommst du hinterher nicht mehr so einfach zurück in das ursprüngliche Koordinatensystem.
3. Natürlich sind Matrizen Syntaxzucker man braucht sie nirgendwofür. Trotzdem machen sie das Lben viel einfacher.

Für orthogonale Systeme braucht man üverhaupt gar keine Einheitsvektoren
Ich wollte nie die Punkte dahin projizieren und schon gar nicht zurück, ich schlage vor, die Projektion nur für die Ordnung zu verwenden
In diesem Fall sind sie Overhead für eine Flexibilität, die man nicht braucht, wir betrachten nicht alle möglichen linearen Abbildungen. Und man braucht nur für einen verschwindend geringen Teil der Punkte überhaupt die projizierte y-Koordinate.

Und 4) Wenn ich gerade so darüber nachdenke, dann müsste sich die Ordnung x->y in dem Alghoritmus einfach nur die analoge Ordnung x->y->z ersetzen lassen, eigentlich ist gar keine Projektion nötig. Könnte aber zu unschönen Ergebnissen führen, wenn man "entartete" Fälle untersucht und die Punkte etwas verrauscht sind, also nicht perfekt in der Ebene liegen.

Algorithmus... Irgendwie passiert mir das jedes zweite Mal

Okay, also um vernünftige Vektoren zu bilden um das Koordinatensystem zu bilden, muss man doch eigentlich sowieso im Zweifel alle Punkte betrachten? Also würde ich vielleicht eher die Bounding-Box verwenden und die "kleinste" Ausdehnung aus dem Algorithmus werfen und anschließend zumindest gedacht in 2D weitermachen, genau wie der Algo es vorschreibt, bloß mit entsprechender Auswahl bei der Bildung der Ordnung.

otze

für axis aligned bounding boxes kann ich dir sofort ein Gegenbeispiel geben (eine Ebene die ungefähr 45° auf der Standardbasis im R^3 liegt) und allgemein rotierte Bounding boxes sind ein schwierigeres Problem als das hier zu lösende.

Für orthogonale Systeme braucht man üverhaupt gar keine Einheitsvektoren

Natürlich kannst du drum herum kommen und im R^3 haste ja noch den Kreuzprodukt operator. Aber ab R^4 kriegste Probleme, den ordentlich zu definieren und fällst dann doch wieder auf Verfahren zurück, die Orthonormalbasen erzeugen

In diesem Fall sind sie Overhead für eine Flexibilität, die man nicht braucht, wir betrachten nicht alle möglichen linearen Abbildungen.

Häh? Wovon redest du? Wir brauchen exakt 6 Parameter für die hier benötigte Abbildung, die Matrix hat 6 Parameter. Welcher Overhead?

Ich hab keine Ahnung wovon Du redest... hast Du Dir überhaupt mal die Zeit genommen zu schauen, was der OP erreichen wollte?
Der Weg, die Punkte zu "rotieren" war ein naheliegender Lösungsansatz, um auf einen kompatiblen Datensatz für seinen 2D-Algorithmus zu kommen (Auch dafür habe ich Deinen Weg aufgezeigt und vollig richtig bemerkt, dass man die Basisvektoren nicht zu normalisieren braucht, da man die projizierten Punkte bloß für die Ordnung benötigt, die auch nach Skalierung erhalten bleibt). Ich mache hier die ganze Zeit nur Vorschläge, wie er seinen 2D-Algorithmus möglichst effizient auf seine 3D-Daten laufen lassen kann, möglichst ohne Hin- und Herzutransformieren.

Und jetzt kommst Du auf einmal mit N-Dimensionalen Räumen? Oo Was geht denn hier bitte ab?!

Und zu der Sache mit der 45°-Ebene... ich weiß natürlich nicht wie Du das genau meinst, aber ich sehe auch gerade problematische Fälle, bei denen man eine dumme Wahl treffen würde, da ich etwas zweifelte verwendete ich auch das konjunktiv...

Dann nimmt man eben die Normale der Ebene, und schmeißt die Koordinate mit der größten Komponente raus. Das kann wohl kaum noch schiefgehen... Immerhin spart man sich N+X (X<<N) Skalarprodukte, beziehungsweise 2*N Vektor-Matrixmultiplikationen nach Deiner Logik...