Programmatisch feststellen, ob zwei Geraden identisch sind

Im letzten Artikel haben wir uns damit beschäftigt, wie wir programmatisch den Schnittpunkt zweier Geraden bestimmen können. Dieser Artikel ist eine Ergänzung zum Thema, wir zeigen, wie wir mit Hilfe unserer Funktion berechneSchnittpunkt([...]) bestimmen können ob zwei Geraden aufeinander liegen, also identisch sind oder nicht.

Wie im letzten Artikel verwenden wir die folgenden generischen Geradengleichungen:
\(
g: \vec{x} = \vec{u} + t \vec{v} \\
h: \vec{x} = \vec{a} + r \vec{b}
\)

Zur Bestimmung des Schnittpunkts zweier Geraden haben wir folgende Formel hergeleitet:
\(
t = \frac{b_x (u_y – a_y) + b_y (a_x – u_x)}{v_x b_y – v_y b_x}
\)

Wir haben im letzten Artikel außerdem gezeigt, dass die Geraden parallel liegen, wenn der Nenner gleich \(0\) wird. Können wir auch mit der Berechnung prüfen ob die Geraden aufeinander, also pseudo parallel zueinender liegen? Tatsächlich funktioniert das auch. Die Geraden liegen nämlich genau dann aufeinander, wenn der Nenner und der Zähler der Formel \(0\) werden.

Ihr fragt euch, warum soll das so sein? Um das zu zeigen müssen wir erst einsehen, dass wenn der resultierende Vektor aus \((\vec{a} – \vec{u})\) linear abhängig zu \(\vec{b}\) ist und \(\vec{b}\) linear abhängig zu \(\vec{v}\) ist, die Geraden aufeinander liegen. Es ist natürlicherweise so, dass wenn \(\vec{b}\) linear abhängig zu \((\vec{a} – \vec{u})\) ist und \(\vec{b}\) linear abhängig zu \(\vec{v}\), dann ist auch \((\vec{a} – \vec{u})\) linear abhängig zu \(\vec{v}\). Das ergibt sich aus der Transitivität der linearen Abhängigkeit. Wenn dem so ist, können wir die Stützvektoren \(\vec{a}\) und \(\vec{u}\) durch Skalierung der Richtungsvektoren der jeweils anderen Geraden erreichen. Damit ist auch jeder andere Punkt der einen Geraden mit der Geradengleichung der anderen Geraden erreichbar. Also müssen die Geraden aufeinander liegen. Am besten macht ihr euch das zusätzlich anhand einer Skizze klar.

Was wir jetzt zeigen müssen ist, dass der Zähler genau dann \(0\) wird, wenn \(\vec{b}\) linear abhängig zu \((\vec{a} – \vec{u})\) ist. Die lineare Abhängigkeit lässt sich mit folgender Gleichung zeigen: \(\vec{b} = k(\vec{a} – \vec{u})\). Wir wissen aus der Betrachtung der linearen Abhängigkeit, dass \(\vec{e} = k \vec{d}\) äquivalent zu \(e_x d_y – e_y d_x = 0\) ist. Wenn wir für \(\vec{e}\) den Vektor \(\vec{b}\) und für \(\vec{d}\) den Vektor \((\vec{a} – \vec{u})\) einsetzen, kommen wir darauf, dass auch \(\vec{b} = k(\vec{a} – \vec{u})\) äquivalent zu \(b_x(a_y – u_y) – b_y(a_x – u_x) = 0\) ist. Der linke Term der Gleichung sieht ähnlich aus, wie der Zähler unserer Formel. Durch Äquivalenzumformung zeigen wir, dass dieser Term tatsächlich äquivalent zum Zähler unserer Formel ist.
\(
\begin{array}{rcll}
\vec{b} &=& k(\vec{a} – \vec{u}) \\
&\Leftrightarrow& \\
b_x(a_y – u_y) – b_y(a_x – u_x) &=& 0 &| \cdot (-1) \\
b_x \cdot (-1) \cdot (a_y – u_y) – (-1) \cdot b_y(a_x – u_x) &=& 0 \\
b_x (-a_y + u_y) – (-b_y)(a_x – u_x) &=& 0 \\
b_x (u_y – a_y) + b_y(a_x – u_x) &=& 0 \\
\end{array}
\)

Also ist der Zähler gleich \(0\), genau dann wenn, \((\vec{a}-\vec{u})\) linear Abhängig zu \(\vec{b}\) ist. Wenn der Nenner \(0\) ist, sind auch die Richtungsvektoren \(\vec{v}\) und \(\vec{b}\) linear abhängig. Sind Nenner und Zähler gleich \(0\) müssen also die Geraden identisch sein, das heißt jeder Punkt der einen Geraden liegt auch auf der anderen Geraden.

In C++ führt die Berechnung von 0.0/0.0 zum Ergebnis NaN. Wenn wir also für die Berechnung des Schnittpunktes einen Vektor mit den Werten (NaN | NaN) erhalten, sind die Geraden identisch. Wenn wir (+inf | +inf) oder (-inf | -inf) erhalten, liegen die Geraden echt parallel zueinander.

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

Wie setze ich mein phpBB Administrator-Passwort über die interne Datenbank zurück?

Finde als erstes heraus, welche Datenbank dein phpBB nutzt. Wahrscheinlich nutzt du MySQL und dein Provider stellt dir Zugang zur Datenbank mittels phpMyAdmin zur Verfügung.

In der Tabelle [dein_phpbb3_db_präfix]_users findest du die Datensätze für alle registrierten Nutzer. Um ein Passwort zu ändern musst du den entsprechenden Eintrag in der Spalte user_password ändern. Wie du selbst erkennen kannst, werden die Passwörter aus Sicherheitsgründen nicht im Klartext gespeichert. Stattdessen speichert phpBB einen BCrypt Hash des Passworts. BCrypt ist ein cryptografisch (noch) sicheres Hashverfahren, welches aus einer modifizierten Version des Blowfish Algorithmus entstand.

Um also ein Passwort in der Tabelle einzutragen, musst du zuerst dein gewünschtes mit BCrypt hashen. Dazu kannst du jede Crypto-API verwenden, die den BCrypt Standard unterstützt oder du gehst auf bcrypt-generator.com. Auf bcrypt-generator.com gibst du dein gewünschtes Passwort ein, drückst auf Hash! und erhältst einen BCrypt Hash. Den BCrypt Hash trägst du statt deines tatsächlichen Passworts in der Spalte user_password der Tabelle [dein_phpbb3_db_präfix]_users ein.

Anschließend solltest du dich wieder in deinem phpBB mit deinem Administratornutzer einloggen können.

Psst! Du kannst selbstverständlich auf diese Weise jedes Passwort jedes anderen Nutzers ändern. So kannst du im Namen jedes anderen Nutzers deines Forums Posts verfassen… damit er das nicht merkt speicherst du natürlich vorher den Hash irgendwo und ersetzt ihn nach deinem schandhaften Tun wieder. Aber Psst! das bleibt unter uns, ja?

Falls etwas schief geht, schreibt mir einen Kommentar. Bei Bedarf mach ich euch auch gerne eine detaillierte Anleitung mit Screenshots
<(^_^)>

textsmili.es

Habt ihr euch auch schon mal gefragt, woher Leute sowas hier ᕕ(◔Ꮂ◔)ᕗ oder dies hier ¯\_☉!☉_/¯ her haben?

Schaut mal bei textsmili.es vorbei. Eine besonders tolles Feature ist das Feature um UNEENDLIIICH Textsmilies zu generieren!

(∩ ͡° ͜ʖ ͡°)⊃━☆゚.*

cool dabei ist auch, dass ihr die Smileys etwas modden könnt indem ihr unterschiedliche Schriftarten auswählt. Das geht allerdings nur, wenn ihr einen Richtext-Editor verwendet oder eine HTML-eMail sendet. Das Beste: die Smileys funktionieren auch in Whatsapp, Telegram und Threema ;D

viel Spaß ^^
euer nuiun

nuiun wird Softwarearchitekt

Bist du Programmierer? Willst du Programme schreiben, die du und andere mit Leichtigkeit warten können? Hast du dir schonmal überlegt dich näher mit Softwarearchitektur zu befassen? Wenn nicht, dann wird es höchste Zeit! Denn

  • Programmieren ist kreativ, unterhaltsam und nur ganz selten super frustrierend, ganz ehrlich ;D
    • falls du kein Programmierender bist —
      I want you to start programming right here and now!
  • Programmieren mit Entwurfsmustern um zu einer soliden Softwarearchitektur zu gelangen ist FRKN G0DL1K3

Falls du also super 1337 sein willst, lern was über Softwarearchitektur und Entwurfsmuster. Kein Schei~piep~.

Vor kurzem war ich auf der Suche nach guten Lehrbüchern für Softwarearchitektur. Dabei ist mir das Buch „Entwurfsmuster von Kopf bis Fuß“ von Eric Freeman und Elisabeth Robson in die Hände gefallen. Das Buch ist erstaunlich unterhaltsam. Ich bin restlos überzeugt und begeistert von den Lehrmethoden mit dem die Autoren dem Leser das Themengebiet näher bringen. Das erste Kapitel erklärt unter der Überschrift „Wir wissen, was Sie gerade denken“, wie wir Menschen lernen und warum wir Menschen lernen, wie wir lernen. Wenn du dieses Buch liest, wird dein Gehirn pausenlos mit interessanten Bildern, Sprechblasen und Fotostories gefüttert.

Hast du schonmal versucht dich neben Menschen in Partystimmung in deiner Lieblingsnachbar-WG zu setzen und ein Fachbuch zu lesen? Nein? Gut so! Denn bevor ich das mit dem Buch aus der Reihe „Von Kopf bis Fuß“ ausprobiert habe, hätte ich nie auch nur annähernd für möglich gehalten, dass das funktionieren könnte (es sei denn du hast eine Art Super-Brain und kannst deine Aufmerksamkeit nach belieben zu 100% lenken. Wenn du das kannst, kannst du wahrscheinlich auch Laserstrahlen aus deinen Augen abfeuern). Punkt um, mit dem Lehrbuch „Entwurfsmuster von Kopf bis Fuß“ könntest du auch Achterbahn fahren, das Buch lesen und tatsächlich etwas vom Gelesenen in deinem Hirn speichern.

Auf fairmondo könnt ihr fair alles mögliche shoppen. Hier gibt es aktuell zum Preis von 20€ eine Gebrauchte Ausgabe von „Entwurfsmuster von Kopf bis Fuß“. Laut Angaben des Verkäufers werden 5%=1€ an Ingenieure ohne Grenzen gespendet. Falls das Buch schon weg ist, hier ein weiterer Link zum Fachbuch „Entwurfsmuster von Kopf bis Fuß“.

Ich habe in diesem Artikel (ausnahmsweise) 0 Sarkasmus verwendet.
Seriously    (∩ ͡° ͜ʖ ͡°)⊃━☆゚.*
nuiun

PS: demnächst habe ich vor euch ein paar Entwurfsmuster mit Anwendungsbeispielen in C++ vorzustellen.
Viel Spaß beim Lesen <(^_^)>

Gender Wörter

Hast du dich je daran gestört, dass es Professor und nicht Professorin heißt? Im Deutschen werden Berufsbezeichnungen und Titel meistens (oder (fast) immer) im allgemeinen Kontext in der männlichen Form verwendet. Nach den Befürwortenden der Geschlechtergerechten Sprache soll damit offiziell ab sofort Schluss sein. Oder zumindest wurden Alternativen vorgeschlagen. Ab sofort solle man statt „Taxifahrer“ oder „Busfahrer“ besser „Taxifahrender“ und „Busfahrender“ schreiben. Zumindest sofern man nicht nur alle männlichen Personen meint, welche taxifahrend oder busfahrend sind ;D

Ok… schauen wir uns das mal an ein paar Beispielen an. Wie wärs mit „Bäcker“? Das wär dann wohl „Bäckernder“? W00T? Nee, wohl eher „Backender“?!? Wie stehts mit Florist? Das hieße wohl dann „Florierender“ (づ◔▾◔)づ Na gut, noch eins: „Metzger“, vielleicht „Metzgernder“? Ups, wahrscheinlich doch „Schlachtender“ how evil is that plx? x_x

Ok, Spaß beiseite. Wie in der Wikipedia zu lesen sind „Ungewohnte und wenig verbreitete Bildungen aus Partizipien I wie Zufussgehende […] laut dem Leitfaden der Schweizerischen Bundeskanzlei zu vermeiden.“.

Hoffe euch hats gefallen, lasst mir n Kommentar oder zwei da und bis demnächst,
euer nuiun <(^_^)>

Mondfischen – Eine Kurzgeschichte von nuiun

Die folgende Geschichte habe ich für einen Poetry Slam geschrieben. Über Kommentare würde ich mich sehr freuen =D
Und nun… viel Spaß beim Lesen
<(^_^)>

Mondfischen

Anmerkung des Autors
zu reimen liegt mir nicht,
deswegen seid mir nicht gram.
Die Sprache beherrsche ich doch gut.

Geschichten zu erzählen,
liegt mir mehr.
Deshalb seid jetzt still.

Bedenkt ein Mensch ist jeder,
der sich Mensch nennen kann.
Ob Mann, ob Frau, das ist egal.

Und jetzt ————-
lasst euch verzaubern
vom bitter süßen Traum

Es war einmal ein Seemann in seinen besten Jahren. Die See war seine zweite Heimat. Wohl war er sich der Gefahren bewusst, die sich in den Tiefen tummeln. Die See konnte launisch im Sturm turmhohe Wellen schwindelerregend über die Köpfe und Segel hinweg schleudern. Sicher hatte auch er so einiges Treibgut nach einem Sturm am Strand gefunden. Bisher hatte er allerdings Glück gehabt. Die See war ihm wohl gesonnen, so schien es.

Der Tag war hell gewesen, nun stand die Sonne bereits auf 160° über dem Horizont. Feuerlodernd gelb-rot tauchten Sonnenstrahlen das wabernde Meer in eine Lavawüste. Mondfischen war angesagt. Deshalb hatte er den halben Tag am Strand liegend verbracht um sich auszuruhen und sich auf die Nacht vorzubereiten. Jetzt war es an der Zeit sein Boot, die Silandara, vorzubereiten.

Gedacht, getan, die Silandara war bald seetüchtig hergerichtet und der Seemann löste die Leinen. Silandara nahm, wie gewohnt, schnell an Fahrt auf. Eine süße Briese wehte über die Dühnen vom Land auf die See. Mit kühnem Blick saß er am Steuer den Blick auf den flammenden Horizont gewandt.

Weit draußen an den Fischgründen warf er sein Netz aus. Die Sonne war inzwischen in ihrer eigenen Glut versunken. Er hisste das kleine Segel um sachte über das jetzt abgrund tief schwarze Meer zu gleiten. Hoch über Silandara am Himmelszelt funkelten tausende und abertausende Sterne. Ein jeder Stern beherberge wiederum eine vielzahl an Seelen, die die Sterne zum leuchten brachten, so sagte man sich. Also gab es auch nichts vor dem Tod zu befürchten, denn er war überzeugt eines Tages selbst auf einem dieser Funken zu reiten.

So wie der Tag das Leben weckte, so stand die Nacht dem Tod nahe, erzählte man sich. Deswegen galt das Mondfischen als Ereignis um die Seele immer wieder aufs neue auf den Tod vorzubereiten. Schließlich währte kein einzelnes Leben ewig. Derlei Gedanken gingen ihm durch den Kopf als er sich plötzlich dem Nebelschwaden um seine Silandara gewahr wurde.

Dies war nicht unbedingt Grund zur Sorge, aber er machte sich dennoch daran die Netze einzuholen. Unterdessen fiel ihm ein dicker nasskalter Tropfen in den Nacken. Erschrocken schaute er empor und sah den gleißend weiß glühenden Mond hinter einer mächtigen ungeheur schwarzen Wolke verschwinden.

Seine Bewegungen wurden hastig, eifrig machte er sich daran das große Netz am Bug notdürftig zu verstauen. Der Regen wurde allmählich stärker und er hetzte zum Mast um das Großsegel zu hissen. Wasser rann ihm über das Gesicht sodass er andauernd blinzeln musste. Silandara ächzte unter dem Druck des Windes auf das große Segel. Er machte die Leinen fest begab sich ans Heck und ans Steuer. Schnell mit dem starken Wind nahm seine Silandara wieder Fahrt Richtung Ufer auf.

Jetzt bemächtigte sich das Unwetter allerdings weitaus größerer Gewalt, der Mast bog sich Gefährlich im Wind. Mit beherzten schweren Schritten machte er sich auf den mühsamen Weg, der bei gutem Wetter keiner Rede wert gewesen wäre, auf zum dicken Segelmast um das Segel zu lösen, damit es Silandara nicht den Mast breche und damit manövrierunfähig mache. Gegen peitschenden Regen und Wind gelehnt, die Arme vor dem Gesicht verschränkt setzte der Seemann verbissen einen Fuß vor den anderen.

Endlich kam er an den zum Zerreißen gespannten Seilen an. Er zog am Seil, doch der Knoten blieb vom Wind wie festgenagelt. Behände zückte er sein Messer, das er immer an seiner Hüfte trug und schlug mit einem einzigen Hieb das Seil in zwei. Die Stränge peitschten gelöst von der Spannung in alle Richtungen, sodass er sich ducken musste um nicht getroffen zu werden.

Als er nach einem Augenschlag wieder aufsah, sah er seine Nemesis. Ein riesiges Ungeheuer, turmhoch, so hoch, dass es den Anschein hatte, als wolle es sich mit dem Himmel und den Wolken voller Finsternis vereinen. Eine Welle von solchem Ausmaß, dass ein leibhaftiger Gott darin hätte wüten können.

Missmutig starrte er seinem Schicksaal entgegen. Er bleckte die Zähne und machte sich mit geballten Fäusten bereit auf den Aufprall, wohl wissend, dass er in wenigen Sekunden die guten Planken Silandaras unter seinen baren Füßen nicht mehr spühren würde. Heulend warf sich das Ungeheuer auf Silandara, sein immer treues Boot, und ihn, dem kleinen Menschenkind.

Der Regen hatte seine Glieder taub werden lassen. So trieb er im Schlund seines Schlächters benommen dahin. Der letzte Lebensfunke weckte ihn unwillkürlich und er begann mit letzter Kraft wild um sich zu strampeln und versuchte zurück an die Oberfläche zu tauchen. Seine Brust brannte wie Feuer. Das Leben selbst bäumte sich in seiner Brust auf und tobte, nicht willens sich von seinem Heim zu lösen. Sein Geist suchte seine Seele zu beschwichtigen, wohl wissend, dass jede Mühe vergebens war.

Da endlich war es so weit, der Schmerz explodierte als er einen großen Schwall Wasser einatmete. Die Schwärze umfing ihn gänzlich, der Schmerz, alles Leid, jeder Kummer fiel von ihm ab als sich seine Seele von ihrem getrauten Heim löste. Sanft schwebte sie zwischen vielerlei form- und farbenfrohen Meeresgetier einher. Bis sie sich teilte, in immer kleinere feinere Fasern teilte um wieder eins mit allem zu werden und in vielerlei Leben wieder geboren zu werden.

Spiel und Spaß mit Bash Shell Befehl sed

Während meiner Arbeit an meiner Blog Reihe zu Skia, SDL2 und OpenGL war es mir irgendwann zu lästig ständig immer wieder dieselben tags einzutippen. Da habe ich mich an den Grundkurs Systemadministration erinnert. Unter anderem habe ich damals etwas Bash-Programmierung gelernt und den Bash Shell Befehl sed verwendet um Strings mit Regulären Ausdrücken in andere Strings zu wandeln. Die man-Page war leider wiedermal für mich recht unverständlich. Glücklicherweise bin ich auf „Sed – An Introduction and Tutorial“ von Bruce Barnett gestoßen. Das Tutorial erklärt in aller Ausführlichkeit alles Wissenswerte und darüber hinaus weitere Details, die wahrscheinlich eher selten Anwendung finden, wenn überhaupt m(.)_(.)m

Um zum Beispiel folgendes zu schreiben:

<pre lang="cpp">
#include <iostream>
int main() {
  using std::cout;
  using std::endl;
  cout << "Hallo SED =D" << endl;
}
</pre>

Kann ich stattdessen einfach dies hier tippen:

[[cpp
#include <iostream>
int main() {
  using std::cout;
  using std::endl;
  cout << "Hallo SED =D" << endl;
}
]]

Anschließend führe ich folgenden Befehl aus:

sed -r -i '' '
  s#^\[\[([a-zA-Z]+)(.*)#<pre lang="\1"\2>#;
  s#^\]\]$#</pre>#;
  s#^\\\[\[#[[#;
  s#^\\\]\]#]]$#
' 'blogPost.txt'

Lass uns das gemeinsam Stück für Stück auseinander nehmen. Das Flag -r aktiviert die erweiterte Syntax und Semantik für Reguläre Ausdrücke. sed auf Mac OSX und FreeBSD verwendet -E statt -r. Der Shellparameter -i gibt die Anweisung, dass die angegebene Datei mit den Substitutionsbefehlen modifiziert werden soll. Der leere String hinter -i veranlasst sed keine Backup Datei anzulegen. Wenn stattdessen beispielsweise -i '.bak' übergeben wird, legt sed eine Kopie der ursprünglichen Datei mit dem Suffix .bak an.

Der nachfolgende String erstreckt sich zur besseren Übersicht über mehrere Zeilen. Jede Zeile enthält eine Substitutionsanweisung. s leitet den Substitutionsbefehl ein. Danach kann ein Delimiter gewählt werden. Als Delimiter bieten sich zum Beispiel _, #, / oder : an. Nach dem ersten Delimiter wird der Reguläre Ausdruck angegeben durch den bestimmt wird, welche Muster ersetzt werden sollen. Über die erweiterte Syntax für Reguläre Ausdrücke können wir mit () Gruppen festlegen, die wir anschließend in der Ersetzungsvorschrift wieder verwenden können.

Nach dem Regulären Ausdruck wird ein weiterer Delimiter und an diesen die Ersetzungsvorschrift angehängt. Mit \n, wobei n für eine Zahl zwischen 1-9 steht, kann die Gruppe ausgewählt werden, deren match anstelle des \n eingefügt werden soll.

Sonderzeichen mit spezieller Bedeutung müssen, wenn diese als reguläre Zeichen erkannt werden sollen mit \ escaped werden. So sind beispielsweise [ und ] Teil der Syntax für Reguläre Ausdrücke. Um [ und ] zu matchen, müssen wir diese mit vorangestelltem \ notieren.

Die erste Substitutionsanweisung besagt folglich, dass Zeilen gematched werden, die mit [[ beginnen und nach [[ mindestens ein Buchstabe folgen muss. Es sind außerdem zwei Gruppen definiert. Die erste erfasst die abfolge der Buchstaben nach [[. Die zweite erfasst alles, was danach folgt, bis zum Zeilenende. Auch der leere String wird mit der zweiten Gruppe erfasst. sed kann leider mit dem Substitutionsbefehl nur Zeilen verarbeiten. Deswegen brauchen wir an dieser Stelle das Zeilenende nicht zu matchen. Im zweiten Teil der Substitutionsanweisung geben wir an, durch was ein Mustertreffer ersetzt werden soll. Dabei werden die Gruppen \1 und \2 genutzt um Informationen aus dem Match zu ziehen und wieder zu verwenden.

Angenommen wir geben dem Befehl folgendes an input:

[[cpp
int main() { return 0; }
]]

Kannst du abschätzen, was uns sed dafür ausspuckt? Mit folgendem Befehl kannst du es einfach ausprobieren:

echo '
[[cpp
int main() { return 0; }
]]
' | sed -r '
  s#^\[\[([a-zA-Z]+)(.*)#<pre lang="\1"\2>#;
  s#^\]\]$#</pre>#;
  s#^\\\[\[#[[#;
  s#^\\\]\]#]]$#
'

Sofern du die erste Substitutionsanweisung verstanden hast, kommt dir die zweite wohl sehr einfach vor. Die Dritte und vierte Anweisung dienen dem Escapen der Zeichenfolgen [[ und ]]. Sollten wir eine der Zeichenketten tatsächlich an den Anfang einer Zeilenkette stellen wollen, ohne dass diese ersetzt werden, müssen wir einen entsprechenden Mechanismus einbauen, der uns das erlaubt. Uns stehen mit sed leider keine programmatischen Verzweigungen zur Verfügung (zumindest nicht, soweit ich weiß). Was wir stattdessen programmieren können sind Textersetzungen. Also definieren wir Escape-Sequenzen, welche durch die von uns jeweils gewünschten Zeichenketten ersetzt werden. So wird über den dritten Befehl \[[ mit [[ ersetzt sofern erstere Zeichenkette am Anfang einer Zeile steht. Wie ganau funktioniert die vierte Substitutionsanweisung? Im Prinzip ganz ähnlich wie die vorhergehende. Du kommst bestimmt selbst darauf ;D

Doch was tun wir, wenn wir tatsächlich \[[ oder \]] am Anfang einer Zeile stehen haben wollen? Dafür müssen wir unsere Anweisungen erweitern. Wenn wir allerdings eine neue Escape-Sequenz einführen, Müssten wir eben diese erneut escapen. Dies Führt zu einer endlosen Rekursion und die Befehlskette würde erst dann aufhören, wenn uns der Speicherplatz dafür ausgeht. Nur leider hätten wir damit schließlich das Problem immer noch nicht gelöst. Stattdessen definieren wir dass aus \[[\[[ -> \[[ wird. Jetzt fragst du sicherlich, aber was tun wir wenn wir \[[\[[ am Anfang der Zeile stehen haben wollen? Auch dafür haben wir mit derselben Vorschrift eine Lösung und das erwähnte Rekursivproblem wird aufgehoben. Wir schreiben \[[\[[\[[ um \[[\[[ zu erhalten. Also jedes mal, wenn wir eine bestimmte Anzahl der Zeichenfolge \[[ am Anfang einer Zeile nach der Ersetzung stehen haben wollen, schreiben wir \[[ einfach einmal mehr dazu, als wir es uns im Endergebnis wünschen. Die ersten Zwei Folgen von \[[ werden durch genau eine Folge ersetzt.

Natürlich müssen wir darauf achten, dass \[[\[[ nicht zu [[\[[ umgeformt wird. Deshalb müssen wir die dritte Regel anpassen, sodass diese nicht greift, wenn \[[\ erkannt wird.

Was also gibt folgender Bash-Shell-Befehl aus?

echo '
[[xml
\[[regex]]
\]] << Escape Sequence
\[[\[[ << Double Escape Sequence [[]]
\]]
\]]\]]
\[[\[[\[[
\]]\]]\]]\]]
]]
' | sed -r '
  s#^\[\[([a-zA-Z]+)(.*)#<pre lang="\1"\2>#;
  s#^\]\]$#</pre>#;
  s#^\\\[\[([^\])#[[\1#;
  s#^\\\]\]$#]]#;
  s#^\\\[\[\\\[\[#\\\[\[#;
  s#^\\\]\]\\\]\]#\\\]\]#;
'

Ich hoffe dir hat das Tutorial gefallen =) Hier ein kleines Skript nur zum Spaß. Weißt du schon vorher was ausgegeben wird? Kleiner Tip: das Suffix g besagt, dass die Substitution global ausgeführt werden soll. Ohne das Suffix g wird nur das erste Vorkommen des Musters in jeder Zeile ersetzt.

echo 'sed and regex are frkn POWERFULL!' | sed -r 's#([a-zA-Z])#[\1]#g'

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