Moin,
ich bin auf der Suche nach einer Formel um herauszufinden ob eine Linie ein Polygon schneidet.
Paul
Bitte etwas genauer
Hossa 
Dafür gibt es viele unterschiedliche Algorithmen, alle unterschiedlich schnell und für andere Sonderfälle. Daher meine Bitte, dass du deine Anfrage etwas konkretisierst.
a) in 2 oder 3 Dimensionen?
b) wenn 3 Dimensionen, liegt das Polygon in einer Ebene?
c) Verläuft die Linie parallel zu einer Koordinatenachse?
d) Geht es um das Füllen eines Polygons oder um eine „hit detection“?
Je mehr weitere Infos du über dein Problem bereitstellen, desto besser…
Viele Grüße
Hase
Hallo und vielen Dank für die Hilfe!
a) 2 Dimensionen
b) siehe a)
c) nein (nicht zwangsweise)
d) möchte nur wissen ob die Linie das Polygon schneidet (true oder false)
Danke,
Paul
Lösung
Hossa Paul
Um herauszufinden, ob eine Gerade ein Polygon schneidet, kannst du z.B. prüfen, ob die Gerade irgendeine Kante des Polygons schneidet.
Im Folgenden seien:
-
P(p1,p2) und Q(q1,q2) zwei verschiedene Punkte auf der Geraden
-
A(a1,a2) und B(b1,b2) die beiden Endpunkte der Polygon-Kante
Dann lautet die Geradengleichung für die Gerade g:
g: \vec x=\vec p+\lambda\left(\vec q-\vec p\right)
und die Geradengleichung für die Kante k:
k: \vec x=\vec a+\mu\left(\vec b-\vec a\right)\quad;\quad 0\le\mu\le1
Wichtig ist hierbei, dass der Parameter mu die Kante begrenzt, indem er zwischen 0 und 1 liegen muss.
Wenn g und k nicht parallel sind, dann schneiden sie sich in genau einem Punkt x. Für diesen gilt die Bedinung:
\vec p+\lambda\left(\vec q-\vec p\right)=\vec a+\mu\left(\vec b-\vec a\right)
Wenn man nun die Koordinaten der Punkte einsetzt, kann man ein Gleichungssystem aufstellen und die Werte für lambda und mu berechnen. Interessant ist hier der Wert für mu, es ergibt sich:
\mu=\frac{\left(p_1-a_1\right)\left(a_2-p_2\right)-\left(p_2-a_2\right)\left(q_1-p_1\right)}{\left(b_1-a_1\right)\left(q_2-p_2\right)-\left(b_2-a_2\right)\left(q_1-p_1\right)}
Liegt dieser Wert zwischen 0 und 1, so schneidet die Gerade g die Kante k. Liegt der Wert bei 0, so berührt die Gerade g die Kante k an einem Endpunkt. Liegt der Wert bei 1, so berührt die Gerade g die Kante k am anderen Endpunkt.
Du musst also nur für jede Kante des Polygons den Wert mu berechnen, so lange, bis er zwischen 0 und 1 liegt. Passiert dies bei keiner Kante, schneidet die Gerade auch das Polygon nicht.
Sonderfall:
Wenn die Gerade g und die Kante k parallel zueinander liegen, haben sie die gleiche Steigung, es gilt also:
\frac{q_2-p_2}{q_1-p_1}=\frac{b_2-a_2}{b_1-a_1}
Oder mathematisich etwas umgeformt:
\left(b_1-a_1\right)\left(q_2-p_2\right)=\left(b_2-a_2\right)\left(q_1-p_1\right)
bzw.
\left(b_1-a_1\right)\left(q_2-p_2\right)-\left(b_2-a_2\right)\left(q_1-p_1\right)=0
Mit anderen Worten, wenn g und k parallel liegen, ist der Nenner in der Formel von mu gleich 0. Streng genommen schneidet die Gerade g in diesem Fall die Kante k nicht, denn entweder haben g und k keinen Punkt gemeinsam, oder sie liegen genau übereinander (was ja kein „Schneiden“ ist).
Daher solltest du den Nenner immer zuerst berechnen. Ist dieser gleich 0, kannst du die nächste Kante testen und brauchst mu nicht weiter auszurechnen. Ist der Nenner jedoch ungleich 0, kannst du mu berechnen und auf ein Ergebnis zwischen 0 und 1 hoffen
Viele Grüße
Hase