Schnitt von Gerade und Fkt. 3. Grades im R2

[leddl]

Zitat von Uwe Raabe:

Na, dann viel Spaß beim Lösen. Meld dich, wenn du fertig bist...

Ich zitiere mal aus dem Original-Post:

Zitat:

Ich versuche nun einfach die 1-3 Schnittpunkte der Geraden und eines solchen Spline-Segmentes zu finden, und zwar so schnell wie möglich (also in Laufzeit).

Was hat das eine mit dem anderen zu tun? Du sagtest, eine solche Gleichung wäre nicht lösbar...
Zudem sollte es deutlich leichter sein, eine solche Gleichung in einem Programm zu lösen (und sei es auch über stures Ausprobieren) als im Kopf

[Uwe Raabe]

Zitat von leddl:

Was hat das eine mit dem anderen zu tun? Du sagtest, eine solche Gleichung wäre nicht lösbar...

Unendlich viele Lösungen oder etwas mit unendlich langer Laufzeit waren offenbar nicht das, was der OP suchte. Zugegeben, meine Aussage war vielleicht mathematisch nicht korrekt, als Antwort aber durchaus brauchbar.

Zitat von leddl:

Zudem sollte es deutlich leichter sein, eine solche Gleichung in einem Programm zu lösen (und sei es auch über stures Ausprobieren) als im Kopf

Ich behaupte mal, daß die Lösung im Kopf und in einem Programm ungefähr gleich viel Zeit braucht - vorausgesetzt Kopf und Programm halten lange genug durch.

[Medium]

Heureka! Ich habs, und es schaut erstmal massig aus, ist aber letztlich garnicht SO schwer gewesen. Für alle die mal suchen:

Gerade := G = A + s*B
Funktion := F = X*t³ + Y*t² + Z*t + W
A, B, X, Y, Z, W element von R2 (Indizes im Folgenden: A0 = x-Koordinate von A; A1 = y-Koordinate von A)
s, t element von R

F = G <=> F-G = 0
F-G = 0 <=> -A + -B*s + X*t³ + Y*t² + Z*t + W = 0

In Koordinaten aufgesplittet:
Gleichung 1: -A0 + -B0*s + X0*t³ + Y0*t² + Z0*t + W0 = 0
Gleichung 2: -A1 + -B1*s + X1*t³ + Y1*t² + Z1*t + W1 = 0

s durch t ausdrücken. Es muss die Gleichung dafür gewählt werden, in der Bx <> 0 ist. Diese gibt es, sonst wäre die Gerade keine Gerade (Richtungsvektor wäre (0, 0)) Hier für den Fall dass B0 <> 0:

s := (-A0 + X0*t³ + Y0*t² + Z0*t + W0) / B0

Einsetzen in Gleichung 2:
-A1 + X1*t³ + Y1*t² + Z1*t + W1 + (-B1/B0)*(-A0 + X0*t³ + Y0*t² + Z0*t + W0) = 0

Umformen und Gruppieren nach Potenzen von t ergibt:
((X1*B0-B1*X0)/B0)*t³ + ((Y1*B0-B1*Y0)/B0)*t² + ((Z1*B0-B1*Z0)/B0)*t + (B0*(W1-A1)+B1*(A0-W0))/B0 = 0

Da B0 nur ein Skalar auf dem gesamten Term ist, kann er komplett für die Nullstellenberechnung ausgelassen werden:
(X1*B0-B1*X0)*t³ + (Y1*B0-B1*Y0)*t² + (Z1*B0-B1*Z0)*t + B0*(W1-A1)+B1*(A0-W0) = 0

Das lässt sich dann vergleichsweise einfach mit der Cardanischen Formel lösen, so dass man 1-3 Werte für t bekommt.
Die entsprechenden s erhält man duch Einsetzen der t in obige Relation: s := (-A0 + X0*t³ + Y0*t² + Z0*t + W0) / B0

Das wichtigste ist eigentlich nur, dass man die Variante für das Bx <> 0 nimmt, sonst knallt es natürlich


Chacka! Danke euch!