Wie kann ich bei einem konkaven Polygon feststellen, ob ein Segment (Kante), das zwei Scheitelpunkte verbindet, innerhalb des Polygons liegt? Im Bild unten gibt es eine Kante (rot), die zwei gleiche Eckpunkte verbindet, die nicht im ursprünglichen Polygon verbunden waren. Ich habe keine Ahnung, wie Innen- und Außen bestimmen. Danke für jede Hilfe.Bestimmen, ob das Segment innerhalb eines Polygons liegt
Wenn das zusätzliche Segment jedes andere Segment des Polygons schneidet, ist es teilweise innerhalb und teilweise außerhalb.
Andernfalls nehmen Sie einen Punkt auf dem zusätzlichen Segment, z. B. seinen Mittelpunkt, und überprüfen Sie, ob es innen oder außen ist. Um zu prüfen, ob sich ein Punkt im Inneren befindet, nehmen Sie einen davon ausgehenden Strahl und zählen Sie die Anzahl der Schnittpunkte mit Polygonkanten. Wenn die Anzahl der Schnittpunkte ungerade ist, ist es innen.
Klingt einfach, aber seien Sie bereit, Sonderfälle wie kollineare Linien oder Kreuzungen an Eckpunkten zu behandeln. Das wird die Implementierung erschweren.
Wie werden die Strahlen von dem Punkt verlängert? Es kann unendlich viele von ihnen geben. Auch im von mir zur Verfügung gestellten Bild sehe ich nicht, wie ungerade/gerade unterschieden würde. Für mich sieht es so aus, als wäre es immer die gleiche Anzahl. – Altidore
@ Altidore: Es spielt keine Rolle, theoretisch können Sie jede Richtung verwenden. In Ihrem Beispiel wäre ein horizontaler Strahl jedoch eine schlechte Wahl, da er mit einigen Kanten kollinear ist. Das ist einer der Spezialfälle, die ich erwähnt habe. –
@Altidore: Nur zur Verdeutlichung: Entsprechen Sie einer Linie, die sich von einem Punkt in beide Richtungen erstreckt, erstreckt sich ein Strahl nur in einer Richtung. Sie zählen also nur die Schnittpunkte auf einer Seite des Punktes. –