✔ Kollision zweier Ellipsen

[Cymatoxa]

Hi Leute,

hier sind die Methematiker unter euch gefragt ^^
Ich hab eine Ellipsenklasse, in der der Mittelpunkt, die Höhe und die Breite gespeichert wird. Die Brennpunkte lassen sich ebenfalls berechnen (vorausgesetzt, dass ich alles richtig umgestellt habe )

    public final Point getFocus1() {
        return new Point(Math.round(x - Math.sqrt((width*width-height*height)/4)), y);
    }
    
    public final Point getFocus2() {
        return new Point(Math.round(x + Math.sqrt((width*width-height*height)/4)), y);
    }

Die Frage an euch: Wie kann ich 2 Ellipsen auf Kollision prüfen?

Grüße, Cymatoxa

 

[chmee]

Vorsicht, das ist nur ne Überlegung, rein theoretisch!
Darf man eine Elippse als gestauchten Kreis definieren?

x = width * cos(t)
y = height * sin(t)
// mit t [-pi,pi]

Nun kannst Du eine Gerade (Vektor) zwischen beiden Brennpunkten ziehen. Daraus ergibt sich der Winkel [Bogenmaß], womit Du Abstand/Position des (potentiell kollidierenden) Ellipsenpunktes errechnest. Das macht man mit beiden Ellipsen und Voilá, hast Du zwei Punkte, die miteinander in Beziehung kommen und entscheiden, ob Kollision oder nicht.

mfg chmee

 

[Cymatoxa]

Danke für deine schnelle antwort!
Das klinkt schonmal sehr gut, auch wenn ich das noch nicht 100%ig verstanden hab
Ich werde mit der Idee erstmal etwas herumspielen.
Hättest du vlt einen Rechenansatz für mich?

Grüße, Cymatoxa

 

[chmee]

Nöö, einen Rechenansatz werd ich jetzt nicht zusammenschustern. Ich hab aber noch ne simple Zeichnung angefertigt, aus der Einiges klar werden sollte.

Ich wiederhole meine Idee einfach nochmal. Wir haben zwei Ellipsen A und B. Die Verbindung der Mittelpunkte ergibt einen zweidimensionalen Vektor mit Länge und Ausrichtung. Dieser Vektor gibt uns den Abstand zwischen den Mittelpunkten - aber vor Allem den Winkel auf der jeweiligen Ellipse, um mit obiger Rechnung den potentiellen Kollisionspunkt zu bestimmen.

Wenn das getan ist, gibt es nur noch eine Abfrage:
Wenn die Summe der Abstände(Mitte-Kollisionspunkt) =<Abstand(Mittelpunkte)
ist, dann scheint eine Kollision stattzufinden.

mfg chmee

 

[Cymatoxa]

Okay, jetzt hab ich es begriffen, danke
Sowas in der Art hab ich mir auch schon überlegt, allerdings gibt es da ein Problem:

Hast du (bzw. irgendjemand im www) noch eine Idee?
Wäre sehr nett!
BTW, mein aktueller Ansatz ist, aus den Ellipsen Gleichungen zu erstellen und duch Gleichsetzten Schnittpunkte zu erhalten:

Grüße, Cymatoxa

 

[chmee]

Oh oO Du hast recht.. Ich stöber weiter in meinen Gehirnwindungen.. mfg chmee

 

[Cymatoxa]

Vielen Dank, dass du heute abend noch so viel Gehirnschmalz für mein Problem investierst

 

[genodeftest]

Kleiner Hinweis: Du solltest dich bei der Berechnung nicht auf den Mittelpunkt der Ellipse stützen, sondern auf beide Brennpunkte. Dann tritt das Problem von Post#5 nicht auf.


// EDIT:
Ich würde in deinem Fall erst mal ne Grobabschätzung der Abstände machen, d.h. überprüfen, ob die Distanz der beiden Mittelpunkte weniger als die Summe der großen Halbachsen beträgt. Nur dann ist eine Überschneidung überhaupt fraglich. Die weiteren Schritte dürften etwas rechenaufwändiger werden.

 

[Cymatoxa]

Doch, leider. Das war mein erster Ansatz.
http://s1.directupload.net/file/d/2596/crli5z6z_png.htm

 

[genodeftest]

Stimmt.

Ich fürchte, wenn du die Grobabschätzung gemacht hast, bleibt dir nur noch, verschiedene Punkte durchiterieren. Das meine ich so:
Ellipse E1, Mittelpunkt M1, Brennpunkte B1, C1, doppelte Ellipsensehne s1 (2 mal die Entfernung von B1 zum Hauptscheitel S1, T1); analog dazu E2, M2, ...

In einer Schleife gehst du im (oder gegen) den Uhrzeigersinn auf E1 (außen). Für jeden einzelnen Punkt P auf E1 testest du dann, ob d(P, B2)+d(P,C2) > 2*s2
wenn nein, schneiden sich die Ellipsen an diesem Punkt.

Die Schleife an sich müsstest du aufteilen:
Zuerst teilst du die Ellipse in 2 Teile (Punkte die zu B1 oder C1 näher liegen)
Dann iterierst du um B1 vom Winkel ?M1B1S1 bis ?M1B1T1 (oder andersrum) und um C1 von ?M1C1S1 bis ?M1C1T1. In welche Richtung du iterierst hängt davon ab, wo du S1 und T1 sowie B1 und C1 wählst.
Und ja, ich weiß, iterieren über einen Winkel ist nicht schön. Aber mir fällt leider gerade nichts besseres ein, die mathematischen Eigenschaften eine Ellipse sind mir nicht weiter bekannt als das, was man auf der dt. Wikipedia findet.

Optimierung wäre noch möglich, indem du den Winkel an der "richtigen" Seite ansetzt, ich weiß allerdings nicht wie.