Exakter Schnitt von Ellipsen

[Nikolas]

Hallo

Ich habe zwei Ellipsen, von denen eine steht und deren Achsen parallel zu den Koordinatenachsen stehen.
Die andere Ellipse ist gedreht und bewegt sich entlang einer Halbgeraden. Jetzt würde ich gerne wissen, wann sie sich zum ersten Mal schneiden. Die Aufgabe klingt eigentlich nicht so heftig, ich komme aber auf keine Lösung. Mein größtes Problem, ist, dass mir keine schöne Lösung einfällt, wie ich bei zwei stehenden Ellipsen den Abstand berechnen kann. Mir fällt gerade nur ein, alle Punkte auf den Ellipsen durch zwei Winkel zu parametrisieren, dann hätte ich eine Funktion vom R^2 nach R, bei der ich dann nach einem Maximum suchen könnte, aber das dürfte etwas größer werden, und ich hoffe noch auf eine Rechnung, die ohne Ana2 funktioniert.
Ich hätte gerne den exakten Punkt, um zu verhindern, dass eine sehr schnelle ellipse einfach durch etwas hindurchfliegt, wenn ich nur eine Überprüfung am Ende eines Frames mache, ob sich die Ellipsen schneiden.

Hintergrund ist, (Überraschung!) eine Kollisionsabfrage, in einem Spiel, das ich für die Uni schreiben muss.

Für alternative Vorschläge bin ich auch offen, so lang sie den Treffpunkt sicher finden. (wenigstens in guter Näherung)

Nikolas

[Jelly]

Du könntest versuchen, die Ellipsen in Parameterdarstellung zu wählen:

Code:

x = x0 + a*cos(alpha * t)
y = y0 + b*sin(alpha * t)

Mittelpunkt (x0,yo)
Durchmesser: a und b

dein alpha läuft von 0 bi 2Pi

Wie die Gleichung aussieht, wenn die Ellipse gekippt wird, ist sicherlich auch ausfindig zu machen.

Für deine 2. Ellipse hast du also eine ähnliche Gleichung. Wenn bei x und y gleich sind, so hast du deinen (oder einen der beiden) Schnittpunkt(e).

[edit]Zeitvariable t vergessen[/edit]

[Nikolas]

Das bringt mich aber nicht weiter, da ich dann zwei Gleichungen, aber noch 3 Unbekannt habe (die beiden Winkel und ein Zeitparameter). Allerdings müsste ich aus einem der Winkel noch den anderen ausrechnen können... Damit hätte ich dann genug Gleichungen. Das werde ich dann wohl mal ausprobieren müssen.

[Jelly]

Hm, ja. Das stimmt wohl mit den 3 Variablen.

Vielleicht kannst du zusätzlich auch noch die Ellipsengleichung heranziehen:

Delphi-Quellcode:

x^2/a^2 + y^2/b^2 = 1

Aber das macht die Sache eigentlich noch komplexer.

[dizzy]

Da hast du dir ja nen Thema ausgesucht... Nach etwas Googelei vergebe ich das Prädikat: Unerwartet krass :lol:

Fazit: Nicht trivial, es läuft auf eine Gleichung 4. Grades hinaus, Infos dazu sind nicht so häufig.

Hier ist ein Forumsthread der einigermaßen weit kommt, und daraus verlinkt jemand auf dieses Paper. Der Fall in allgemeiner Lage ist gleich mal der komplexeste, bei parallelen Achsen sind wohl deutliche Vereinfachungen möglich.

Gruss,
Fabian

[Nikolas]

Auf diese Seite bin ich auch schon gestoßen.

Die Ellipsengleichung füht im Falle der Drehung auf Probleme. Wenn die Ellipse, sagen wir mal um 45 grad verdreht ist, muss man dann eine Gleichung schreiben, die von links unten nach rechts oben die untere Hälfte beschreibt (und analog oben) und die kenne ich nicht. (Am Besten mal zeichnen)

Meine Ansatz sieht jetzt so aus, dass ich beide Ellipsen in Polardarstellung darstelle, (wie in jellys erster version) auf eine muss ich noch eine Rotationsmatrix anwenden, damit sie auch verdreht ist.
Jetzt lasse ich erstmal beide Ellipsen fest im Raum. Jeder Winkel in der einen Ellipse beschreibt einen Punkt auf ihrem Rand. Zu diesem Punkt finde ich bei der anderen Ellipse einen Punkt, der diesem ersten am nächsten ist und zu diesem Punkt habe ich auch einen Winkel. Dieser zweite Winkel ist eindeutig und existiert, also muss ich ihn auch berechnen können. (Sollte auch nicht allzu fies werden, glaube ich)

Jetzt habe ich noch die beiden Gleichungen, die Jelly in seinem ersten Post erwähnt hat. Wenn ich jetzt die Bewegung einer der Ellipsen reinnehme, habe ich drei Parameter (die beiden Winkel und der Zeitparameter) und drei Gleichungen, die alle gelten müssen, wenn sich die beiden Ellipsen berühren.

Wenn ich jetzt keinen Denkfehler gemacht habe, sollte ich damit doch auf den gesuchten Parametersatz kommen, oder sieht jemand ein Problem?

Die Lösung in diesem Problem ist auf jeden Fall eindeutig und sie existiert auch. Von da her sollte sie auch findbar sein. (mit welchem Aufwand und in welcher Zeit und ob überhaupt sie anzugeben ist, weiss ich nicht, aber so schlimm sieht das Problem doch eigentlich nicht mehr aus).

Nur der Rechenaufwand ist recht hoch, von da her hoffe ich mal auf eine alternative Lösung :)