Algorithmen gesucht: Convex Hull (3D) und Triangulierung
-
Ich suche ein Buch oder ein gutes Skript (aber Buch wär mir lieber), wo schnelle und einfach zu implementierende Algorithmen für
a) Berechnung der konvexen Hülle einer endlichen Punktmenge im IR³
b) Triangulierung der in a) berechneten konvexen Hülle, sodass ich sie in einem 3D-Programm ausgeben kann.Vielen Dank!
-
Ich habe Computational Geometry: Algorithms and Applications, behandelt konvexe Huellen und Triangulierung. Leider wirst du daraus keine schnelle und einfache Implementierung ableiten koennen. Die Algorithmen sind nicht einfach und man muss sich schon Zeit nehmen, um ein tieferes Verstaendnis dafuer zu entwickeln. Eine Bibliothek wie Qhull ist fuer dich wohl besser.
-
die algorithmen sind zumiest relativ einfach, problematisch sind float ungenauigkeiten und unmengen von sonderfaellen.
an sich ist es nur eine schleife
for every vertex
if hull.outside(vertex) then
hull.add(vertex)der outside test is an sich auch simpel bei convexen koerpern, das komplexe faeng int "add" an.
der kleinste koerper den du representieren kannst hat 4 punkte, was wenn alle 4punkte aber auf einer ebene liegen? was wenn wirklich alle punkte die du je einfuegst auf einer ebene liegen, dann musst du ja trotzdem eine saubere convexe huelle erstellen.
kurz: die algorithmen sind simpel, die implementierung ein kopfschmerz, folge dem rat von knivil
-
Das Buch, das knivil angegeben hat, ist wirklich sehr gut. Es gibt übrigens ziemlich viele Algorithmen für konvexe Hülle in 3D. Aber ich stimme da ebenfalls meinen Vorrednern zu, dass es einfach ist, etwas fertiges zu nehmen, als das selbst zu implementieren. Qhull ist sicher recht bekannt und wird viel verwendet. Wenn es etwas mehr C++ sein soll, kann ich auch [url="http://www.cgal.org/"]CGAL[/url] empfehlen. Ist nicht ganz einfach zu benutzen, aber sehr mächtig und vor allem sehr genau. Die verwenden exakte Arithmetik um Dir wirklich auch die korrekte konvexe Hülle zu berechnen. Damit es nicht unheimlich lahm wird berechnen sie erst mit floating points und nur wenn sie feststellen, dass die Genauigkeit nicht reicht wechseln sie auf andere Methoden. Dadurch bleibt alles schön flott.
-
Danke, ich versuchs mal mit CGAL
-
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älltDas 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.
-
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älltDu 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.
-
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?