Algorithmen gesucht: Convex Hull (3D) und Triangulierung

ein anderer Algo für die Konvexe Hülle geht so:

tiefsten Punkt in der Punktmenge suchen. Dann den nächsten Verbindungspunkt mit den größten Winkel suchen. und das immer so weiter bis man einmal rum ist. Der Vorteil ist,.. man erhält die Punkte geordnet in der Reihenfolge. Das Problem mit
"hull.add(vertex) " entfällt

Hier ist eine sehr schöne Beschreibung von Triangulierverfahren für Punktmengen:
http://www.wwk.forst.tu-muenchen.de/chair/people/SeifertS/Diplom/MaterialMethoden/VisMethoden/ErzeugungBoden.html
Danach kannst du dir den Algorithmus selbst schreiben.

BILL schrieb:

ein anderer Algo für die Konvexe Hülle geht so:

tiefsten Punkt in der Punktmenge suchen. Dann den nächsten Verbindungspunkt mit den größten Winkel suchen. und das immer so weiter bis man einmal rum ist. Der Vorteil ist,.. man erhält die Punkte geordnet in der Reihenfolge. Das Problem mit
"hull.add(vertex) " entfällt

Das funktioniert so einfach aber nicht in 3D. Da mußt Du dann schon mit einer Ebene und deren Winkel rumwedeln, das wird langsam und mit steigender Dimension wird es immer langsamer.

Zum selber implementieren würde ich eines der randomisierten Verfahren empfehlen, die sine meistens etwas einfacher.

rapso

BILL schrieb:

ein anderer Algo für die Konvexe Hülle geht so:

tiefsten Punkt in der Punktmenge suchen. Dann den nächsten Verbindungspunkt mit den größten Winkel suchen. und das immer so weiter bis man einmal rum ist. Der Vorteil ist,.. man erhält die Punkte geordnet in der Reihenfolge. Das Problem mit
"hull.add(vertex) " entfällt

Du hast wohl versucht den jarvis algorithm zu beschreiben, dabei sollte man drauf achten, dass auch in diesem fall (gerade wenn man mit winkeln rechnen sollte, fass aber in diesem fall eigentlich nicht noetig ist) float ungenauigkeiten auftretten koennen die zwei im selben Winkel liegende punkte falsch einordnen koennen.
fuer 2D wuerde ich von daher eher graham scan empfehlen.

aber 2D ist auch der trivialfall, den man sicher mal in ner stunde runter implementiert ohne ueber einen algorithmus zu lesen. ab 3d wird es knackig.

Erstaunlich da sagt man was, uns schon tauchen 10 Leute auf die es besser wissen. Tipps geben kann keiner aber besser wissen tun es alle.... wie immer...
Nun gut ich habe solche Dinge Programmiert und kann wenigsten aus Erfahrung berichten.

Ich denke Algorhythmiker meinte die 2d Ebene.
In 3d würde ich den Marching Cubes empfehlen.

BILL schrieb:

Ich denke Algorhythmiker meinte die 2d Ebene.
In 3d würde ich den Marching Cubes empfehlen.

Ja klar, deswegen hat er auch R^3 geschrieben, was?

Ich sehe zwar, wie man mit Marching Cubes eine gesampelte Oberfläche wieder zusammensetzt, aber wie man damit die konvexe Hülle bestimmt ist mir nicht so richtig klar. Ich denke, dafür sind andere Verfahren besser geeinget.

Auch mit den Triangulierungsverfahren muß man ein kleines bißchen vorsichtig sein, schließlich geht es nicht um eine Triangulierung in der Ebene, sondern auf einer Kugel. Glücklicherweise ist das aber fast das gleiche.

rapso

BILL schrieb:

Tipps geben kann keiner aber besser wissen tun es alle.... wie immer...

sowas kommt meist von leuten auf die das am besten zutrifft, komisch, vielleicht weil sie das zu oft selber hoeren?

Ich verwende jetzt die Delaunay-Klasse. Gibt es eine Möglichkeit, aus einer gegebenen Punktmenge aus der berechneten konvexen Hülle die Vertices, die im Inneren liegen (also irrelevant sind für die Hülle), zu entfernen?

ja, indem man für jeden Knoten v_i prüft, ob v_i in der konvexen Hülle der übrigen v_j enthalten ist:
v_i = sum_{j != i} c_j v_j, sum_j c_j = 1, 0 <= c_j <= 1

Dazu muss ich aber für jeden Punkt ein LGS lösen. Gibt es keine *eingebaute* Funktion, die das automatisch macht?