geschlossene Polygone triangulieren
-
Kennt jemand von euch eine bibliothek bzw. hat jemand einen fertigen algorithmus für C++, der geschlossene polygone, die sich nicht selber schneiden - können sowohl konkav als auch konvex sein - trianguliert. Sie bestehen aus 4 bis 7 Punkten. Das muss kein schneller algorithmus sein.
-
Was verstehst du unter triangulieren? Zerlegen eines Polygons in Dreiecke? muessen die bestimmte Bedingungen erfuellen?
-
Dieser Thread wurde von Moderator/in CStoll aus dem Forum C++ in das Forum Mathematik verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
ja, der geschlossene polygonzug - der übrigens in einer ebene liegt - darf nur mehr aus dreiecken bestehen. Neue Punkte kann man einfügen. Wichtig ist, dass jedes Dreieck aus genau drei Punkten -Eckpunkte- besteht. Wäre ein vierter Punkt auf einer Seite, so müsste man dieses Dreieck in zwei Dreiecke teilen.
-
Für 4-7 Punkte ist ja (nahezu) jeder beliebige Algorithmus effizient. Such einfach zwei Punkte, die sich sehen. Füg die entsprechende Kante hinzu. Jetzt zerfällt das Polygon in zwei Polygone, die Du rekursiv triangulieren kannst.
Für größere Probleme gibt es schnelle Algorithmen, die O(n log n) Zeit brauchen. Es gibt sogar einen Linearzeitalgorithmus, der ist allerdings so kompliziert, dass ihn kein Mensch benutzt. Schwer zu implementieren und für realistische Eingabegrößen vermutlich zu langsam.