Triangles in Concaven Polygonen

[FireMail]

Hiho,

hab mal wieder ne kleine aber feine frage ;)

und zwar hab ich ein concaves polygon vorgegeben bzw dessen referenz vertice points.
wie man auf der linken seite in der graphik sieht, ist es kein problem ein triangle reinzupassen - überschnitte sind mittels intersect berechnung leicht abzufangen.

auf der rechten seite sieht man nun die verzwickte lage. es tritt keine intersection (überschneidung) auf - jedoch liegt eine gerade außerhalb des concaven polygons.

wie man checkt ob ein punkt innerhalb eines beliebigen polygons liegt ist mir klar - jedoch ist es mit einer linie wirklich komplex :(


hat einer von euch eventuell eine idee?

[Jan Krüger]

Es wird dir wahrscheinlich weiterhelfen, den Winkel in jedem Eckpunkt auszurechnen. Wenn du dann feststellst, dass der Winkel einer der Eckpunkte zwischen denen, die du verbindest, in die falsche Richtung geht (konkav ist), ziehst du keine Verbindung.

Ich habe gerade schon einen Sonderfall gefunden, in dem man das Polygon mit diesem Verfahren schon nicht mehr in Dreiecke aufteilen kann, aber einen Versuch war's wert. :]

Update: stopp, Kommando zurück. Wenn man nach jeder eingefügten Sehne die Betrachtung auf die beiden Polygone beschränkt, in die man das Ganze gerade aufgeteilt hat, geht's. Hach, ich liebe Divide and Conquer...

[FireMail]

ich hab zwar die eckpunkte des polygons in einem array gegeben - daraus kann man zwar einen winkel zwischen 2 linien berechnen - jedoch kann es leicht sein dass in anderer form so stimmen würde. glaube nicht dass das eine allgemein funktionierende lösung ist :-/

wenn ich dich falsch verstanden hab - kannsts mal kurz skizzieren?

[Jan Krüger]

Naja:

1) ziehe eine Verbindung zwischen zwei Punkten. Die Kanten zwischen den zwei Punkten dürfen in der einen Richtung keine konkaven Winkel haben.

2) betrachte jetzt die beiden Polygone, die entstehen, wenn man das Ursprungspolygon an der neuen Verbindung durchschneidet, und führe den Algorithmus für beide wieder aus. Terminierungsbedingung: ein Polygon hat nur noch drei Punkte.