Ellipsen überfordern mich - bitte um Hilfe

[Rolf B]

Hallo Felix,

Dazu müsste ich meine Sprites aber alle sehr genau kennen. Meine Lösung möchte ich aber generisch gestalten, damit sie bei egal welchen Sprites grundsätzlich funktioniert.

Hm, ja. Dazu kann man vielleicht was programmieren, was aus einem Image als Vorab-Verarbeitung eine Approximation durch Rechtecke berechnet. Aber es ist natürlich nie perfekt; und wenn dein Spiel so geartet ist, dass diese Vorbereitungsarbeit ineffektiv ist... Das weißt Du sicher am besten. Die Formulierung „egal welche“ ist allerdings sehr weit; die Freiheitsstatue mit einer Ellipse anzunähern wäre z.B. suboptimal.

Deine Aufteilung in A- und B-Problem sehe ich als den Versuch an, das B-Problem, dessen Implementierung möglicherweise rechenintensiver und schwieriger zu bauen ist, durch ein anderes, simpleres Problem zu ersetzen, welches für die eingesparte Rechenleistung mehr Datenaufwand in der Erstellung erfordert.

Ich persönlich neige zu Formulierungen in diesem Duktus, wenn ich innerlich koche bzw. mich persönlich angegriffen fühle. Das bin aber ich, nicht Du. Sicherheitsrückfrage: Habe ich Dich geärgert? Bist Du sauer? Das wäre vermutlich durch Formulierungen wie „hereinfallen“ und „bespaßt“ verursacht und ich möchte mich dann gerne entschuldigen. Ein schwieriges Problem zu umgehen und dafür eine einfachere Lösung zu wählen, mit der die Aufgabe erledigt wird, finde ich übrigens überhaupt nicht verwerflich; deine Formulierung klingt aber beinah so.

Eine Alternative zu Ellipsen könnten übrigens auch Sechs- oder Achtecke sein. Was hältst Du davon?

Und ich hatte auch noch was in Geogebra zu Ellipsen gebastelt: https://ggbm.at/MWhS5SRH

Ich bin dabei von meinem Vorschlag ausgegangen, vor dem Schnitt zweier Ellipsen eine von den beiden in den Einheitskreis zu transformieren (also Verschieben des Mittelpunktes einer Ellipse nach (0,0) und dann mit (1/a, 1/b) skalieren, wobei a und b die Halbachsen sind.

Im Geogebra kannst Du die Ellipse verschieben. Da sieht man, wie viel man mittels In- und Umkreis der Ellipse sowie der Kreise um die Brennpunkte abhandeln kann. Diese Kreise sind leicht bestimmbar. Und du siehst, dass ein möglicher Berührpunkt IMMER zwischen den beiden Strecken liegt, die den Mittelpunkt des Kreises mit den Brennpunkten der Ellipsen liegen. Ein Kollisionstest könnte dann so aussehen:

• speichere vorab pro Sprite den Radius von Inkreis und Umkreis (also kleine und große Halbachse)

• bilde zunächst das Quadrat vom Abstand der Mittelpunkte (Pythagoras ohne Ziehen der Wurzel). Ist es größer als das Quadrat der Summe der Umkreisradien, überlappt sich nichts. Ist es kleiner als das Quadrat der Summe der Inkreisradien, überlappt es sich definitiv. Auf das Wurzelziehen können wir hier verzichten, da Quadrierung positiver Zahlen die Kleiner-Relation erhält.

• Test auf Überlappung der Hüll-Rechtecke ist jetzt unnötig.

• transformiere die Sprite-Ellipse, deren Mittelpunkt das kleinere Y hat, in den Einheitskreis (erst Verschieben, dann Skalieren)

• Führe die gleiche Verschiebung und Skalierung mit der anderen Sprite-Ellipse durch. Wir haben jetzt einen Einheitskreis K und eine Ellipse E.

• Sei w die Länge der waagerechten Halbachse, v die Länge der vertikalen Halbachse. Sei a=max(w,v), b=min(w,v). Sei Z der Mittelpunkt der Ellipse (=Mittelpunkt des Hüllrechtecks). Bestimme die Länge von Z

• Entartet E zum Kreis (oder beinah zum Kreis, d.h. $\displaystyle \left\vert\frac{b}{a}\right\vert < 0{,}01$ oder so), prüfe lediglich noch Z < 1+a. Wenn erfüllt -> Überlappung.

• Teste, ob der Nullpunkt in der Ellipse liegt. Setze dafür (0,0) in die Ellipsengleichung $\frac{(x-x_0)^2}{w^2}+\frac{(x-y_0)^2}{v^2}=1$ ein: Teste $\displaystyle \frac{x_Z^2}{w^2}+\frac{y_Z^2}{v^2} \le 1$. Wenn ja -> Überlappung

• Bis jetzt wurde mit vergleichsweise einfachen und schnellen Operationen eine GANZE MENGE Situationen abgefangen, der Rest sind seltenere Grenzfälle!

• Bestimme für E die lineare Exzentrizität $e=\sqrt{a^2-b^2}$ und daraus die Koordinaten der Brennpunkte F₁ und F₂. Sei m der Mindestabstand der Ellipsenbrennpunkte zum Rand, es ist m=a-e.

• teste, ob einer der Brennpunkte der Ellipse dem Kreis zu nahe kommt. Dabei nutze m; ist ein Brennpunkt dem Mittelpunkt näher als 1+m -> Überlappung

• Bestimme die Schnittpunkte der Verbindungslinien Mittelpunkt-Brennpunkt mit dem Kreis. Das ist nach der Transformation simpel: Ist F ein Brennpunkt, muss nur der Vektor OF auf Länge 1 normiert werden. Dazu teilt man seine Koordinaten durch seine Länge. Der Schnittpunkt zu F₁ sein S₁, der Schnittpunkt zu F₂ sei S₂.

• Prüfe, ob einer der beiden Schnittpunkte in der Ellipse liegt. Dazu bestimmt man die Abstände der Schnittpunkte von den Brennpunkten (Vektorlänge) und addiert sie. Ist die Summe größer als 2a, ist der Punkt außerhalb der Ellipse.

• Ist einer von beiden innerhalb -> Überlappung.

• Jetzt bleibt der blöde Rest übrig. Dazu habe ich eine Lösung, von der ich nicht sagen kann, warum sie funktioniert. Aber…

  • Schau in mein Geogebra-Blatt. Da habe ich die Verbindungen S₁F₂ und S₂F₁, sozusagen die "Überkreuz-Verbindungen" der Brennpunkte mit den oben genannten Schnittpunkten. Diese Überkreuzverbindungen schneiden sich - diesen Punkt G musst Du berechnen. Das ist lineare Algebra, ein Gleichungssystem mit 2 Variablen. Dafür darf E allerdings nicht zum Kreis entarten, aber den Fall haben wir ja schon weg. Wenn sich K und E berühren, liegt der Berührpunkt auf der Geraden OG. Merkwürdig, aber wahr. Wenn Du also den Vektor OG auf Länge 1 normierst und sein Endpunkt (im Geogebra das H) innerhalb der Ellipse liegt, hast Du eine Überscheidung. Das ist im Prinzip die Idee von Dickie, aber der lag mit den Mittelpunkten falsch.

Rolf