Schnittpunkt zweier Geraden mit einem Programm berechnen

Einleitung: Warum machen wir das Überhaupt? und warum Hausaufgaben doch irgendwie wichtig sind… ;D

Eine der wichtigsten Fragen überhaupt ist bei diesem, wie bei jedem anderen Thema: Warum wollen wir überhaupt wissen, wie der Schnittpunkt zweier Geraden sich programmatisch berechnen lässt? Ein guter Grund wäre, weil es uns interessiert ob überhaupt und wenn ja, wie das möglich ist. Warum ich darauf kam? Ich bin gerade dabei ein Programm für Roboter zur Wegfindung auf einer zwei dimensionalen Karte zu schreiben. Dafür muss der Roboter unter anderem wissen, ob er das Ziel sehen kann oder nicht. Die Hindernisse sind auf der Karte als Polygone (Vielecke) verzeichnet. Die Position des Roboters und die Position des Ziels sind ebenfalls auf der Karte verzeichnet. Schneidet die direkte Strecke von Roboter zum Ziel keine Kante eines Polygons, so kann der Roboter das Ziel sehen und gegebenenfalls auf diesem Pfad zum Ziel laufen.

Ein anderer Grund ein Programm zur Schnittpunktberechnung zu schreiben wäre, weil man keine Lust hat seine Hausaufgaben selbst zu machen und seine Hausaufgaben lieber dem Computer überlässt (ihr Schlingel! xD) Bedenkt, wenn ihr eure Matheaufgaben nicht selbst löst, ist das so, wie wenn ihr eigentlich gerne sportlich wärt, allerdings viel zu selten tatsächlich Sport treibt. Ihr werdet eurem Ziel, in Mathe besser zu werden, einfach nicht näher kommen. Ein offenes Geheimnis ist, dass unser Körper und unser Geist trainiert werden muss um eine Fertigkeit zu erlernen. Manchen fällt das leichter als anderen. Falls du einer derjenigen bist, denen Mathe schwer fällt: Die allermeisten, denen Mathe leicht fällt, sind tatsächlich nicht schlauer als du. Garantiert! Die meisten denen Mathe leicht fällt haben entweder mehr Disziplin oder einfach Spaß an Mathe und beschäftigen sich deshalb mehr mit Mathe als du ;D Außerdem hilft eine hohe Motivation aus biologischen Gründen enorm, um sich auf ein Thema einzulassen oder sich eine Fähigkeit anzueignen. Dein Hirn ist so gebaut, dass wenn dich etwas interessiert, du es dir leicht merken kannst. Falls es sich um ein schwierig zu lösendes Problem handelt, das du unbedingt lösen willst, wird dein Gehirn auch während du schläfst oder du mit anderen Dingen beschäftigt bist in deinem Unterbewusstsein weiter an der Problemlösung arbeiten. oO(Ich denke darüber sollte ich demnächst einen Blogeintrag schreiben. Könnt euch schonmal drauf freuen <(^.^)> )

Hauptteil: Mathe, 2D Vektoren, Geraden und Gleichungssysteme

Im Folgenden erarbeiten wir gemeinsam eine Formel zur Berechnung des Schnittpunkts zweier Geraden. Weil für meinen Anwendungsfall einer Landkarte, auf der die Geraden verlaufen, zwei Dimensionen ausreichen, verwende ich zweidimensionale Vektoren und erhalte entsprechend eine Formel, die für zweidimensionale Geraden funktioniert. Nachdem ihr den Artikel gelesen und verstanden habt, könnt ihr bestimmt selbst ein Verfahren für drei Dimensionen herleiten. Wenn ihr daran interessiert seid und nicht weiter kommt, schreibt mir ein Kommentar unter den Blogeintrag. Ich werde mich gerne mit euch zusammen an die Lösung des Schnittpunktproblems im dreidimensionalen Raum setzen.

Zwei Geraden im zweidimensionalen Raum lassen sich mit Hilfe von Vektoren mit folgenden Geradengleichungen beschreiben:
TODO: Einführung in Vektorgeometrie und Geradengleichungen
\(
g: \vec{x} = \vec{u} + t \vec{v} \\
h: \vec{x} = \vec{a} + r \vec{b}
\)

Wie helfen uns diese Geradengleichungen den Schnittpunkt zu bestimmen? Mit Hilfe der Geradengleichung von \(g\) können wir jeden beliebigen Punkt auf der Geraden mittels des variablen Faktors \(t\) erreichen. Also können wir auch den Schnittpunkt der beiden Geraden erreichen. Entsprechendes gilt für die Gerade \(h\): mit dem variablen Faktor r können wir jeden Punkt der Geraden h erreichen. Der Trick bei der Sache ist: der Schnittpunkt der Geraden \(g\) und \(h\) liegt auf beiden Geraden! Vorrausgesetzt \(g\) und \(h\) schneiden sich in einem Punkt, muss es also ein \(t\) und ein \(r\) geben, sodass die Geradengleichungen \(g\) und \(h\) bei Berechnung der jeweiligen rechten Seite auf dasselbe Ergebnis führt. Wenn die Geradengleichungen dasselbe Ergebnis produzieren, dann liegt der resultierende Punkt auf beiden Geraden. Der resultierende Punkt ist also unser gesuchter Schnittpunkt.

Wie finden wir solche \(t\) und \(r\), die uns zum Schnittpunkt führen? Als Bedingungen haben wir die genannten Geradengleichungen, die erfüllt sein müssen und wir wissen, dass diese Gleichungen gleich sein müssen, wenn \(t\) und \(r\) so gewählt werden, dass wir den Schnittpunkt erhalten. Diese Bedingungen halten wir mathematisch logisch fest, indem wir die Gleichungen gleich setzen. Wenn wir es schaffen diese neue Gleichung zu lösen, finden wir so solche \(t\) und \(r\), die bei Einsetzen derselben in die ursprünglichen Gleichungen zum selben Ergebnis, unserem gesuchten Schnittpunkt führen.
\(
\vec{u} + t \vec{v} = \vec{a} + r \vec{b}
\)

Wir werden keine Zahlen zum Lösen der Gleichung verwenden, da unser Programm später generisch den Schnittpunkt zweier Geraden bestimmen können soll, die der Nutzer dem Programm vorgibt. Dazu geben wir dem Nutzer programmatisch die Möglichkeit die Stütz- und Richtungsvektoren der zwei Geraden einzugeben. Daher ist es für uns sinnvoll, wenn wir uns die Vektoren \(\vec{u}\), \(\vec{v}\), \(\vec{a}\), und \(\vec{b}\) so vorstellen, als seien uns die Zahlenwerte der Koordinaten bekannt. Ganz so als stünden statt Buchstaben tatsächlich Zahlen, mit denen wir wie gewohnt rechnen können. Also haben wir in obiger Gleichung zwei Unbekannte: \(t\) und \(r\).

Eine Gleichung zwei Unbekannte? Leider nein… Tatsächlich verbirgt sich hinter der obigen Gleichung ein Gleichungssystem mit zwei Gleichungen. Eine Gleichung jeweils für die x- und eine für die y-Koordinate.
\(
u_x + t v_x = a_x + r b_x \\
u_y + t v_y = a_y + r b_y
\)

Kannst du das Gleichungssystem nach \(t\) und \(r\) selbst lösen? Du kannst gerne weiterlesen und einen Versuch starten das Rätsel selbst zu lösen, sobald du einen Einstieg gefunden hast.

Wir fangen damit an, die Gleichung für die x-Koordinate nach \(r\) aufzulösen.
\(
\begin{array}{rcll}
u_x + t v_x &=& a_x + r b_x &| -a_x \\
u_x + t v_x – a_x &=& r b_x &| \cdot \frac{1}{b_x} \\
(u_x + t v_x – a_x) \cdot \frac{1}{b_x} &=& r \\
r &=& (u_x + t v_x – a_x) \cdot \frac{1}{b_x}
\end{array}
\)

Als nächstes machen wir dasselbe für die andere Gleichung. Im wesentlichen könnt ihr die Auflösung nach \(r\) abschreiben, da die Gleichung für die y-Koordinate der der x-Koordinate entspricht.
\(
\begin{array}{rcll}
u_y + t v_y &=& a_y + r b_y &| -a_y \\
u_y + t v_y – a_y &=& r b_y &| \cdot \frac{1}{b_y} \\
(u_y + t v_y – a_y) \cdot \frac{1}{b_y} &=& r \\
r &=& (u_y + t v_y – a_y) \cdot \frac{1}{b_y}
\end{array}
\)

Jetzt haben wir zwei neue Gleichungen, die wiederum auf dasselbe Ergebnis für \(r\) kommen müssen. Also können wir diese beiden Gleichungen über \(r\) gleich setzen.
\(
\begin{array}{rcl}
r &=& (u_x + t v_x – a_x) \cdot \frac{1}{b_x} \\
r &=& (u_y + t v_y – a_y) \cdot \frac{1}{b_y} \\
(u_x + t v_x – a_x) \cdot \frac{1}{b_x} &=& (u_y + t v_y – a_y) \cdot \frac{1}{b_y} \\
\end{array}
\)

Damit erhalten wir eine Gleichung, die nur noch eine Unbekannte, nämlich \(t\) besitzt. Wie hilft uns das weiter? Wenn wir \(t\) in Abhängigkeit der anderen Variablen bestimmen, haben wir eine Formel, mit der wir ein passendes \(t\) berechnen können, das uns zum Schnittpunkt führt. Um nach \(t\) aufzulösen, behandeln wir alle anderen Variablen als konstant, wie bisher auch.
\(
\begin{array}{rcll}
(u_x + t v_x – a_x) \cdot \frac{1}{b_x} &=& (u_y + t v_y – a_y) \cdot \frac{1}{b_y} &| \cdot b_x \cdot b_y \\
(u_x + t v_x – a_x) \cdot b_y &=& (u_y + t v_y – a_y) \cdot b_x \\
u_x b_y + t v_x b_y – a_x b_y &=& u_y b_x + t v_y b_x – a_y b_x
&| -t v_y b_x – u_x b_y + a_x b_y \\
t v_x b_y – t v_y b_x &=& u_y b_x – a_y b_x – u_x b_y + a_x b_y \\
t \cdot (v_x b_y – v_y b_x) &=& u_y b_x – a_y b_x – u_x b_y + a_x b_y &| \cdot \frac{1}{v_x b_y – v_y b_x} \\
t &=& \frac{u_y b_x – a_y b_x – u_x b_y + a_x b_y}{v_x b_y – v_y b_x} \\
t &=& \frac{b_x (u_y – a_y) + b_y (-u_x + a_x)}{v_x b_y – v_y b_x} \\
t &=& \frac{b_x (u_y – a_y) + b_y (a_x – u_x)}{v_x b_y – v_y b_x} \\
\end{array}
\)

Das so gefundene \(t\) setzen wir in die Geradengleichung \(g\) ein, um so den Schnittpunkt zu berechnen. Am besten macht ihr das in zwei Schritten.

Wenn man die gesamte Berechnung unbedingt in einer Formel haben möchte, sieht das so aus:
\(
\begin{array}{rcll}
g: \vec{x} &=& \vec{u} + t \vec{v} \\
t &=& \frac{b_x (u_y – a_y) + b_y (a_x – u_x)}{v_x b_y – v_y b_x} \\
g: \vec{x} &=& \vec{u} + \frac{b_x (u_y – a_y) + b_y (a_x – u_x)}{v_x b_y – v_y b_x} \cdot \vec{v} \\
\end{array}
\)

Wie gießen wir diese Formel in ein Programm, sodass unser Computer für uns unsere Hausaufgaben erledigt? Das findet ihr bestimmt selbst heraus, sofern ihr eine Programmiersprache gelernt habt. Alternativ könnt ihr euch gerne mein Beispielprogramm in C++ unten anschauen. Ihr dürft das Programm gerne kopieren, compilieren und ausprobieren. (Natürlich macht ihr eure Hausaufgaben selbst, ihr Schlingel ;D ihr könnt das Programm natürlich nutzen um eure Ergebnisse zu prüfen. Oder ihr nutzt das Programm, um euch selbst Aufgaben zu geben um zu trainieren. Das Programm sagt euch anschließend ob ihr ein Fehler in eurer Berechnung habt.)

#include <iostream>
 
struct Vector {
  double x;
  double y;
};
 
Vector berechneSchnittpunkt(Vector const& u, Vector const& v,
                            Vector const& a, Vector const& b) {
  double const t = (b.x*(u.y - a.y) + b.y*(a.x - u.x))
    / (v.x*b.y - v.y*b.x);
 
  // Ausgabe nur zu Testzwecken ;D
  using namespace std;
  cout << "t = " << t << endl;
 
  Vector schnittpunkt;
  schnittpunkt.x = u.x + t*v.x;
  schnittpunkt.y = u.y + t*v.y;
  return schnittpunkt;
}
 
int main(int argc, const char * argv[]) {
  using namespace std;
  Vector u, v, a, b;
 
  cout << "u.x = ";
  cin >> u.x;
  cout << "u.y = ";
  cin >> u.y;
  cout << endl;
 
  cout << "v.x = ";
  cin >> v.x;
  cout << "v.y = ";
  cin >> v.y;
  cout << endl;
 
  cout << "a.x = ";
  cin >> a.x;
  cout << "a.y = ";
  cin >> a.y;
  cout << endl;
 
  cout << "b.x = ";
  cin >> b.x;
  cout << "b.y = ";
  cin >> b.y;
  cout << endl;
 
  Vector schnittpunkt = berechneSchnittpunkt(u, v, a, b);
 
  cout << "Schnittpunkt:"
    << " ( " << schnittpunkt.x << " | " << schnittpunkt.y << " ) "
    << endl;
 
  return 0;
}

Was aber passiert, wenn sich die Geraden gar nicht schneiden sondern parallel liegen?

Dann wird der Nenner \(v_x b_y – v_y b_x\) in der Formel gleich \(0\)! Was? Das glaubt ihr nicht? Und warum überhaupt sollte das so sein? Ich werde es euch beweisen, dass es so ist und ihr werdet begreifen, warum das so ist =)

Beginnen wir mit einer einfacheren Frage: Wann liegen zwei Geraden parallel? Ja, genau dann, wenn ihre Richtungsvektoren in die gleiche oder genau entgegengesetzte Richtung zeigen. Wenn Vektoren in die gleiche Richtung zeigen, nennt man diese Vektoren auch linear abhängig. Na, klingelts? Wenn nicht, nicht schlimm. Lineare Abhängigkeit zweier Vektoren heißt, dass der eine Vektor sich aus dem anderen Vektor ergibt, wenn man den einen mit einem bestimmten konstanten Faktor multipliziert. Also wenn man die Koordinaten des einen Vektors mit einer bestimmten Zahl mal nimmt, kommen die Koordinaten des anderen heraus. Algebraisch können wir das folgendermaßen beschreiben:
\(
\vec{b} = \vec{v} \cdot k
\)

Daraus resultiert für die Koordinaten folgendes Gleichungssystem:
\(
b_x = v_x \cdot k \\
b_y = v_y \cdot k
\)

Wie ihr seht, haben wir für ein Gleichungssystem mit zwei Gleichungen nur eine tatsächliche Unbekannte, nämlich \(k\). Die anderen Variablen sind uns wegen der Geradengleichungen vorgegeben. Das heißt es gibt nicht immer eine Lösung für das Gleichungssystem. Das Gleichungssystem hat nur dann eine Lösung für \(k\), wenn \(\vec{v}\) und \(\vec{b}\) in die gleiche oder genau entgegengesetzte Richtung zeigen.

Natürlich könnten wir eine der beiden Gleichungen im konkreten Fall lösen und schauen ob die jeweils andere Gleichung mit dem Ergebnis eine wahre Aussage liefert um zu prüfen ob unsere Richtungsvektoren linear abhängig sind. Sie sind genau dann linear abhängig, wenn beide Gleichungen bei Eingabe desselben \(k\)s eine wahre Aussage liefern. Andernfalls sind sie nicht linear abhängig.

Wie hängt dies mit der Frage zusammen, warum der Nenner \(v_x b_y – v_y b_x\) gleich null wird, wenn die Geraden parallel liegen? Wenn die Richtungsvektoren \(\vec{v}\) und \(\vec{b}\) der Geraden \(g\) und \(h\) linear abhängig sind, dann sind die beiden Geraden parallel zueinander.
\(
\begin{array}{rcll}
\vec{v} &=& s \vec{b} \\
\hline
v_x &=& s b_x \\
v_y &=& s b_y \\
\hline
v_y &=& s b_y &| \cdot \frac{1}{b_y} \\
\frac{v_y}{b_y} &=& s \\
\hline
v_x &=& s b_x &| s = \frac{v_y}{b_y} \\
v_x &=& \frac{v_y}{b_y} b_x &| \cdot b_y \\
v_x b_y &=& v_y b_x &| – v_y b_x \\
v_x b_y – v_y b_x &=& 0 \\
\end{array}
\)

Was haben wir durch die ganze Rechnerei erreicht? Durch Äquivalenzumformung haben wir gezeigt, dass genau dann wenn \(\vec{v} = s \vec{b}\) gilt, gilt auch \(v_x b_y – v_y b_x = 0\). Also sind die Richtungsvektoren \(\vec{v}\) und \(\vec{b}\) genau dann linear abhängig, wenn der Nenner in unserer Formel gleich \(0\) ist. Deshalb sind sind die Geraden \(g\) und \(h\) genau dann parallel, wenn der Nenner \(v_x b_y – v_y b_x\) gleich \(0\) ist.

Wir haben damit ganz nebenbei eine neue Formel gefunden, mit deren Hilfe wir viel einfacher lineare Abhängigkeit zwischen zwei Vektoren bestimmen können. Wir haben bewiesen, dass wenn für zwei beliebge Vektoren \(\vec{d}\) und \(\vec{e}\) gilt: \(d_x e_y – d_y e_x = 0\), dann sind die Vektoren \(\vec{d}\) und \(\vec{e}\) linear abhängig.

Was passiert, wenn die Geraden aufeinander liegen und somit unendlich viele ‚Schnittpunkte‘ haben?

Liegen zwei Geraden aufeinander, werden diese auch als pseudo-parallel zueinander bezeichnet. Sie teilen mit echt parallel liegenden Geraden die Eigenschaft, dass deren Richtungsvektoren linear abhängig sind. Der Unterschied zu echt parallel liegenden Geraden ist, dass bei pseudo-parallelen Geraden jeder Punkt der einen Gerade auch auf der anderen Geraden liegt. Bei echt parallelen Geraden liegt dagegen kein Punkt der einen Gerade auf der anderen.

Wie stellen wir fest ob zwei Geraden aufeinander liegen? Könnt ihr euch diese Frage mit den Informationen aus dem ersten Absatz selbst beantworten?

Wir wissen, dass bei aufeinander liegenden Geraden die jeweiligen Richtungsvektoren linear abhängig sein müssen. Dafür prüfen wir die Richtungsvektoren auf lineare Abhängigkeit indem wir entweder den Linearfaktor um den sich die Richtungsvektoren unterscheiden mit dem beschriebenen Gleichungssystem bestimmen. Oder wir nutzen die hergeleitete Gleichung \(u_x v_y – u_y v_x = 0\), wobei wir für \(\vec{u}\) und \(\vec{v}\) die jeweiligen Richtungsvektoren der Geradengleichungen einsetzen.

Stellen wir fest, dass die Richtungsvektoren linear abhängig sind, müssen wir prüfen ob ein Punkt der einen Geraden auch ein Punkt auf der anderen Geraden ist. Da Geraden bekanntlich keine Krümmung aufweisen und die Geraden in diesem Fall parallel liegen, muss es so sein, dass die Geraden pseudo-parallel zueinander liegen. Das heißt alle Punkte der einen, liegen auch auf der anderen Geraden.

Wir benötigen also einen Punkt, der auf einer der Geraden liegt, damit wir diesen auf der anderen Geraden testen können. Die Stützpunkte liegen immer auf den jeweiligen Geraden. So können wir für \(g\) den Stützvektor \(u\) wählen, da der Ortsvektor \(u\) auf jeden Fall auf einen Punkt der Geraden \(g\) zeigt.
\(
g: \vec{x} = \vec{u} + t \vec{v} \\
h: \vec{x} = \vec{a} + r \vec{b}
\)

Um zu testen ob \(\vec{u}\) auf einen Punkt der Geraden \(h\) zeigt, verwenden wir die Geradengleichung. Wir setzen für \(\vec{x}\) den Vektor \(\vec{u}\) ein. Es folgt wieder ein Gleichungssystem mit einer Unbekannten \(r\) und zwei Gleichungen. Lösen wir eine der beiden Gleichungen nach \(r\) auf, müssen wir anschließend \(r\) in die andere Gleichung einsetzen um zu testen ob unser Punkt tatsächlich auf der Geraden liegt oder nicht. Ergibt die andere Gleichung nach Einsetzung des gefundenen \(r\) eine wahre Aussage, so liegt der gewählte Punkt auf der Geraden. Andernfalls liegt der Punkt nicht auf der Geraden.
\(
\begin{array}{rcll}
\vec{u} &=& \vec{a} + r \vec{b} \\
\hline
u_x &=& a_x + r b_x \\
u_y &=& a_y + r b_y \\
\hline
u_x &=& a_x + r b_x &| -a_x \\
u_x – a_x &=& r b_x &| \cdot \frac{1}{b_x} \\
\frac{u_x – a_x}{b_x} &=& r \\
r &=& \frac{u_x – a_x}{b_x} \\
\hline
u_y &=& a_y + \frac{u_x – a_x}{b_x} \cdot b_y \\
\end{array}
\)

Wenn also \(\vec{v}\) und \(\vec{b}\) linear abhängig sind und \(u_y = a_y + \frac{u_x – a_x}{b_x} \cdot b_y\) eine wahre Aussage ergibt, dann sind \(g\) und \(h\) pseudo-parallel zueinander, beziehungsweise liegen \(g\) und \(h\) übereinander.

Ist unser Programm unter Rücksichtnahme unserer neuen Erkenntnisse korrekt?

Ich würde sagen jain ;D Also wie jetzt? Nunja, zumindest in C++ ist eine Division durch 0 nicht verboten, wenn es sich dabei um float oder double Werte handelt. Bei einer Division durch 0, wird das Ergebnis schlicht NaN, +inf oder -inf. NaN steht für Not_a_Number. Egal wie man den Wert NaN mit anderen Zahlen arithmetisch verknüpft (also malnimmt, plus oder minus rechnet und so weiter), es kommt immer NaN dabei heraus. Die Werte +inf und -inf stehen, na wer hätte es gedacht? für +Unendlich und -Unendlich. Entsprechend liefert uns die Funktion berechneSchnittpunkt([...]) einen Vektor mit den Werten NaN, +inf oder -inf. Leider wissen wir mit diesem Ergebnis nur, dass die Geraden parallel zueinander liegen. Ob sie aufeinander also pseudo-parallel oder echt parallel zueinander liegen, können wir nach den bisherigen Ergebnissen nicht entscheiden. Dafür bräuchten wir den Punkttest, wie oben beschrieben. Kann man aus diesem Ergebnis nicht doch ablesen, ob die Geraden pseudo-parallel oder echt parallel zueinander liegen? Ohja, das geht! Wie genau und warum, erkläre ich euch im nächsten Artikel.

Unser Programm ist also nicht tatsächlich falsch. Falls wir uns jedoch im weiteren Programmverlauf darauf verlassen würden, dass es uns die Funktion berechneSchnittpunkt([...]) immer einen echten Schnittpunkt liefert, werden wir in wenigen Fällen feststellen, dass unser Programm seltsame Dinge produziert. Das passiert genau dann, wenn die Geraden parallel zueinander liegen, was wahrscheinlich in den allermeisten Fällen nicht der Fall sein wird, aber zu Programmabstürzen oder unter Umständen Schlimmerem führen kann. Solche Fehler sind oft schwer zu finden, falls man nicht vorher daran denkt 😉

Deswegen gibt es hier ein Update für unser Programm, das die besprochenen Sonderfälle berücksichtigt:

#include <iostream>
 
struct Vector {
  double x;
  double y;
};
 
bool sindLinearAbhaengig(Vector const& u, Vector const& v) {
  double const erlaubterFehler = 0.000001;
  double const test = u.x*v.y - u.y*v.x;
 
  return (0 - erlaubterFehler) <= test && (0 + erlaubterFehler) >= test;
}
 
bool punktLiegtAufGeraden(Vector punkt, Vector stuetzVctr, Vector richtungsVctr) {
  double const erlaubterFehler = 0.000001;
  double const rechteSeite = stuetzVctr.y
    + (punkt.x - stuetzVctr.x) / richtungsVctr.x
    * richtungsVctr.y;
  return (punkt.y - erlaubterFehler) <= rechteSeite
    && (punkt.y + erlaubterFehler) >= rechteSeite;
}
 
Vector berechneSchnittpunkt(Vector const& u, Vector const& v,
                            Vector const& a, Vector const& b) {
  double const t = (b.x*(u.y - a.y) + b.y*(a.x - u.x))
    / (v.x*b.y - v.y*b.x);
 
  // Ausgabe nur zu Testzwecken ;D
  using namespace std;
  cout << "t = " << t << endl;
 
  Vector schnittpunkt;
  schnittpunkt.x = u.x + t*v.x;
  schnittpunkt.y = u.y + t*v.y;
  return schnittpunkt;
}
 
int main(int argc, const char * argv[]) {
  using namespace std;
  Vector u, v, a, b;
 
  cout << "u.x = ";
  cin >> u.x;
  cout << "u.y = ";
  cin >> u.y;
  cout << endl;
 
  cout << "v.x = ";
  cin >> v.x;
  cout << "v.y = ";
  cin >> v.y;
  cout << endl;
 
  cout << "a.x = ";
  cin >> a.x;
  cout << "a.y = ";
  cin >> a.y;
  cout << endl;
 
  cout << "b.x = ";
  cin >> b.x;
  cout << "b.y = ";
  cin >> b.y;
  cout << endl;
 
  if (sindLinearAbhaengig(v, b)) {
    if(punktLiegtAufGeraden(u, a, b)) {
      cout << "Geraden liegen aufeinander bzw. sind pseudo-parallel zueinander." << endl;
    } else {
      cout << "Geraden liegen echt parallel zueinander" << endl;
    }
  } else {
    Vector schnittpunkt = berechneSchnittpunkt(u, v, a, b);
    cout << "Schnittpunkt:"
    << " ( " << schnittpunkt.x << " | " << schnittpunkt.y << " ) "
    << endl;
  }
 
  return 0;
}

Wegen der Numerischen Auslöschung müssen wir darauf achten, dass wir Gleitkommazahlen nicht mit == vergleichen. Stattdessen bestimmen wir die Gleichheit von Werten mit einer Fehlertoleranz von +0.000001 und -0.000001 um zu verhindern, dass durch die Numerische Auslöschung mathematisch eigentlich gleiche Werte als ungleich gewertet werden. Natürlich werden dadurch Geraden, die tatsächlich minimal verschoben echt parallel zueinander liegen auch als aufeinander liegend also als pseudo parallel gewertet. In der Praxis bleibt uns nicht wirklich etwas anderes übrig, weil der Computer nur endlich genaue Zahlen darstellen kann. In der Praxis reicht diese Genauigkeit meistens völlig aus.

Da wir ausschließlich Addition, Subtraktion, Multiplikation und Division verwenden, gäbe es tatsächlich die Möglichkeit Rationale Zahlenmodelle programmatisch zu verwenden. Damit würden wir das Problem der Numerischen Auslöschung umgehen, da wir dann ausschließlich mit ganzen Zahlen rechnen. Die Implementierung ist allerdings aufwändig und komplex. Deshalb würde das den Rahmen dieses Artikels deutlich sprengen. Außerdem würde die Laufzeit bei Berechnung des Schnittpunkts vieler Geraden in die Knie gehen. Wenn ihr Lust habt, könnt ihr euch gern selbst daran versuchen <(^_^)>

Na alles verstanden? Wenn nicht, schreibt mir einen Kommentar und wir klären das gemeinsam =)