Ellipsen überfordern mich - bitte um Hilfe

[derdicki]

Hallihallo!

Eine Idee, wie man vektoriell an die Sache rangehen könnte. Sie beinhaltet zwar noch viel Rumprobiererei, aber beschränkt diese meiner Meinung nach auf das Nötigste, und dürfte relativ schnell laufen. Ich bastel gerade an einem Test…

• von den beiden Ellipsen lassen sich anhand der umgebenden Rechtecke sehr leicht die Mittelpunkte für die Ellipsen (M1 und M2) und die Achsen bestimmen.
• Aus diesen Werten lassen sich wiederum sehr leicht die beiden Brennpunkte der Ellipsen berechnen (wieder 4 Vektoren, F1 und F2 für Ellipse1, F3 und F4 für Ellipse 2). Ein online-Rechner mit knappen und verständlichen Erklärungen ist auf der Seite von Arndt Bruenner zu finden.
• Man weiss: eine Ellipse ist die Menge aller Punkte (also Vektoren), für die gilt: Die Summe der Abstände der Punkte von den beiden Brennpunkten ist gleich der grossen Achse der Ellipse.
• Jetzt geht das Probieren los, und dafür möchte ich die Menge der Punkte, die ich durchprobiere, so weit wie irgend möglich reduzieren.
• Ich weiss, dass die kürzeste Entfernung zwischen den Ellipsen immer die Verbindung ihrer Mittelpunkte ist. WENN es eine Kollision gibt, dann ist IMMER ein Punkt auf dieser Linie in der Schnittmenge enthalten.
• Man bildet nun die Differenz der beiden Ellipsenmittelpunkte zueinander und normiert diese. Man erhält einen Richtungsvektor vom M1 zu M2.
• Man läuft nun so lange diesen Richtungsvektor ab und prüft die Abstände zu den Vektoren, bis man ausserhalb der Ellipse ist (Abstandssumme zu den Brennpunkten F1 und F2 ist plötzlich grösser als die grosse Achse). Für jeden Schritt wird gleichzeitig geprüft, ob gleichzeitig die Abstandsbedingung für Ellipse2 erfüllt ist.
• Sollte während irgendeines Iterationsschrittes die Abstandsbedingung für beide Ellipsen gleichzeitig erfüllt oder übererfüllt sein, liegt eine Kollision vor.

Man kann die Anzahl der benötigten Iterationsschritte sogar noch weiter eingrenzen, indem man mit der halben Länge der kleinen Achse startet (kleinstmöglicher Abstand zum Mittelpunkt der Ellipse) und spätestens bei der halben Länge der grossen Achse endet (grösstmöglicher Abstand zum Mittelpunkt).

Das ist soweit die Idee, mit der ich gerade experimentiere.

Ich hoffe, das hilft weiter.

Beste Grüsse, Tobias Hahner

Edit noch vor dem Abschicken: Ich erkenne gerade, dass die Behauptung, die ich in Punkt 5 aufgestellt habe, nur gilt, wenn beide Ellipsen in der gleichen Lage liegen. Hier müsste ich also nochmal nachbessern…

Und noch ein Edit: es gibt insgesamt neun verschiedene leicht berechenbare Abstände zwischen den beiden Ellipsen:
M1 zu M2, F3 oder F4,
F1 zu M2, F3 oder F4,
F2 zu M2, F3 oder F4.
Man könnte einfach alle ausrechnen und die kürzeste davon durchiterieren.