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