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 =)

OpenGL-SDL2-Window-Skia-Wrapper

Achtung! dieser Post ist Work in Progress ;D

Eine Instanz der Window Klasse ist ein Wrapper um ein SDL Fenster mit OpenGL-Kontext und Schnittstelle für die Skia Grafikbibliothek. Im Wesentlichen besteht die öffentliche Schnittstelle für Window Objekte aus nur drei Methoden.

class Window {
public:
  Window(std::string title, int x, int y, int width, int height);
  SkCanvas* getCurrentCanvas();
  void display();
};

Nach dem Konstruieren eines Window objekts, erscheint unserem Nutzer ein betriebssystemnatives Fenster. Mit getCurrentCanvas() erhalten wir das SkCanvas-Objekt auf das wir die Geometrie zeichnen, welche wir dem Benutzer zeigen wollen. Die Methode display() rufen wir auf, um das Gezeichnete dem Benutzer anzuzeigen.

Der Konstruktor kümmert sich um die Erstellung des Fensters, des OpenGL-Kontexts und der Schnittstelle für Skia.

Window::Window(std::string title, int x, int y, int width, int height) :
  sdlWindow(nullptr),
  glContext(nullptr),
  surfaceProps(SkSurfaceProps::kLegacyFontHost_InitType) {
  configureGl();
  initializeSdl();
  initializeSdlWindow(title.c_str(), x, y, width, height);
  initializeGlContext();
  initializeSurface();
}

Um bei der Programmierung nicht die Übersicht zu verlieren, ist das Initialisierungsprogramm in mehrere Funktionen aufgeteilt. Der Reihe nach werden Initialisierungsparameter für OpenGL via SDL konfiguriert, SDL initialisert, das SDL_Window objekt und darin der OpenGL-Kontext erstellt und dieser mit dem Skia Interface verknüpft.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Window::configureGl() {
  // set OpenGL version to 3.0
  SDL_GL_SetAttribute(SDL_GL_CONTEXT_MAJOR_VERSION, 3);
  SDL_GL_SetAttribute(SDL_GL_CONTEXT_MINOR_VERSION, 0);
 
  SDL_GL_SetAttribute(SDL_GL_CONTEXT_PROFILE_MASK, SDL_GL_CONTEXT_PROFILE_CORE);
 
  // skia requires 8 bit stencils
  SDL_GL_SetAttribute(SDL_GL_RED_SIZE, 8);
  SDL_GL_SetAttribute(SDL_GL_GREEN_SIZE, 8);
  SDL_GL_SetAttribute(SDL_GL_BLUE_SIZE, 8);
  SDL_GL_SetAttribute(SDL_GL_STENCIL_SIZE, 8);
 
  // we are using double buffer for swaping graphic content to avoid flickering when clearing
  SDL_GL_SetAttribute(SDL_GL_DOUBLEBUFFER, 1);
 
  SDL_GL_SetAttribute(SDL_GL_DEPTH_SIZE, 0);
 
  SDL_GL_SetAttribute(SDL_GL_ACCELERATED_VISUAL, 1);
 
  // uncomment the following to disable multisampling
  SDL_GL_SetAttribute(SDL_GL_MULTISAMPLEBUFFERS, 1);
  SDL_GL_SetAttribute(SDL_GL_MULTISAMPLESAMPLES, 4);
}

Die Einstellungen für den OpenGL-Kontext können theoretisch angepasst und optimiert werden. Auf meinem System liefern die festgeschriebenen Einstellungen gute Resultate. Mir ist kein Grund bekannt, warum auf anderen Systemen diese Konfiguration zu schlechten Ergebnissen führen sollte. Deshalb habe ich mich entschieden die Einstellungen in den Quelltext der Methode zu schreiben anstatt die Werte als Paramter zu übergeben. Fällt dir ein Grund ein, warum eine Parameterübergabe doch sinnvoller sein sollte?

void Window::initializeSdl() {
  const bool sdlInitSuccess = SDL_Init(SDL_INIT_VIDEO | SDL_INIT_EVENTS) == 0;
  if (!sdlInitSuccess) {
    throw domain_error("Cannot initialize SDL");
  }
}

Auf lesbaren Quelltext lege ich besonders großen Wert. Das erleichtert anderen und mir selbst den Quelltext zu verstehen, selbst dann, wenn ich den Quelltext schon Monate lang nicht mehr angesehen habe. Deshalb habe ich mir angewöhnt bei if-Verzweigungen meistens die Prüfung in einer Variablen zu erfassen. Die Variable gibt an, was genau geprüft wurde. Damit ist das if-Statement ziemlich hübsch zu lesen, ganz so als ob wir uns tatsächlich mit unserem Computer unterhalten und beraten könnten <(^_^)>

Bei einem Fehler während der Initialisierung soll eine Ausnahme geworfen werden, sodass dies vom Aufrufenden Programm verarbeitet werden kann. Denkbar wäre zum Beispiel recht einfach ein Benachrichtungssystem einzubauen, mit Hilfe dessen der Kunde die Entwickler benachrichtigen kann. Systeminformationen über den Rechner unseres Kunden könnten mit Hilfe anderer Softwarebausteine automatisch erfasst und dem Fehlerbericht beigefügt werden…

void Window::initializeSdlWindow(char const*const title,
                                 int const& x, int const& y,
                                 int const& w, int const& h) {
  int const windowOptions = SDL_WINDOW_OPENGL | SDL_WINDOW_RESIZABLE;
  sdlWindow = SDL_CreateWindow(title, x, y, w, h, windowOptions);
 
  bool const createWindowFailed = (sdlWindow == nullptr);
  if (createWindowFailed) {
    throw domain_error("Cannot create window");
  }
}

Natürlich wollen wir ein hardwarebeschleunigte Anzeige für unser Fenster. Außerdem gehe ich davon aus, dass die Größe des Fensters anpassbar sein soll. Also setzen wir die Optionen unseres Fensters auf das Bitmuster SDL_WINDOW_OPENGL | SDL_WINDOW_RESIZABLE.

TODO: bitmuster / bitflags / bitmasken erklären und verlinken

Erst jetzt initialisieren wir den OpenGL-Kontext, da wir ab jetzt sicher sein können, dass das Fenster erfolgreich erstellt wurde.

void Window::initializeGlContext() {
  glContext = SDL_GL_CreateContext(sdlWindow);
 
  bool const createGlContextFailed = (glContext == nullptr);
  if (createGlContextFailed) {
    throw domain_error("Cannot create GLContext");
  }
}

Mit Hilfe der Funktion GrGLCreateNativeInterface() erzeugen wir das Skia-OpenGL-Interface. Die Funktion liefert uns ein Pointerprimitv zurück, welches wir in einem Shared-Pointer-Konstrukt der Skia Bibliothek unterbringen. Um die passenden Einstellungen für das Skia-OpenGL-Interface zu finden, können wir SDL nach den jeweiligen Konfigurationsdaten fragen. Was für dich vielleicht ungewohnt ist: die Abfragen werden mit output-Parametern realisiert, satt Werte per return-Statement zurück zu geben. So übergeben wir einen Pointer auf renderTargetDesc.fStencilBits, damit die SDL Funktion auf den den mit dem Pointer referenzierten Speicher zugreifen kann und wir den Wert in renderTargetDesc.fStencilBits erhalten, den wir uns in der Variablen wünschen.

TODO: shared pointer erklären und verlinken

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Window::initializeSurface() {
  sk_sp<const GrGLInterface> grGlInterface(GrGLCreateNativeInterface());
  SkASSERT(grGlInterface.get() != nullptr);
 
  // this cast looks awkard, but it is intended to do so by the skia library
  grContext = sk_sp<GrContext>(GrContext::Create(kOpenGL_GrBackend, (GrBackendContext)(grGlInterface.get())));
  SkASSERT(grContext.get() != nullptr);
 
  // initialize renderTargetDesc by using queries
  SDL_GL_GetAttribute(SDL_GL_STENCIL_SIZE, &renderTargetDesc.fStencilBits);
  GrGLint frameBufferObjectId;
  grGlInterface->fFunctions.fGetIntegerv(GR_GL_FRAMEBUFFER_BINDING, &frameBufferObjectId);
  renderTargetDesc.fRenderTargetHandle = frameBufferObjectId;
  SDL_GL_GetAttribute(SDL_GL_MULTISAMPLESAMPLES, &renderTargetDesc.fSampleCnt);
  // static initialization of renderTargetDesc
  renderTargetDesc.fConfig = kSkia8888_GrPixelConfig;
 
  // create surface
  synchronizeSurfaceSizeByRecreation();
}

Das SkSurface-Objekt, welches SkCanvas zur Verfügung stellt muss nach einer Änderung der Fenstergröße neu konstruiert werden. Die Funktion synchronizeSurfaceSizeIfNecessary() prüft ob sich die Fenstergröße geändert hat. Sollte dies der Fall sein, wird das bisher verwendete SkCanvas-Objekt über synchronizeSurfaceSizeByRecreation() durch ein neu erstelltes an die Fenstergröße angepasstes SkCanvas-Objekt ersetzt.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SkCanvas* Window::getCurrentCanvas() {
  synchronizeSurfaceSizeIfNecessary();
  return surface->getCanvas();
}
 
void Window::synchronizeSurfaceSizeIfNecessary() {
  int width, height;
  SDL_GetWindowSize(sdlWindow, &width, &height);
  bool const needsSynchronization = (width != renderTargetDesc.fWidth) || (height != renderTargetDesc.fHeight);
  if (needsSynchronization) {
    renderTargetDesc.fWidth = width;
    renderTargetDesc.fHeight = height;
    surface = SkSurface::MakeFromBackendRenderTarget(grContext.get(), renderTargetDesc, &surfaceProps);
  }
}
 
void Window::synchronizeSurfaceSizeByRecreation() {
  SDL_GetWindowSize(sdlWindow, &renderTargetDesc.fWidth, &renderTargetDesc.fHeight);
  surface = SkSurface::MakeFromBackendRenderTarget(grContext.get(), renderTargetDesc, &surfaceProps);
}

Weil von Frame zu Frame die Größe des Fensters geändert werden kann und folglich das SkSurface-Objekt nach einer Größenänderung neu erzeugt werden muss, muss entsprechend auch das SkCanvas in jedem Frame mit getCurrentCanvas() erneut geholt werden. Dies ist eine Konvention, die vom Nutzer der Klasse eingehalten werden muss. Kannst du erklären, warum es so ungeheuer wichtig ist diese Konvention einzuhalten?

Im Detail wird durch die Zuweisung des Attributs surface dessen Referenzzähler um eins dekrementiert. Der Shared-Pointer surface ist im Window-Objekt gekapselt. Die Implementierung lässt keinen direkten Zugriff auf den Shared-Pointer zu. Deshalb kann es maximal eine aktive Referenz auf das SkSurface-Objekt geben, welches über den Shared-Pointer surface referenziert wird. Der Referenzzähler des Shared-Pointers surface kann also nie größer als 1 werden. Sobald surface ein anderer Shared-Pointer zugewiesen wird, wird der Referenzzähler um eins erniedrigt. Dies führt in diesem Fall unweigerlich dazu, dass der Referenzzähler den Wert 0 erreicht und damit das referenzierte SkSurface-Objekt gelöscht wird.

Über getCurrentCanvas() bekommen wir allerdings mit dem zurück gelieferten Pointer Zugriff auf Innereien der SkSurface. Folglich könnten wir selbst nach dem Löschen der SkSurface weiterhin mit dem Pointer auf bereits freigegebenen Speicherplatz zugreifen. Dies führt allerdings zu undefiniertem Verhalten, da der Speicherplatz in der Zwischenzeit neu vergeben und anders partitioniert werden kann. Wir lesen praktisch Datenmüll und falls wir schreibend auf das SkCanvas mit einem draw(***)-Aufruf zugreifen, könnten wir so ausversehen Speicher mit Datenbits überschreiben, welcher eigentlich bereits für andere Objekte reserviert wurde. Im schlimmsten Fall, wenn wir lesend und schreibend auf das SkCanvas zugreifen, dessen Speicherplatz bereits freigegeben und anschließend für andere Objekte reserviert wurde, schreddern wir also unsere Daten im RAM. Hoffentlich stürzt das Programm sofort ab, sodass wir die Fehlerquelle leichter einschränken können.

Wenn wir je Frame ein einziges mal getCurrentCanvas() aufrufen, sind wir vor dieser Fehlerquelle auf jeden Fall geschützt. (Mir fällt auch kein guter Grund ein, warum man die Funktion öfter als ein mal je Frame aufrufen sollte. Fällt dir ein Grund ein?)