spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ist das polygon konkav oder konvex?

Dann wirst du über diese Methode der Schnittpunkt Berechnung nicht herum kommen.
Was das Ganze aber noch ein wenig vereinfacht ist folgendes:

Wenn man sich das Polygon betrachtet und alle Punkte im Uhrzeigersinn zu Strecken zusammen setzt, dann kann man prüfen, ob beide Punkte der zu prüfenden Strecke rechts von der Strecke des Polygons sind. Zusätzlich kann man noch prüfen, ob einer der beiden Punkte der Strecke auf der Strecke des Polygons sitz.
Wenn die beiden Punkte rechts von allen Strecken sind (oder auf der Strecke), dann ist die Strecke innerhalb des Polygons.
Bei konkaven Polygonen wird das schwieriger, da hier tatsächlich geprüft werden muss, ob eine der Teilstrecken geschnitten wird.
Allerdings gleiche Vorgehensweise.
Zuerst checken ob Punkte rechts oder darauf und dann noch prüfen ob sie vollständig geschnitten oder nicht.

Um viele unmögliche Fälle auszuschließen, kannst du dir das bounding Rect des Polygons erstellen und erstmal schauen ob überhaupt beide Punkte innerhalb des Rechtecks liegen.

Zusätzliche Informationen über den konkreten Anwendungsfall könnten dabei helfen, eine einfachere Lösung zu finden. Woher kommen die Polygone und Linien, und was stellen diese dar? Sind die Linien der Polygone immer waagerecht und senkrecht oder ist das in dem skizzierten Bild nur zufälligerweise so?

Für konvexe Polygone wäre die Ermittlung relativ einfach: man prüft für beide Punkte der Linie, ob diese rechts oder links von jeder Kante des Polygons liegen (abhängig davon, ob diese im oder gegen den Uhrzeigersinn betrachtet werden).
Hat man mehrere Konvexe Polygone, müssen beide Punkte in irgendwelchen der Polygone liegen und weiterhin darf die Linie sich nur mit Polygonkanten schneiden, die von 2 der Polygone geteilt werden.
Ein Konkaves Polygon kann man durchaus in mehrere Konvexe Polygone aufteilen und die obere Prüfung durchführen. Wie aber bereits geschrieben kann es sein, dass sich das Problem noch einfacher lösen lassen könnte, sollte es für die Polygone oder Linien noch weitere Einschränkungen geben.

Dieses Problem ist doch nun wirklich ein alter Hut, zu dem man haufenweise Lösungen im Netz findet. Eine kurze Suche bringt einen beispielsweise dorthin: http://stackoverflow.com/questions/44978…-convex-polygon