Schnitt von Gerade und Fkt. 3. Grades im R2

[Medium]

Eigentlich bin ich ja relativ Sattelfest in solchen Dingen, aber ich wurschtel mich hier gerade selbst ein.

Ich habe eine Gerade in Vektorform (A+t*B) und ein Catmull-Rom-Spline, welches auf seinen einzelnen Abschnitten einfach eine Funktion 3. Grades ist (a*t³+b*t²+c*t+d). Der Knackpunkt ist, dass alles im R2 passiert, also auch die a, b, c und d's in der Funktion haben 2 Koordinaten.

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). Ich hab mich beim Herleiten aber dermaßen verrannt, dass ich nicht mehr Kaffee von Kippen unterscheiden kann. "Irgendwie Gleichungssystem" ist im Moment alles was meine Neuronen noch her geben :stupid:.

Hat da grad jemand eine Kiste :idea: parat?

[Uwe Raabe]

Ich krame dann mal ganz tief in der Kiste...

Was du suchst ist die Menge aller t für die

Delphi-Quellcode:

(a*t³+b*t²+c*t+d) = (A+t*B)

.

Einfaches Umformen bringt:

Delphi-Quellcode:

a*t³ + b*t² + (c-B)*t + (d - A) = 0

Das Ganze reduziert sich somit auf die Berechnung der Nullstellen eines Polynoms 3. Grades und da habe ich auch gerade nichts brauchbares zur Hand.

[alleinherrscher]

Kannst du etwas genauer erklären, was was in deiner notation ist?

A+t*B: sind A und B zweikomponentige-Vektoren (B richtungsvektor, A Stützvektor) und t ein Skalar?

(a*t³+b*t²+c*t+d): Handelt es sich bei dem t hier ebenfalls um ein skalar und was meinst du mit "a, b, c und d's in der Funktion haben 2 Koordinaten" also sind das auch zweikomponentige Vektoren?

In diesem Fall solltest du durch gleichsetzen der beiden Terme zwei (skalare) Gleichungen dritten Grades erhalten, welche beide die selben Lösungen für t enthalten müssen.

d.h. dein Problem "reduziert" sich auf ein Lösen von "normalen" Polynomen dritten Grades?!

[edit]
Und ein Polynom dritten grades kann man wohl über die sog "Cardanischen Formeln" lösen:

http://de.wikipedia.org/wiki/Cardanische_Formel

[/edit]

[Medium]

Zitat:

Zitat von alleinherrscher

A+t*B: sind A und B zweikomponentige-Vektoren (B richtungsvektor, A Stützvektor) und t ein Skalar?

Jap.

Zitat:

Zitat von alleinherrscher

(a*t³+b*t²+c*t+d): Handelt es sich bei dem t hier ebenfalls um ein skalar und was meinst du mit "a, b, c und d's in der Funktion haben 2 Koordinaten" also sind das auch zweikomponentige Vektoren?

Jap - sogar die Begrifflichkeiten sind bei mir schon degeneriert... :)

Was unglücklich gewählt war, war das t in beiden Termen. Es handelt sich nicht um das selbe t in Gerade und Funktion! Nennen wir doch das t in der Gerade einfach mal s: A+s*B

Ich brauche also entweder eine Lösung in t oder in s, wobei das Eine ja das Andere ergeben sollte. Letztlich brauche ich auch beide Skalare um zu prüfen ob der Schnitt auf einem bestimmten Abschnitt der Funktion, und in der richtigen Orientierung der Geraden ist.

[alleinherrscher]

Du bekommst ja nach dem Gleichsetzen 2 Gleichungen mit jeweils s und t drin
Durch geschickte Addition/Subtraktion der beiden Gleichungen solltest du das s bzw das t (am einfachsten das skalar, welches zur Geradengleichung gehört) herauswerfen können oder?

[Uwe Raabe]

Zitat:

Zitat von Medium

Was unglücklich gewählt war, war das t in beiden Termen. Es handelt sich nicht um das selbe t in Gerade und Funktion! Nennen wir doch das t in der Gerade einfach mal s: A+s*B

Ich denke, es ist doch dasselbe - oder zumindest lediglich um eine Konstante verschoben. Wenn es nämlich keine Beziehung zwischen s und t gibt, entziehst du deinem System nämlich jede Lösungsmöglichkeit!

[Medium]

s und t sind über die aus der Gleichsetzung entstandenen Formel miteinander verbunden, ein einfacher Skalar wird das eher selten sein.

Und so langsam dämmert es wieder: Ich muss im gleichgesetzten Term entweder s durch einen Term in t ausdrücken, oder umgekehrt! Also genau diese Formel rausziehen, über die s und t voneinander abhängen. Das muss nun nur noch nicht nur auf dem Papier, sondern möglichst flott und automatisch im Programm passieren :gruebel:

[Uwe Raabe]

Zitat:

Zitat von Medium

s und t sind über die aus der Gleichsetzung entstandenen Formel miteinander verbunden, ein einfacher Skalar wird das eher selten sein.

Wenn du die Abhängigkeit von s und t nicht durch etwas anderes als die Gleichsetzung bekommst, kannst du das Problem nicht lösen. Du hast dann nämlich nur eine Gleichung mit zwei Unbekannten und die ist erfahrungsgemäß nicht lösbar.

[leddl]

Zitat:

Zitat von Uwe Raabe

Du hast dann nämlich nur eine Gleichung mit zwei Unbekannten und die ist erfahrungsgemäß nicht lösbar.

*hust* Na das wäre ja mal ganz was Neues :lol:
Genaugenommen ist so eine Gleichung nicht nur lösbar, sie hat sogar unendlich viele Lösungen :zwinker:

//Edit:
Gelöst wird dann üblicherweise über freie Belegung einer Variablen (wie unser Lehrer es immer so schön nannte "Raten"):
zB.:

Code:

a + b = 10 => a = 10-b
Setze b = 1: => a = 10-1 = 9
==> a = 9 / b = 1

Hupsa, eine mögliche Lösung von vielen :mrgreen:

[Uwe Raabe]

Zitat:

Zitat von leddl

Zitat:

Zitat von Uwe Raabe

Du hast dann nämlich nur eine Gleichung mit zwei Unbekannten und die ist erfahrungsgemäß nicht lösbar.

*hust* Na das wäre ja mal ganz was Neues :lol:
Genaugenommen ist so eine Gleichung nicht nur lösbar, sie hat sogar unendlich viele Lösungen :zwinker:

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

[leddl]

Zitat:

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

:gruebel: Was hat das eine mit dem anderen zu tun? Du sagtest, eine solche Gleichung wäre nicht lösbar... :roll:
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 :zwinker:

[Uwe Raabe]

Zitat:

Zitat von leddl

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

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:

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 :zwinker:

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! :bounce1: Danke euch!