polygonzug triangulieren
-
Ich hab zwei coplanare Dreiecke A & B
(beide in der selben Ebene liegend) geschnitten.
Diese habe ich in verschiedene Polygonzyge
- einfach verkette Listen; jeder Punkt zeigt auf seinen Nachfolger-
zerlegt; z.B. den Durchschnitt, A-B usw.
Jetzt suche ich einen Algorithmus, der diese Polygonzüge mit maximal 7 Punkten neu trianguliert.Kenn mich jedoch überhaupt nicht damit aus.
Wäre über Hilfe bzw. Unterstützung dankbar.
-
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.
-
würd erstmal die konvexe hülle aller 6 punkte berechnen. dabei kommt ein polygon mit 3-6 ecken heraus. ausgehend von diesem kannst du jetzt die restlichen 1-4 punkte dazuholen. um das zu tun, nimmst du dir jede kante vor und prüfst, ob die beiden zugehörigen eckpunkte zu unterschiedlichen dreiecken gehören. ist das der fall, berechnest du den schnittpunkt der zu diesen ecken gehörenden geraden der ursprünglichen dreiecke (liegen innerhalb des polygons, weil konvexe hülle). können auch mehrere schnittpunkte vorhanden sein, also immer den nehmen, der am nächsten an der gerade bearbeiteten kante des neuen polygon liegt.
wenn du das einmal gemacht hast, bist du fertig. wenn dein polygon allerdings schon vorher 7 ecken besitzt, kannst du abbrechen.
illustration
http://img477.imageshack.us/img477/5640/dreiecksm8.gif
-
Da hab ich mich eingangs wahrscheinlich nicht exakt genug ausgedrückt.
für mich ist es wichtig, dass ich die beiden urspürnglichen dreiecke a und b zerlege in- A-B
- B-A
- den druchschnitt von A und B
der dritte fall ist kein problem, da der durchschnitt immer konvex ist, jedoch müssen a-b und umgekehrt nicht konvex sein.
