Schnittpunkt zweier Geraden in C++ ermitteln? (bzw. Lineares Gleichungssystem lösen)

Ich frage mich, wieviele Leute wohl schon das GE implementiert haben und es war trotz seiner Probleme gut genug für sie und gleich im nächsten Schritt, warum es nicht einfach in der Standardbibliothek eine Umsetzung gibt...

SeppJ

Decimad schrieb:

Ich frage mich, wieviele Leute wohl schon das GE implementiert haben und es war trotz seiner Probleme gut genug für sie und gleich im nächsten Schritt, warum es nicht einfach in der Standardbibliothek eine Umsetzung gibt...

Weil es keine praktische Bedeutung hat.

Und das würdest Du auch über LU-Zerlegung und jedes andere Lösungsverfahren sagen und am Ende gibt es keines in der Standardbibliothek und jeder schreibt sich für seine kleinen Probleme wieder ein GE...

knivil

Da scheint ja jemand alles ueber mich zu wissen. Aber nur weil ich einen Spatz selbst realisieren wollte, wuerde ich es noch lange nicht bei einem Elephanten tun. Dir scheint es ums Prinzip zu gehen, mir geht es ums Problem. Und LU ist im Allgemeinen schwieriger als der Schnittpunkt zweier Geraden. Und dann bleibt noch das Problem der schlechten Konditionierung.

Darueber hinaus gibt es vielleicht was in boost.geometry. Das ist aber auch mit Kanonen auf Spatzen schiessen. Auch in Intels ipp gibt es sowas fuer kleine Matrizen.

Naja, mal die Problemstellung hier außen vor gelassen. Ich würde nicht den Schnittpunkt zweier 3D-Geraden berechnen, sondern deren Abstand voneinander und die nächsten Punkte.

SeppJ

Decimad schrieb:

Und das würdest Du auch über LU-Zerlegung und jedes andere Lösungsverfahren sagen

Nein. Leg mir nichts in den Mund, was ich nicht sage. Aber GE gibt es nicht in der Standardbibliothek aus ähnlichem Grund, aus dem es kein Bubblesort gibt. Das implementieren auch sehr viele Leute selber und haben damit auch oft Schwierigkeiten und ihr Resultat ist insgesamt von schlechter Qualität. GE ist eben vor allem eine Hausaufgabe, kaum jemand braucht es wirklich und die, die es brauchen sollten, könnten es schnell selber implementieren. Die Gründe, warum es nicht in der Standardbibliothek ist, sind ausführlich dargelegt:
1. Arbeit mit Matrizen ist tendenziell zu selten, als dass man es in der Standardbibliothek bräuchte
2. Arbeit mit Matrizen wird von externen Bibliotheken exzellent unterstützt
3. Man müsste auch Matrizen und vieles mehr einführen, wenn man GE in die Standardbibliothek aufnimmt.
4. Selbst wenn man mit Matrizen arbeitet, liefert das GE selten das, was man wirklich sucht. Eine MAtrix invertieren muss man praktisch nie, die Lösungen eines LGS findet man mit anderen Verfahren genauso einfach oder sogar einfacher.
5. Zum Thema Lösungen einfacher finden: Das Verfahren bricht bei großen Matrizen ein, ist also nicht allgemein benutzbar. Das ist schlecht für einen Algorithmus in einer Standardbibliothek. Zumal der Fall großer Matrizen doch gerade der interessante ist, für die Leute, die überhaupt mit Matrizen arbeiten müssen.
6. Wenn man meint, für sein Spiel 3x3-Gleichungen mittels GE lösen zu müssen, dann macht man etwas ebenso falsch wie die Leute, die Bubblesort in echten Anwendungen benutzen (es gibt Gerüchte, in Excel wäre mal Bubblesort an einer Stelle benutzt worden ). edit: Danke an volkard, der, während ich an meiner Antwort schrieb, schon so schön eine Alternative zeigt.

Jetzt habe ich dir alles gesagt, was ich dazu zu sagen habe, jetzt kannst du die einzelnen Aussagen kritisieren.

volkard

ntldr schrieb:

Mathematisch lässt sich das ja Problemlos als Gleichungsystem darstellen:
I    o1x + r * d1x = o2x + s * d2x
II   o1y + r * d1y = o2y + s * d2y
III  o1z + r * d1z = o2z + s * d2z
(o hierbei für den Ortsvektor der Geraden, d für den Richtungsvektor)
(r und s hier unbekannt)

Jetzt stellt sich für mich die Frage, wie ich nun dieses Gleichungsystem in C++ lösen kann, da ich ja nur eine Variable direkt berechnen lassen kann.
Also prinzipiell so:
double r = (-o1x + o2x + s * d2x) / d1x
Jetzt ist hier aber s nicht eindeutig definiert .

In dem Fall wie genannat Cramerregeln.
Und allgemein, falls man nix findet, was Große Mathematiker scon rausgefunden haben, einfach selber mal Mathematiker sein.
Das LGS per Hand lösen, obwohl(!) da noch Variablen stehen.

o1x + r*d1x = o2x + s*d2x   //*d1y
o1y + r*d1y = o2y + s*d2y   //*d1x

o1x*d1y + r*d1x*d1y = o2x*d1y + s*d2x*d1y
o1y*d1x + r*d1y*d1x = o2y*d1x + s*d2y*d1x

//subtrahieren

o1x*d1y - o1x*d1y = o2x*d1y + s*d2x*d1y - o2y*d1x - s*d2y*d1x

//Produkte mit s nach links, Rest nach rechts. 

s*d2y*d1x - s*d2x*d1y = o2x*d1y - o2y*d1x + o1x*d1y - o1x*d1y

//s ausklammern

s*(d2y*d1x-d2x*d1y) = o2x*d1y - o2y*d1x + o1x*d1y - o1x*d1y

//s final isolieren

s = (o2x*d1y - o2y*d1x + o1x*d1y - o1x*d1y) / (d2y*d1x-d2x*d1y)

So hat jeder seinen kleinen Mathematiker in der Tasche, wenn er mag.

krümelkacker

volkard schrieb:

...
So hat jeder seinen kleinen Mathematiker in der Tasche, wenn er mag.

Würde ich nicht so machen. Das ist keine Lösung im Sinne der kleinsten Fehlerquadrate bei windschiefen Geraden.

knivil

Decimad schrieb:

Naja, mal die Problemstellung hier außen vor gelassen. Ich würde nicht den Schnittpunkt zweier 3D-Geraden berechnen, sondern deren Abstand voneinander und die nächsten Punkte.

Dann hier: http://paulbourke.net/geometry/pointlineplane/

dot

Rein prinzipiell würd mich mal interessieren, wofür genau du eigentlich den Schnittpunkt zweier Geraden in 3d berechnen musst. Was genau willst du erreichen und wieso denkst du, dass die beste Lösung über den Schnittpunkt zweier Geraden führt? Meiner Erfahrung nach ist sowas in 3d nämlich meistens wohl eine eher ziemlich unelegante Lösung...

hustbaer

Ich würde hier auch die beiden Lotfusspunkte berechnen, und dann gucken ob die nahe genug beieinander liegen dass sie als ein Punkt durchgehen.

Dazu muss man nur ne Linie mit ner Fläche schneiden können, und das wiederrum kann man ohne das Lösen irgendwelcher Gleichungssysteme machen. Dabei kommt man mit einer einzigen Fallunterscheidung durch, und zwar ob ein Wert durch den man gerade dividieren möchte ungleich Null ist.
Im Gegensatz zur "einsetzen und auflösen" Variante muss man dann aber kein anderes Gleichungspaar mehr versuchen, sondern weiss - Falls der Wert Null ist - dass die beiden Geraden parallel liegen. (EDIT: bzw. eigentlich kann man das sogar vorher schon abfangen, da man ja schnell sieht dass das Kreuzprodukt der beiden Richtungsvektoren Null ist... /EDIT)

Sind sicher mehr Rechenoperationen als nötig, dafür aber Code den ich als halbwegs einfach und elegant empfinde.

Ersteinmal vielen Dank für die Antworten. Mit dem Gauss-Verfahren funktioniert das jetzt wie gewünscht.

Was genau willst du erreichen und wieso denkst du, dass die beste Lösung über den Schnittpunkt zweier Geraden führt?

Wenn die Aufgabenstellung (bzw. der Input vom User) besagt: Errechne mir (sofern vorhanden) den Schnittpunkt zweier Geraden, dann ist vermutlich die beste Lösung, den Schnittpunkt zu berechnen :D.

Den Ansatz von volkard finde ich weiterhin auch sehr interessant. Auf die Idee eine Variable durch subtrahieren zu entfernen war ich bisher noch nicht gekommen. Zeigt mir doch, dass ich mir das mal auf Papier hätte aufschreiben sollen zum Ausprobieren.

Prinzipiell ging es hier um eine Android Berechnungsapp, die verschiedene Flächen schnell berechnen kann. Diese App wollte ich nun erweitern, sodass auch dreidimensionale Körper nutzbar sind. Mit eurer Hilfe ist mir das jetzt gelungen. In diesem Sinne nochmals Danke