Hallo,

ich würde gerne einen Algorithmus entwickeln der zwischen konkaven und konvexen Polygonen unterscheiden kann. Soweit ich weiß, ist ein konvexes Polygon ein Polygon mit Winkeln, die 180° nicht überschreiten (oder wie ich es hier schon gefunen habe: wenn man eine Schnur drum legt, liegt diese überall an).

Nun kann man ja von Vektor zu Vektor des Polygons gehen und nachsehen ob die Richtung immer die gleiche ist (im zweidimensionalen raum). Wenn es immer rechts oder links herum geht, ist das Polygon konvex. Ist zwischendrin eine Richtungsänderung zu erkennen, muss es konkav sein.

Kann mir jemand sagen wie man das im dreidimensionalen Raum überprüfen kann?

Danke

Ich würd rekursiv durch die Eckpunkte gehen, daraus Vektoren machen (also aus Punkt 1 und zwei Vektor 1 und aus Punkt 2 und 3 Vektor 2, usw) und dann per Skalarprodukt den Winkel berechnen. Dann schaust du einfach nach, ob die Summe der Winkel größer als (Summe der Punkte - 2)*180 ist.

_________________
"Du musst ein Schwein sein in dieser Welt, sangen die Prinzen, das ist so 1.0. Du musst auf YouTube zeigen, dass dir dein Schweinsein gefällt, das ist leuchtendes, echtes Web 2.0."
- Hal Faber
Meine Homepage: http://laboda.delphigl.com

gute Idee

du kannst dir auch die normale des polygons berechnen und das koordinatensystem ins polygon drehen. dann kannst du den 2d algorithmus verwenden

Was ist die Normale eine Polygons?

Die Normale ist ein Vector welcher Senkrecht auf dem Polygon steht und die Länge 1 hat.

Mehr dazu : Normale

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Meinst du mit Polygon im R3 ein FLACHES, konkaves Polygon, oder ein Dreidimensionales, NICHT flaches Polygon?
Wenn das Polygon flach ist, kannst du, wie thordk gesagt hat, einfach die 2d Variante verwenden, ist es jedoch 3d, duerfte das mit der normalen schwierig werden...

Ausserdem: Ist dein Polygon trianguliert, also zeichnest du lauter Dreiecke, oder hast du nur die Eckpunkte?
Die Triangulierte Version hat den Vorteil, das du einfach schaust, in welcher Drehrichtung die einzelnen Dreiecke definiert sind (im oder Gegen Uhrzeigersinn) und wenn eines andersrum ist, ist das Polygon konvex.

MFG gmgler

_________________
Geniale Menschen sind selten ordentlich, ordentliche selten genial (Albert Einstein)

Soweit ich das gelernt habe im Studium, dürfen Polygone für eine korrekte Darstellung in OpenGL nur konvex und eben sein. Wenn eines von beiden nicht gilt, kann man nicht garantieren, dass die Ausgabe konstant bleibt.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Wenn man statt GL_POLYGON einfach GL_TRIANGLE_FAN nimmt (wobei ich nicht genau weiß, warum es ersteres überhaupt gibt), dann kann man auch bei nicht ebenen, konkaven Polygonen noch vorhersagen, wie es aussieht. Ändert aber nichts daran, dass mans nicht machen sollte...

_________________
[18:30] tomok: so wie ich das sehe : alles. was nich was anderes ist als nen Essay ist nen Essay

hi, i'm a signature viruz, plz set me as your signature and help me spread

@Al: Ich hab ja auch Polygone gemeint nicht dreiecke. Das ein TRIANGLE_FAN nicht in einer Ebene sein muss ist durchaus richtig.

_________________
Blog: kevin-fleischer.de und fbaingermany.com