PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Konvexes Polytop approximieren

Actionhank
2012-09-30, 13:16:43
Kennt jemand zufällig einen Algorithmus, um ein konvexes Polytop durch ein inneres einfacheres konvexes Polytop zu approximieren? Habe dazu bisher ein Paper von Reisner gefunden. Kennt jemand noch was anderes? Achso, Dimension sollte nicht fest sein, aber n=3 wäre auch interessant.

Thx.
Gast
2012-10-01, 09:02:52
Wie genau soll das gehen? Wenns konvex ist ist es ja bereits die convex hull der Eckpunkte, wie willst du das weiter vereinfachen ohne Punkte wegzulassen? Oder ist das die Frage, welche Punkte man am besten weglässt? Da fällt mir auf die Schnelle ein jeweils die Winkel an allen Vertices berechnen und den weglassen wo der Winkel am kleinsten ist. Das ist dann die "spitzeste" Ausbuchtung und es geht am wenigsten Information verloren. Muss man vielleicht auch noch die Fläche drunter berechnen falls es eine sehr lange Ausbuchtung ist.
Actionhank
2012-10-01, 10:15:14
Ja, man lässt einfach Ecken (Vertices) weg. Oder aber lineare Beschränkungen mit denen man auch ein Polytop definieren kann.
Gast
2012-10-01, 10:34:16
Dazu müsste man wahrscheinlich die Motivation wissen. Soll das resultierende Polytop auch konvex sein? Soll es möglichst kleine Fläche haben? Soll es möglichst ähnlich dem Original sein? Soll es möglichst "rund" sein?
Actionhank
2012-10-01, 12:21:32
Dazu müsste man wahrscheinlich die Motivation wissen. Soll das resultierende Polytop auch konvex sein? Soll es möglichst kleine Fläche haben? Soll es möglichst ähnlich dem Original sein? Soll es möglichst "rund" sein?

Ok, etwas ausführlicher: Das "innere" Polytop muss auch konvex sein. Eine Bewertung der Approximation erfolgt durch das Volumen. Je näher das innere approximierende Polytop an das ursprüngliche Volumen kommt, desto besser.

Hier mal eine Arbeit dazu:
Dropping a vertex or a facet from a convex polytope (http://www.degruyter.com/dg/viewarticle.fullcontentlink:pdfeventlink/contentUri?format=INT&t:ac=j$002fform.2001.13.issue-3$002fform.2001.012$002fform.2001.012.xml)
MartinB
2012-10-01, 19:50:55
Such mal nach "Hausdorff Abstand" bzw "Parametrischer Abstand".

Oder direkt den "Douglas-Peucker" Algorithmus.
DocEW
2012-10-02, 21:53:10
Schau mal hier (http://www.itwm.fraunhofer.de/fileadmin/ITWM-Media/Abteilungen/BV/Pdf/Diplomarbeit_Kessler.pdf) in Kapitel 3. Suchst du sowas?
Oder direkt den "Douglas-Peucker" Algorithmus.
Ist das nicht eher ein Verfahren zur Vereinfachung von Streckenzügen? Oder kann man das Vorgehen irgendwie auf Polytope übertragen?