Algorithmus gesucht: Schnitt Polygon <-> Gerade

[Codewalker]

Hallo zusammen.

Ich habe eine Problemstellung und weiß nicht, wie ich es genau angehen soll: Ich habe 2 gegebene Punkte sowie eine Menge von Polygonen. Ich möchte nun für ein Polygon testen, ob die Strecke (nicht die Gerade) zwischen diesen beiden Punkten, das Hexagon schneidet.
Wie würdet ihr sowas überprüfen? Ich habe eine Hilfsfunktion, die prüft ob ein Punkt im Polygon liegt - aber das hilft mir nicht wirklich weiter. Ich kann ja nicht alle möglichen Punkte durchprobieren.

Danke und Grüße

[kalmi01]

Hallo Codewalker,

eigentlich doch reecht einfach, schneidet Deine Strecke AB eine der Polygonlinien, dann schneidet AB auch Dein Polygon.
Algo's dafür findest Du zB. hier.

[idontwantaname]

Also ich würde das so lösen: mache aus dem Polygon eine Ebene und schneide die Gerade bzw. erweiterte Strecke mit dieser. Nun prüfst du, ob der Schnittpunkt im Polygon liegt - wenn ja, dann prüfst du noch, ob der Schnittpunkt auch auf der Strecke liegt ;)

[Nikolas]

Wenn du nur mit Hexagonen arbeitest, solltest du vorher noch eine kleine Abfrage mit einer BoundingBox (circle) vorschalten. Die Eckpunkt deines Polygons liegen auf einem Kreis, so dass eine Gerade sicher diesen Kreis schneiden muss, wenn sie das Polygon schneidet. Die Abfrage, ob der Kreis geschnitten wird, ist eine einfache quadratische Gleichung, damit kannst du dir die ausfwändige Lösung mit dem Schnitt mit allen Polygonstrecken sparen.

[Codewalker]

Danke für die Tipps. Ich denke mit dem Test auf BoundingBox, ein paar generelle Ausschlüsse durch X/Y-Koordinaten (was zu weit weg liegt, muss ich nicht prüfen) lässt sich die Zahl der Hexagons so weit reduzieren, dass der Test mit den 6 Seiten performancemäßig nicht groß auffallen sollte.
Das ganze soll ein Line-of-Sight - Algorithmus werden - bin mir noch nicht sicher, ob ich das sauber hinbekomme, weil ich ja noch bedenken muss, welche Felder im Verlauf der Strecke durch andere bereits geblockt werden. :gruebel:

[Medium]

Reden wir eigentlich über 2D oder 3D? Bei 2D reicht es die Schnitte mit den Kanten zu prüfen, in 3D kannst du immer noch die Fläche treffen, ohne eine Kante zu schneiden.

[Codewalker]

Nein, ist alles nur 2D

[Nikolas]

Wie viele Sechsecke hast du denn und wie oft musst du diese Suche durchführen.
Mach dir am Besten erst mal keine Gedanken über die Geschwindigkeit, sondern schreib erst eine kleine Testversion.
Vielleicht ist die Rechenzeit überhaupt kein Problem und du hast duir zu viele Gedanken gemacht.
Worüber du dir auf jeden Fall Gedanken machen solltest, ist die Repräsentation von Geraden. f(x)=mx+c zum Beispiel gibt größere Probleme bei steilen Geraden, der Ansatz (x,f(x))=(v,w)+r*(a,b) ist da vielleicht passender, da kannst du auch schnell sehen, ob ein Schnittpunkt innerhalb deiner Strecke liegt.

[Codewalker]

Nun, es sind derzeit 30x30 = 900 Sechsecke. Aufruf bei jeder Bewegung einer Figur (Sichtlinienberechnung), also sagen wir mal im Schnitt alle paar Sekunden einmal zum aktualisieren des Fog of War.
Ich muss da erstmal drüber schlafen - hilft meistens :coder2:

[Nikolas]

Fog of War? Das heisst doch Nebel des Krieges, oder? Also nicht: exakte Grenze des Krieges.
Bei dieser Aufgabe könntest du einfach nur den BoundingCircle benutzen und gut ist.

Vorschlag: Nimm dir den Mittelpunkt einer der Strecken, die das Sechseck umschließen und rechne den Abstand zur Mitte aus. Wenn der Abstand deiner Gerade zum Mittelpunkt kleiner ist, wird das Sechseck getroffen, ansonsten nicht.

In den meisten Fällen solltest du damit sehr gute Ergebnisse erzielen und einen minimalen Programmieraufwand haben.