Innenwinkel eines Polygon (konkav <> konvex)

[poiz]

Ich möchte von einem simplen Polygon bestimmen, welche Ecken bzw. Schnittpunkte der Kanten konkav und welche konvex sind.
Wenn der Innenwinkel grösser als 180 Grad ist, dann ist die Ecke ja konkav. Dazu muss ich aber bestimmen können, welches der Innenwinkel (bzw. Aussenwinkel) ist und das will mir nicht so recht gelingen. Vielleicht gibt es aber auch einen anderen Weg.

Gegeben sind einfach alle Punkte des Polygons.

Danke für die Hilfe.

[Ben04]

Seien P_i die Ecken des Polygons. Das Zeichen von det(vec(P_n-1, P_n), vec(P_n, P_n+1)) verrät dir ob du an P_n im Uhrzeigersinn oder dagegen abbiegst. Nun betrachtest du alle Ecken, der Ausreißer wird deine gesuchte Ecke sein.

[poiz]

Danke für die prompte Antwort!

Ist vec(P_n-1, P_n) ein Vektor mit Startpunkt in P_n-1 und Endpunkt in P_n?

Funktioniert das Ganze auch, wenn das Polygon mehrere "konkave" Ecken hat? Also ich möchte alle konkaven Ecken bestimmten können.

Werd es mal in MatLab ausprobieren...

[Jester]

Zweimal Ja.

[Ben04]

poiz schrieb:

Funktioniert das Ganze auch, wenn das Polygon mehrere "konkave" Ecken hat? Also ich möchte alle konkaven Ecken bestimmten können.

Es geht immer solange du strikt mehr konvexe Ecken als konkave hast. Sonst kannst du mit dem Verfahren nicht feststellen welche konkave und welche konvex sind.

Ein Beispiel für ein Polygon bei dem es genauso viele konkave wie konvexe Ecken gibt wäre ein Stern.

[poiz]

Hab den Vorschlag über die Determinate in MatLab kurz ausprobiert und es scheint so weit auch zu funktionieren. Gibt es denn eine andere Variante, die immer funktioniert? Denn der Benutzer kann ein beliebiges Polygon (ohne "Löcher" und Überschneidungen) eingeben, also auch bspw. einen Stern. Wobei ein Test mit dem Stern (4 konkave und 4 konvexe Ecken) auch funktioniert hat bei meinen Versuchen...

Ich habe unter http://local.wasp.uwa.edu.au/~pbourke/geometry/clockwise/index.html#concave noch etwas gefunden. Hier wird mit dem Kreuzprodukt gearbeitet. Gilt hier die Einschränkung, dass es strikt mehr konvexe Ecken haben muss, ebenfalls? Diese Variante hab ich auch kurz getestet mit dem selben Resultat wie oben.

[Ben04]

Seien u und v Vektoren welche in den beiden ersten Dimensionen enthalten sind dann gilt |u x v| = det(u, v) und damit ist das Verfahren das gleiche wie das welches ich beschrieben habe.

Wobei ein Test mit dem Stern (4 konkave und 4 konvexe Ecken) auch funktioniert hat bei meinen Versuchen...

Du weißt nicht welche Ecken konkave sind und welche konvex sind. Du weißt aber welcher Gruppe sie angehörten. Wenn du also von einer Ecke weißt was sie ist dann weißt du es von allen. Du hast also eine 50% Chance beim raten. Es ist also nicht erstaunlich, dass es das richtige Resultat geliefert hat.

[poiz]

Gilt denn nicht folgendes? :
-liegen die aufeinanderfolgenden Punkte des Polygons im Gegenuhrzeigersinn vor, so ist das Vorzeichen der Determinante von konkaven Ecken negativ
-liegen die aufeinanderfolgenden Punkte des Polygons im Uhrzeigersinn vor, so ist das Vorzeichen der Determinante von konkaven Ecken positiv

Den Uhrzeigersinn der Punkte kann ich ja bestimmen und damit auch das "Vorzeichen" einer konkaven bzw. konvexen Ecke zuweisen.

[CStoll]

Wenn du weißt, in welcher Richtung du um das Polygon herumgelaufen bist, kannst du feststellen, welche Ecken konkav waren (wenn du im Uhrzeigersinn wanderst, alle, die nach links abgebogen sind). Wenn du die Umlaufrichtung nicht kennst, mußt du raten, welche der Gruppen die konkaven Ecken sind.

Also würde ich vermutlich dafür sorgen, daß ich in einer definierten Richtung um das Polygon laufe - dann ist die Zuordnung klar.