Viele Programmierer, die sich mit Geometrie beschaeftigen (haeufig Spieleprogrammierer) treffen auf das Problem: Line-Line-Intersection. Auch ich bin vor kurzem darauf gestossen und da ist mir aufgefallen, dass es nicht so einfach ist wie ich zuvor dachte. Nachfolgend werde ich meinen Loesungsweg mathematisch erlaeutern und dann mit C++ Quellcode anreichern.
Mathematische Herleitung
Gegeben sind zwei Strecken, die durch jeweils zwei Punkte P, Q definiert sind:
P1, Q1, P2, Q2
Eine Gerade durch die Punkte P und Q kann mit folgender Formel definiert werden:
g: A * x + B * y = C
Also habe ich zwei Geraden:
g1: A1 * x + B1 * y = C1
g2: A1 * x + B2 * y = C2
Bei dieser Form sind A, B, C wie folgt definiert:
A = Qy – Py
B = Px – Qx
C = A * Px + B * Qy
Um einen Schnittpunkt zu errechnen setze ich beide Geradengleichungen gleich. Zuvor multipliziere ich aber beide Gleichungen mit B1 bzw. B2, was beim Loesen spaeter von Vorteil ist.
A1 * B2 * x + B1 * B2 * y = C1 * B2
A2 * B1 * x + B1 * B2 * y = C2 * B1
Nun subtrahiere ich die zweite Zeile von der ersten und forme noch etwas um:
A1 * B2 * x – A2 * B1 * x + B1 * B2 * y – B1 * B2 * y = C1 * B2 – C2 * B1
=> A1 * B2 * x – A2 * B1 * x = C1 * B2 – C2 * B1
=> (A1 * B2 – A2 * B1) * x = C1 * B2 – C2 * B1 | / (A1 * B2 – A2 * B1)
=> x = (C1 * B2 – C2 * B1) / (A1 * B2 – A2 * B1)
Wenn kein Schnittpunkt existiert, ist der Nenner 0, also muss eigentlich nur ueberprueft werden, ob A1 * B2 – A2 * B1 = 0 erfuellt ist.
Spass mit C++
Nachdem ich die mathematische Seite auf ein Blatt Papier gekritzelt habe, baute ich daraus eine nette Funktion, mit den Argumenten A1, B1, A2, B2 des Typs Point[1]. Der Rueckgabetyp ist bool, da wir ja nur wissen wollen, ob die Strecken sich schneiden oder nicht.
bool Intersection::LineLine(Point A1, Point B1, Point A2, Point B2)
Jetzt folgen die Definitionen von A, B, C fuer die beiden Strecken A1B1 und A2B2:
double A_1 = B1.y - A1.y;
double B_1 = A1.x - B1.x;
double C_1 = A_1 * A1.x + B_1 * A1.y;
double A_2 = B2.y - A2.y;
double B_2 = A2.x - B2.x;
double C_2 = A_2 * A2.x + B_2 * A2.y;
Und dann lasse ich den Nenner (siehe oben) berechnen:
double determinator = A_1 * B_2 - A_2 * B_1;
Nun lasse ich den Nenner ueberpruefen:
Wenn der Nenner 0 ist, heisst das nicht, dass es keinen Schnittpunkt gibt, sondern dass es auch unendlich viele Schnittpunkte geben kann (die Geraden sind identisch). Also muss ich ueberpruefen, ob die Geraden parallel sind. Das mache ich, indem ich einfach die bekannten Punkte einsetze:
if (A_1 * A2.x + B_1 * A2.y == C_1 && A_1 * B2.x + B_1 * B2.y == C_1)
Wenn die Geraden gleich sind, heisst das noch lange nicht, dass die Strecken sich auch schneiden. Also muss das auch noch ueberprueft werden. Das mache ich, indem ich pruefe, ob die Laengen der Strecken laenger sind, als die Abstaende der Punkte A1, A2 und B1,B2:
Vector A1B1 = ((Vector) (B1 - A1));
Vector A2B2 = ((Vector) (B2 - A2));
Vector A1A2 = ((Vector) (A2 - A1));
Vector B1B2 = ((Vector) (B2 - B1));
if (A1A2.Length2() < A1B1.Length2() || B1B2.Length2() < A2B2.Length2())
{
return true;
}Ich verwende Length2(), also das Quadrat der Laenge, da Length ueber den Satz des Pythagoras die Laenge des Vektors berechnet. Length2 zieht im Gegensatz zu Length nicht die Wurzel, ist also schneller.
So jetzt nochmal zu dem Fall, dass ein Schnittpunkt gefunden wird: Er muss sich auf den Strecken befinden. Liegt er ausserhalb der Strecke, so ist er irrelevant:
Point S;
S.x = (B_2 * C_1 - B_1 * C_2) / determinator;
S.y = (A_1 * C_2 - A_2 * C_1) / determinator;
if (min(A1.x, B1.x) <= S.x && S.x <= max(A1.x, B1.x)
&& min(A1.y, B1.y) <= S.y && S.y <= max(A1.y, B1.y)
&& min(A2.x, B2.x) <= S.x && S.x <= max(A2.x, B2.x)
&& min(A2.y, B2.y) <= S.y && S.y <= max(A2.y, B2.y))
{
return true;
}Den zusammengesetzten Code gibt es hier: Intersection.cpp, Intersection.h.
[1] Die verwendeten Klassen Vector und Point habe ich schon vorher mal gepostet. Hier gehts zu den Klassen: Vektoren fuer C++ Programmierer
