nicht angemeldet Felix Riesterer
MudGuard
J o
Gunnar Bittersmann
Tabellenkalk
Richard Rüfenacht
Rolf B
Gunnar Bittersmann
derdicki
Rolf B
Gunnar Bittersmann
ottogal
Felix Riesterer
Liebe Mitlesende,
für eine primitive Kollisionserkennung zweier Bilder möchte ich folgende Idee umsetzen: Anstatt die Kanten der Rechtecke als Begrenzung der Bilder zu nehmen (Inhalte können kreisförmig sein), soll ermittelt werden, ob sich zwei Ellipsen schneiden.
Wie errechne ich, ob sich zwei Ellipsen schneiden?
Über die Ellipsen ist jeweils das Rechteck bekannt, dessen Seitenmittelpunkte die Ellipse jeweils schneidet: 
Liebe Grüße,
Felix Riesterer.
Hi,
für eine primitive Kollisionserkennung zweier Bilder möchte ich folgende Idee umsetzen: Anstatt die Kanten der Rechtecke als Begrenzung der Bilder zu nehmen (Inhalte können kreisförmig sein), soll ermittelt werden, ob sich zwei Ellipsen schneiden.
würd ich zweistufig machen:
Also prüfen, ob mind. eine der 4 Ecken zwischen den Koordinaten des anderen Rechtecks liegt.
Wenn nein, können sich die innendrin liegenden Ellipsen auch nicht schneiden.
Formeln dazu kann ich Dir leider nicht nennen …
cu,
Andreas a/k/a MudGuard
Hallihallo!
für eine primitive Kollisionserkennung zweier Bilder möchte ich folgende Idee umsetzen: Anstatt die Kanten der Rechtecke als Begrenzung der Bilder zu nehmen (Inhalte können kreisförmig sein), soll ermittelt werden, ob sich zwei Ellipsen schneiden.
Nur ein Schnellschuss, da Du von kreisförmig schreibst, und die Kollisionserkennung von Kreisen sehr einfach ist:
Wenn der Abstand der Mittelpunkte der Objekte zueinander kleiner ist als r1+r2, dann liegt eine Kollision vor.
Falls Du wirklich Ellipsen brauchst, bin ich leider auch erstmal raus...
Beste Grüsse, Tobias Hahner
Lieber derdicki,
Nur ein Schnellschuss, da Du von kreisförmig schreibst,
es ist nicht auszuschließen, dass in besonderen Fällen das Rechteck in Wirklichkeit ein Quadrat ist. Dann wäre die Ellipse ein Kreis. Ja.
und die Kollisionserkennung von Kreisen sehr einfach ist:
Da ich eine allgemeine Lösung anstrebe, möchte ich keine Sonderfälle als Untermenge implementieren. Aber trotzdem danke für den Denkanstoß.
Liebe Grüße,
Felix Riesterer.
Lieber MudGuard,
vielen Dank für Deine Ideen.
- Stufe: schneiden sich die Rechtecke?
Klingt im Moment für mich danach, als wäre das nur doppelter Aufwand, da ich davon ausgehe (ich weiß es nicht besser), dass es eine Formel gibt, die das Schneiden der Ellipsen errechnen kann. Das würde schon genügen. Dein erster Schritt sieht eher nach Fallback aus, falls ich die Formel nicht (heraus-)finde.
- Stufe: schneiden sich auch die Ellipsen?
Formeln dazu kann ich Dir leider nicht nennen …
Ach menno... ;-)
Liebe Grüße,
Felix Riesterer.
Lieber MudGuard,
- Stufe: schneiden sich die Rechtecke?
je länger ich darüber nachdenke, desto mehr muss ich Dir doch Recht geben.
Die Schnittmenge der Rechtecke, also die Menge der gemeinsamen Pixel, ist eine endliche Menge und dazu deutlich kleiner, als die gesamte Menge aller Pixel von beiden Rechtecken, und eignet sich wesentlich besser, um in den Prüffunktionen inEllipse der jeweiligen Ellipsen getestet zu werden.
Jetzt versuche ich nur noch zu verstehen, wie ich aus linker oberer Ecke, Länge und Breite eine Ellipse erstellen kann, um zu testen, ob ein gegebener Punkt in ihr liegt, oder nicht. Diese Code-Beispiele, die man so im Netz findet, verstehe ich einfach noch nicht - und wie ich diese mit meinen Daten nutzen kann.
Liebe Grüße,
Felix Riesterer.
Lieber Felix,
apropos Ellipsen und Kurven, gib das mal in deinen Browser ein:
sqrt(cos(x))*cos(300x)+sqrt(abs(x))-0.7)*(4-x*x)^0.01, sqrt(6-x^2), -sqrt(6-x^2) from -4.5 to 4.5
Herzliche Grüße
Matthias Scharwies
Lieber Matthias,
apropos Ellipsen und Kurven, gib das mal in deinen Browser ein:
sqrt(cos(x))*cos(300x)+sqrt(abs(x))-0.7)*(4-x*x)^0.01, sqrt(6-x^2), -sqrt(6-x^2) from -4.5 to 4.5
das verstehe ich nicht. "Einfach so" copy&paste in die Konsole warf einen (zu erwartenden) Fehler. In der Suchmaschine meiner Wahl ergab es keine Treffer (die kennt diesen Thread noch nicht gut genug).
Was ist das von Dir gepostete?
Liebe Grüße,
Felix Riesterer.
Hallo Felix Riesterer,
In der Suchmaschine meiner Wahl ergab es keine Treffer
Wähle eine andere. https://www.google.de/search?q=sqrt(cos(x))*cos(300x)%2Bsqrt(abs(x))-0.7)*(4-x*x)^0.01%2C+sqrt(6-x^2)%2C+-sqrt(6-x^2)+from+-4.5+to+4.5
Bis demnächst
Matthias
Hey,
den Abstand eines Punktes vom Mittelpunkt bekommst du mit:
Matthias Scharwies
Matthias Apsel
Camping_RIDER
JürgenBMath.sqrt(Math.pow(A * Math.cos(winkel), 2) + Math.pow(B * Math.sin(winkel), 2))
Dabei wären A und B die Verhältnisse der Halbachsen zum Radius eines Kreises, dessen Radius der Mittelwert zwischen großer und kleiner Halbachse ist. Und den Winkel bekommst du über die Lage der Mittelpunkte zueinander. (Nachtrag: dabei sind A sowie B Konstant und nur abhängig von dem Winkel der Hablachse zum Koordinatensystem, also laut deiner skizze: kleine Halbachse 180° und große Halbachse 0°)
Hoffe das hilft dir weiter.
Gruß
Jo
Lieber Jo,
den Abstand eines Punktes vom Mittelpunkt bekommst du mit:
Math.sqrt(Math.pow(A * Math.cos(winkel), 2) + Math.pow(B * Math.sin(winkel), 2))
dazu müsste ich einen Winkel bestimmen können. Hmm. Alles was ich habe ist das Rechteck um das HTML-Element, also offsetLeft, offsetTop, offsetWidth und offsetHeight.
@Camping_RIDER hatte per Chat noch die Idee, dass ich die Prüfung mit "Pixel liegt in der Ellipse" dadurch realisieren könnte, wenn ich meine Koordinaten in folgende Formel würfe:
( (x - mx)² / a²) + ( (y - my)² / b² ) <= 1
Dabei ist mx und my das Koordinatenpaar für den Mittelpunkt des Rechtecks, a die halbe längere Seite, b die halbe kürzere Seite, und der zu prüfende Punkt (aka Pixel) das Koordinatenpaar x und y.
Liebe Grüße,
Felix Riesterer.
@@Felix Riesterer
Wie errechne ich, ob sich zwei Ellipsen schneiden?
Die allwissende Ente spuckt mir bei der Suche nach „schnittmenge ellipsen“ u.a. dieses aus: Wie berechnet man den Schnittpunkt zweier Ellipsen geometrisch?
LLAP 🖖
Hallo,
Über die Ellipsen ist jeweils das Rechteck bekannt, dessen Seitenmittelpunkte die Ellipse jeweils schneidet:
das Schneiden ist eher ein Berühren, oder?
Gruß
Kalk
Lieber Tabellenkalk,
das Schneiden ist eher ein Berühren, oder?
aus visueller Sicht vielleicht schon, aus mathematischer Sicht ist es "haben mindestens einen gemeinsamen Punkt".
Liebe Grüße,
Felix Riesterer.
Hallo Felix Riesterer,
das Schneiden ist eher ein Berühren, oder?
aus visueller Sicht vielleicht schon, aus mathematischer Sicht ist es "haben mindestens einen gemeinsamen Punkt".
Den Begriff des Berührens gibt es auch in der Mathematik.
Bis demnächst
Matthias
@@Matthias Apsel
das Schneiden ist eher ein Berühren, oder?
aus visueller Sicht vielleicht schon, aus mathematischer Sicht ist es "haben mindestens einen gemeinsamen Punkt".
Den Begriff des Berührens gibt es auch in der Mathematik.
Aus mathematischer Sicht ist es „haben genau einen gemeinsamen Punkt“.
LLAP 🖖
Lieber Gunnar,
Den Begriff des Berührens gibt es auch in der Mathematik.
Aus mathematischer Sicht ist es „haben genau einen gemeinsamen Punkt“.
verstehe, aber es ist nur eine Untermenge der von mir zu prüfenden Möglichkeiten. Auch wenn sich die Ellipsen in mehr als nur einem Punkt "überlappen", also mehr als nur einen Punkt gemeinsam haben, will ich das feststellen können.
Liebe Grüße,
Felix Riesterer.
Hallo Felix
für eine primitive Kollisionserkennung zweier Bilder möchte ich folgende Idee umsetzen: Anstatt die Kanten der Rechtecke als Begrenzung der Bilder zu nehmen (Inhalte können kreisförmig sein), soll ermittelt werden, ob sich zwei Ellipsen schneiden.
Ich würde die Ellipsen (oder welche Formen auch immer) als geschlossene Pfade erzeugen und mit Pixelbildern füllen. Für diese Vektoren kann dann eine Kollisions-Abfrage gemacht werden.
Mit besten Grüssen
Richard
Lieber Richard,
Ich würde die Ellipsen (oder welche Formen auch immer) als geschlossene Pfade erzeugen und mit Pixelbildern füllen.
das sagt mir nichts. Ich habe <img src="bild.gif" alt="player">, was im Box-Modell zunächst ein Rechteck darstellt. Wenn der Inhalt aber eher rund ist (nicht unbedingt ein Kreis!), dann sieht es weniger nachvollziehbar aus, wenn sich zwei Rechtecksecken gerade berühren und die Kollision erkannt wird - obwohl für das Auge des Betrachters die Bildinhalte noch einen sichtbaren Abstand haben. Mit den Ellipsen gedachte ich, diesen Abstand auf ein visuell günstigeres Maß zu reduzieren.
Für diese Vektoren kann dann eine Kollisions-Abfrage gemacht werden.
Vektoren? Welche Vektoren? Du sprichst mit einem Musiker, der gerne auch mal mit JavaScript hantiert!
Liebe Grüße,
Felix Riesterer.
Hallo Felix
Vektoren? Welche Vektoren?
Denk an SVG. Es geht darum, die Rechtecke zu vermeiden, welche die Ellipsen umgeben. Wenn du die Ellipsen als Pfad wie in SVG erzeugst, sind dies Vektoren und es gibt keine umgebenden Rechtecke. Dann kollidieren direkt diese Vektoren und nicht die umgebenden Rechtecke. Damit erübrigt sich jede Berechnung.
In AdobeCC gibt es Software, welche diese Prozeduren perfekt beherrscht.
Mit besten Grüssen
Richard
Lieber Richard,
Wenn du die Ellipsen als Pfad wie in SVG erzeugst, sind dies Vektoren und es gibt keine umgebenden Rechtecke.
aha... Ich habe aber als Ausgangslage die Rechtecke. Von diesen schließe ich auf die Ellipsen. Aber gut, wahrscheinlich kann ich dann von den Ellipsen auf Vektoren schließen.
Dann kollidieren direkt diese Vektoren und nicht die umgebenden Rechtecke. Damit erübrigt sich jede Berechnung.
Das verstehe ich nicht. Ob Vektoren kollidieren, muss ich doch berechnen, oder wie soll ich Kollisionen von Elementen in meinem Spiel erkennen können?
In AdobeCC gibt es Software, welche diese Prozeduren perfekt beherrscht.
Das nützt mir aber in meinem Browsergame nichts.
Liebe Grüße,
Felix Riesterer.
Hallo Felix Riesterer,
aha... Ich habe aber als Ausgangslage die Rechtecke.
Der Mittelpunkt des Rechtecks $$M(x_M \mid y_M)$$ ist der Mittelpunkt der Ellipse. Breite a und Höhe b des Rechtecks sind das Doppelte der Halbachsen.
$$\frac{(x-x_M)^2}{a^2}+\frac{(y-y_M)^2}{b^2}= 1$$
liefert alle Punkte der Ellipse.
Umgestellt nach y die obere bzw. untere Halbellipse:
$$y=y_M \pm \frac{b}{a} \cdot \sqrt{- x^2 + 2 \cdot x_M \cdot x + a^2 - x_M^2} $$
Bis demnächst
Matthias
Lieber Matthias,
Der Mittelpunkt des Rechtecks $$M(x_M \mid y_M)$$ ist der Mittelpunkt der Ellipse.
das hatte ich bereits verstanden.
Breite a und Höhe b des Rechtecks sind das Doppelte der Halbachsen.
Ja, das meinte ich mit "die Achsen in der Ellipse, also Länge und Breite des Rechtecks".
$$\frac{(x-x_M)^2}{a^2}+\frac{(y-y_M)^2}{b^2}= 1$$
Das sieht mir sehr nach der Formel aus, die ich schon von @Camping_RIDER erhalten hatte. Gut, dass Du sie bestätigen kannst.
liefert alle Punkte der Ellipse.
Dann kann ich sie zum Testen eines beliebigen Schnittmengenpunktes der Rechtecke benutzen, ob dieser sich in der jeweiligen Ellipse befindet. Du bestätigst das also.
Umgestellt nach y die obere bzw. untere Halbellipse:
$$y=y_M \pm \frac{b}{a} \cdot \sqrt{- x^2 + 2 \cdot x_M \cdot x + a^2 - x_M^2} $$
Da ich ein Koordinatenpaar testen will, ist diese Formel wohl weniger gut geeignet, da ich y nach der Berechnung mit meiner vorhandenen Y-Koordinate vergleichen muss. Und was mache ich, wenn es nicht exakt das selbe Ergebnis ist? Da gefällt mir das <=1 (siehe oben) vom Gefühl her besser.
Ist es mit der ersteren Formel eigentlich egal, ob die Ellipse hochkant oder waagrecht ist? Und wenn ja, warum?
Liebe Grüße,
Felix Riesterer.
Aloha ;)
Den Zweifel mit hochkant und waagrecht habe ich gestreut, als ich dir die Formel gegeben habe, also ist es wohl auch an mir, das wieder auszumerzen 😂
Ist es mit der ersteren Formel eigentlich egal, ob die Ellipse hochkant oder waagrecht ist? Und wenn ja, warum?
Wikipedia kennt die Herleitung der Gleichung für den vereinfachten Fall, dass M bei (0|0) liegt.
Da unsere beliebig im Raum liegende Ellipse lediglich um die Koordinaten von M verschoben ist, genügt es, den dortigen Fall zu betrachten - wenn die Gleichung sowohl für die waagrechte als auch für die hochkante Ellipse im Ursprung gilt, dann gilt sie auch sowohl für die waagrechte als auch für die hochkante verschobene Ellipse.
Für die im Ursprung liegende waagrechte Ellipse (Brennpunkte auf der x-Achse) gilt:
$$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 $$
Wenn wir nun eine hochkante Ellipse betrachten wollen, können wir eine Koordinatentransformation vornehmen: $$ \tilde{x} = y $$ und $$ \tilde{y} = x $$. Unsere Ellipse, die im Koordinatensystem aus x,y waagrecht war, ist nun im transformierten Koordinatensystem eine hochkante (Brennpunkte auf der $$\tilde{y}$$-Achse).
Unsere Gleichung, die ja für die waagrechte Ellipse gilt, gilt dann natürlich auch in transformierten Koordinaten für eine dort hochkante Ellipse:
$$\frac{\tilde{y}^2}{a^2} + \frac{\tilde{x}^2}{b^2} = 1 $$
Es gilt für hochkante Ellipsen also dieselbe Gleichung wie oben, mit dem einen Unterschied, dass a und b vertauscht sind.
Was passiert nun, wenn wir eine hochkante Ellipse vorliegen haben, die aber "fälschlicherweise" mit den Bezeichnungen einer waagrechten Ellipse versehen - d.h. wir lesen a an der x-Achse und b an der y-Achse ab, obwohl bei einer hochkanten Ellipse eigentlich a parallel zur y-Achse und b parallel zur y-Achse liegt.
Dann haben wir doch a und b vertauscht.
Und wenn wir jetzt auch noch "fälschlicherweise" die Gleichung für waagrechte Ellipsen anwenden - mit vertauschten a und b - dann wenden wir damit implizit die gültige, korrekte Formel für hochkante Ellipsen an, da diese sich ja von der für waagrechte Ellipsen nur durch Vertauschung von a und b unterscheidet.
Dadurch verwenden wir trotz der "falschen" Beschreibung nachher wieder eine gültige Gleichung.
Somit ist die Gleichung, wenn wir 2a generell als Breite in x-Richtung und 2b generell als Breite in y-Richtung auffassen, sowohl für waagrechte als auch für hochkante Ellipsen korrekt und anwendbar.
Und da die Gleichung für die Ellipsen im Ursprung sowohl hochkant als auch waagrecht gültig ist, ist es natürlich auch die um M verschobene Gleichung
$$\frac{(x - x_m)^2}{a^2} + \frac{(y-y_m)^2}{b^2} = 1 $$
Grüße,
RIDER
Hallo Felix,
SPIEL
ah, heiliger Alan und John, wieso fallen wir immer wieder auf Fragen mit A-B Problemen herein.
Dein B-Problem, mit dem Du uns bespaßt hast, ist die Ellipsenüberlappung. Dein A-Problem, das Du mit deinen Ellipsen lösen wolltest, ist ein Kollisionstest von Sprites.
Lösen wir lieber A statt B. Du willst keine Ellipsen. Du willst eine Partitionierung deiner Sprites
Beispielsweise so:
Beachte die orangen Linien erstmal nicht - die sieht man eh nur wenn man reinzoomt, glaube ich 😀
Zerlege jedes Objekt, für das Du Kollisionstests machen willst, in eine Liste von Rechtecken. Bei dem Space-Invader hier könnten das 6 Stück sein: 2 Ohren, zwei Fußspitzen, das Gesicht und der „Hut“. Die beiden Ohren könntest Du auch zu einem Rechteck zusammenfassen; niemand verlangt, dass Partialrechtecke überlappungsfrei sind. Hinzu kommt das rote Hüllenrechteck.
Echte Ellipsen kannst Du so auch annähern, brauchst dann nur ein paar Rechtecke mehr...
Auf den ersten Blick hast Du nun dein Problem „Teste die Überlappung von 17 Sprites“ zum Problem „Teste die Überlappung von hunderten von Partitionen“ aufgeblasen. Überlappungstests haben bei naiver Programmierung quadratische Komplexität (bzw. linear, wenn Du genau ein Objekt gegen alle anderen testen willst), aber wir haben ja auch noch die Hüllrechtecke. D.h. deine Kollisionsprüfung machst Du zweistufig. Im ersten Schritt testest Du ob die Hüllrechtecke sich überlagern. Und nur, wenn das zutrifft, vergleichst Du die Partitionen. Auch da wieder zweistufig: Wenn sich SpriteA und SpriteB mit den Hüllrechtecken überlappen, fragst Du für jede Partition von A erstmal, ob sie im Hüllrechteck von B liegt, und nur wenn das zutrifft, prüfst Du gegen alle Partialrechtecke.
Das kann man bei komplexen Sprites mit vielen Partitionen auch mehrstufig gestalten, siehe die orangen Linien. Da wäre das Sprite in 3 Regionen mit je 2 Rechtecken aufgeteilt.
Wenn Du viele Sprites hast, die durcheinander wuseln und wo Du pro Sprite testen musst, ob es mit irgendeinem anderen kollidiert, kann es sinnvoll sein, vor einem generellen Kollisionstest erstmal eine nach der „Left“ Koordinate sortierte Liste der Sprites zu erstellen. Das erlaubt eine binäre Suche in der Sprite-Liste und kann bei vielen Sprites den Aufwand von O(n²) auf O(n log(n)) reduzieren (sofern Du einen Sort-Algorithmus mit O(n log(n)) verwendest und nicht Bubble-Sort). Hier muss man aber auch testen. Laufzeitkomplexität (also O(n²) vs O(n log(n)) und echte Laufzeit sind zwei paar Schuhe. Ein Algorithmus mit höherer Komplexität wird ab einem bestimmten N definitiv langsamer sein, dieses N kann aber im Bereich von 10000 oder mehr liegen.
Rolf
Lieber Rolf,
Lösen wir lieber A statt B.
ok, mal sehen.
Du willst keine Ellipsen. Du willst eine Partitionierung deiner Sprites [...]
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.
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.
Liebe Grüße,
Felix Riesterer.
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…
Rolf
Lieber Rolf,
und wenn dein Spiel so geartet ist, dass diese Vorbereitungsarbeit ineffektiv ist... Das weißt Du sicher am besten.
aktuell arbeite ich an einem Prototypen mit Smiley-Grafiken als Platzhalter. Die sind in aller Regel ziemlich genau kreisförmig. Wenn ein Smiley noch Accessoires einsetzt, wird das Bild breiter oder höher und der Kreis passt nicht mehr. Daher die Idee mit der Ellipse.
Die Formulierung „egal welche“ ist allerdings sehr weit; die Freiheitsstatue mit einer Ellipse anzunähern wäre z.B. suboptimal.
Das ist sicherlich richtig.
Ich persönlich neige zu Formulierungen in diesem Duktus, wenn ich innerlich koche bzw. mich persönlich angegriffen fühle.
Ach herrje! Ich bin Dir doch nicht böse, wenn Du mir einen neuen Lösungsweg aufzeigen willst! Nein! Im Gegenteil: Ich bin Dir sogar dankbar dafür. Nur habe ich dummerweise vergessen, das zu notieren. Da war ich wieder einmal beim Abschicken zu eilig, bevor ich meine Antwort auf atmosphärische Wechselwirkungen hin untersucht habe.
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.
Aus meiner Sicht heraus war Dein Lösungsweg mit neuen Problemen versehen, die ich nicht mathematisch lösen kann, sondern mit Daten. Das hat meine Erwartungshaltung nicht befriedigt. Daher habe ich diesen Weg abgelehnt. Jedoch sollte das keine prinzipielle Abwertung sein, nur eine Entscheidung aus meiner durch mein Projekt stark eingeengten Sichtweise.
Deine vielen GeoGebra-Sachen muss ich mir jetzt erst einmal in Ruhe zu Gemüte führen. Da bitte ich um Zeit, um das angemessen tun zu können. Vieles sieht auf den ersten Blick sehr faszinierend aus und verspricht, wenigstens konzeptionell in meinen Kram zu passen. Wie ich das dann implementiere, muss ich noch sehen.
Liebe Grüße,
Felix Riesterer.
Hallo Felix,
Ich bin Dir doch nicht böse
Ich bin erleichert. Danke schön.
Ich bin Dir sogar dankbar dafür.
Gern geschehen. Bin gespannt auf das Spiel, das da entsteht 😂
Rolf
Lieber Rolf,
Bin gespannt auf das Spiel, das da entsteht 😂
es handelt sich um eine Gruppenaufgabe im Informatikunterricht. Da ich meinen Schülern helfen will, mache ich das für mich natürlich auch. Gerade die Kollisionsabfrage war so ein Punkt, an dem ich für meine Schüler vorarbeiten will.
Liebe Grüße,
Felix Riesterer.
@@Felix Riesterer
Gerade die Kollisionsabfrage war so ein Punkt, an dem ich für meine Schüler vorarbeiten will.
Wenn das für uns schon (zu) hoch ist, ist es das für deine Schüler nicht erst recht?
Müssen es denn unbedingt Ellipsen sein? Geht nicht auch ein Oval so wie eine 400-Meter-Bahn im Stadion[1]: zwei Halbkreise, dazwischen ein Rechteck? Die Rechnung dürfte um einiges einfacher werden …
LLAP 🖖
Übergangsbögen vernachlässigen wir mal hier ↩︎
Tach!
Gerade die Kollisionsabfrage war so ein Punkt, an dem ich für meine Schüler vorarbeiten will.
Wenn das für uns schon (zu) hoch ist, ist es das für deine Schüler nicht erst recht?
Müssen es denn unbedingt Ellipsen sein? Geht nicht auch ein Oval so wie eine 400-Meter-Bahn im Stadion[^1]: zwei Halbkreise, dazwischen ein Rechteck? Die Rechnung dürfte um einiges einfacher werden …
Oder noch einfacher nur Rechtecke. Das muss doch sicher nicht ein 100% akkurates Programm sein. Es reicht vielleicht schon, wenn das Prinzip erkennbar ist.
dedlfix.
Hallo,
Müssen es denn unbedingt Ellipsen sein? Geht nicht auch ein Oval so wie eine 400-Meter-Bahn im Stadion[^1]: zwei Halbkreise, dazwischen ein Rechteck? Die Rechnung dürfte um einiges einfacher werden …
Oder noch einfacher nur Rechtecke. Das muss doch sicher nicht ein 100% akkurates Programm sein. Es reicht vielleicht schon, wenn das Prinzip erkennbar ist.
oder Kreise. Da kann die Kollision direkt berechnet weden. Felix schrieb ja, es ginge um runde Smilies mit Accessoires. Wenn diese Accessoires überlappen ist es noch keine Kollision, nur ein „Nasenrubeln“, erst wenn die Köpfe sich berühren, knallt's.
Gruß
Jürgen
Lieber Gunnar,
Wenn das für uns schon (zu) hoch ist, ist es das für deine Schüler nicht erst recht?
sicher. Aber dieses Detail kann ich ihnen ja schenken. Da ist so vieles, wass für sie "hoch" sein wird. Der Umgang mit dem DOM, das Verknüpfen von JS/DOM/CSS usw. Damit aber am Ende ein nettes Ergebnis steht, möchte ich sie dadurch unterstützen, dass ich ihnen in den Bereichen aushelfe, die mit Eigenheiten von Browser/DOM/JavaScript zusätzliche Probleme neben dem reinen Konzept (Modularisierung und Modellierung von Programmen/Objekten/Datentypen usw.) entstehen. Mit den Erfahrungen und Ergebnissen aus meinem Selbstversuch könnte ich dann noch vorhandene Lücken schließen. Allem voran wird es sicher die Tastatursteuerung einer Figur sein... aber mal sehen, was sie so alles von alleine lösen können. Immerhin steht bei ihnen bald das schriftliche Abitur an, da werden sie ihre Energien auf wichtigere Dinge konzentrieren.
Liebe Grüße,
Felix Riesterer.
Hallo Felix,
ich habe meine Strategie nochmal überarbeitet. Es gab vorher, gerade bei starken Größenunterschieden, ein paar Lücken.
Das Delta siehst Du im Versionsvergleich :)
Rolf
Hallo Felix
aha... Ich habe aber als Ausgangslage die Rechtecke. Von diesen schließe ich auf die Ellipsen. Aber gut, wahrscheinlich kann ich dann von den Ellipsen auf Vektoren schließen.
Die Vektoren sind die Ellipsen. Wie du die erstellst, ist nicht entscheidend. Du brauchst lediglich Software, die aus einer gezeichneten Ellipse einen Vektor erzeugt.
Dann kollidieren direkt diese Vektoren und nicht die umgebenden Rechtecke. Damit erübrigt sich jede Berechnung.
Das verstehe ich nicht. Ob Vektoren kollidieren, muss ich doch berechnen, oder wie soll ich Kollisionen von Elementen in meinem Spiel erkennen können?
Weil diese Berechnung automatisch erfolgt, wenn aus den Vektoren die darzustellende Fläche auf dem Bildschirm ermittelt wird. Die Kollision erfolgt dann nur noch, wenn sich die Ellipsen (oder welche Form auch immer) direkt berühren. Jetzt erfolgt die Kollision, wenn sich die umgebenden Rechtecke berühren. Die Kollision zweier Elemente erfolgt, wenn sich deren Flächen beginnen zu überschneiden. Bevor mit Vektoren gerechnet werden konnte, wurde zur Vereinfachung mit umgebenden Rechtecken gerechnet.
In AdobeCC gibt es Software, welche diese Prozeduren perfekt beherrscht.
Das nützt mir aber in meinem Browsergame nichts.
Die Software eignet hervorragend zum Erstellen von Browsergames. Ich wollte nur darauf hinweisen, dass auch andere Leute sich mit diesem Problem beschäftigen und bereits Lösungen haben. Mir ist bekannt, dass du diese Produkte nicht einsetzt.
Mit besten Grüssen
Richard
Hallo Felix,
ich habe auch mal ein bisschen gesucht - und irgendwer schrieb, man müsse dafür Gleichungen vierten Grades lösen. Ich fürchte, sie oder er hat recht...
Wenn ich ein Hüllrechteck (left,top,right,bottom) für eine Ellipse habe, kann ich daraus die Breite und Höhe berechnen und den Mittelpunkt. Die halbe Breite ist die X-Halbachse, die halbe Höhe ist die Y-Halbachse, der Mittelpunkt $$(x_0, y_0)$$ errechnet sich aus den entsprechenden Mittelwerten der Rechteck-Koordinaten.
Damit kann ich eine Ellipse $$E_i$$ mit Mittelpunkt $$(x_i, y_i)$$, horizontaler Halbachsenlänge $$a_i$$ und vertikaler Halbachsenlänge $$b_i$$ durch die Ellipsengleichung für kartesiche Koordinaten beschreiben:
$$\quad \quad \quad \frac{(x-x_i)^2}{a_i^2}+\frac{(y-y_i)^2}{b_i^2}=1$$
Das kann man auflösen nach y, und ich hoffe, ich habe mich nicht verrechnet:
$$\quad \quad \quad y = y_i \pm b_0\sqrt{1-\frac{1}{a_i^2}(x-x_i)^2}$$
So. Wenn ich jetzt für zwei Ellipsen $$E_i,E_j$$ wissen will, ob sie sich schneiden, muss ich das gleichsetzen und die Wurzelgleichung lösen. Dann bekomme ich null bis zwei X-Werte heraus, und zu denen gehören jeweils 2 Y-Werte. Ich brauche die aber nur insoweit, dass ich eine Probe machen muss, ob meine beim Lösen der Wurzelgleichung gefundenen X-Werte stimmen (da gibt's ja diese Werteinflation beim Quadrieren).
Die Rechnung kostet sicherlich etwas Zeit, daher ist es effizient, wenn ich vorher die Hüllrechtecke auf Überschneidung prüfe. Wenn ich in X- und Y-Richtung eine Überlappung von mehr als 50% habe, dann müssten sich die Ellipsen definitiv schneiden. Möglicherweise kann man diese Quote noch feintunen. Habe ich gar keine Überlappung, schneiden sich die Ellipsen definitiv nicht. Dazwischen muss man die Wurzelgleichung lösen. Das habe ich noch nicht durchgezogen, aber es scheint, ich müsste drei mal quadrieren und dann wäre ich bei einem Polynom sechsten Grades. Autsch, ich mach wohl noch was falsch. Es geht dann aber im Zweifel per Newton zu interpolieren.
Ist das ein Ansatz?
Rolf
@@Rolf B
Damit kann ich eine Ellipse $$E_i$$ mit Mittelpunkt $$(x_i, y_i)$$, horizontaler Halbachsenlänge $$a_i$$ und vertikaler Halbachsenlänge $$b_i$$ durch die Ellipsengleichung für kartesiche Koordinaten beschreiben:
$$\quad \quad \quad \frac{(x-x_i)^2}{a_i^2}+\frac{(y-y_i)^2}{b_i^2}=1$$
Wer sagt denn, dass die Achsen horizontal/vertikal liegen?
Die Ellipsen können beliebig gedreht sein, was die Rechnung noch unangenehmer macht.
LLAP 🖖
Hallo Gunnar,
das habe ich aus Felix' Problembeschreibung stillschweigend angenommen und hätte es explizit sagen müssen, ja.
Rolf
Lieber Rolf,
da es sich um HTML-Elemente und ihr Box-Modell handelt, sind die Ellipsen entweder waagrecht, oder senkrecht, je nachdem ob das Rechteck darum liegend oder stehend ist.
Also ich sehe gerade vor lauter Wald keine Bäume mehr. Ist Dein Ansatz wirklich effizienter, als die Schnittmenge an Pixeln der Rechtecke zu berechnen, um dann zu prüfen, ob einer der Pixel zu beiden Ellipsen gehört?
Muss ich eigentlich die Formel, die ich von @Camping_RIDER habe, bei hochkant stehenden Rechtecken anders benutzen? Im Moment dachte ich in meiner Naivität, dass ich einfach a und b (die Achsen in der Ellipse, also Länge und Breite des Rechtecks) so wähle, dass a >= b gilt, und der Rest ist dann eben die Formel...
Liebe Grüße,
Felix Riesterer.
Hallo Felix,
da war noch eine Frage offen…
Die Formel von Camping Rider hab ich schon mal irgendwo gesehen, aber weiß grad nicht wo. Eigentlich gilt für verschobene Ellipsen die (x-x0)²/a²+(y-y0)²/b² = 1 Relation. D.h. für die Punkte auf UND IN der Ellipse dann <= 1.
Bei der Formel ist die Lage der Ellipse (also a<b oder a>b) egal.
Rolf
Hallo Gunnar,
vielleicht kann man das Problem ja auch vereinfachen, wenn man vor der Schnittberechnung die Koordinaten transformiert. Schritt 1: Translation des Mittelpunktes einer Ellipse in den Ursprung; Schritt 2: Skalieren von X und Y um 1/a und 1/b, so dass Ellipse 1 der Einheitskreis wird. Ellipse 2 hat dann einen anderen Mittelpunkt und andere Halbachsen, wird aber im Allgemeinen eine Ellipse bleiben.
Wenn man natürlich voraussetzen könnte, dass die Bilder den gleichen Aspekt haben, dann habe ich nach der Transformation zwei Kreise, DANN müsste ich nur noch schauen ob der Abstand der Mittelpunkte geringer ist als die Summe der Radien.
Rolf
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…
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.
Hallo derdicki,
Ich weiss, dass die kürzeste Entfernung zwischen den Ellipsen immer die Verbindung ihrer Mittelpunkte ist.
Das gilt für Kreise. Definiere "Entfernung zwischen Ellipsen"...
WENN es eine Kollision gibt, dann ist IMMER ein Punkt auf dieser Linie in der Schnittmenge enthalten.
Nein.
Es gilt nicht mal, wenn beide Ellipsen die lange Achse in der gleichen Richtung haben.
Tut mir leid. Wäre sonst ein schöner Ansatz gewesen...
Rolf
@@Felix Riesterer
Wenn die Achsen der beiden Ellipsen horizontal und vertikal liegen, sind die Ellipsen beschrieben durch
$$\displaystyle \left( \frac{x - x_1}{a_1} \right)^2 + \left( \frac{y - y_1}{b_1} \right)^2 = 1$$
und
$$\displaystyle \left( \frac{x - x_2}{a_2} \right)^2 + \left( \frac{y - y_2}{b_2} \right)^2 = 1$$
Wir verschieben das Koordinatensystem: x′ = x − x₁; y′ = y − y₁. In diesem Koordinatensystem sind die Ellipsen beschrieben durch
$$\displaystyle \left( \frac{x'}{a_1} \right)^2 + \left( \frac{y'}{b_1} \right)^2 = 1$$
und
$$\displaystyle \left( \frac{x' - \left( x_2 - x_1 \right)}{a_2} \right)^2 + \left( \frac{y' - \left( y_2 - y_1 \right)}{b_2} \right)^2 = 1$$
Wir stauchen das Koordinatensystem: x″ = x′ / a₁; y″ = y′ / b₁. In diesem Koordinatensystem sind die Ellipsen beschrieben durch
$$x''^2 + y''^2 = 1$$
und
$$\displaystyle \left(\frac{ x'' - a_1 \left(x_2 - x_1 \right)}{a_1 a_2} \right)^2 + \left(\frac{ y'' - b_1 \left(y_2 - y_1 \right)}{b_1 b_2} \right)^2 = 1$$
Wir setzen x₀ = a₁(x₂ − x₁); a = a₁a₂; y₀ = b₁(y₂ − y₁); b = b₁b₂:
$$x''^2 + y''^2 = 1$$
und
$$\displaystyle \left( \frac{x'' - x_0}{a} \right)^2 + \left( \frac{y'' - y_0}{b} \right)^2 = 1$$
Durch die Transformation des Koordinatensystens ist aus der ersten Ellipse der Einheitskreis geworden; die zweite Ellipse ist immer noch eine Ellipse (mit anderen Parametern). Dadurch haben wir das Problem vereinfacht:
Wir bestimmen den geringsten Abstand der Ellipse vom Kreis. Wir suchen den Punkt der Ellipse, der am nächsten am Mittelpunkt des Kreises, also dem Koordinatenursprung O liegt. Wenn dessen Abstand 1 ist, berühren sich Ellipse und Kreis; ist er kleiner als 1, dann schneiden sie sich.
Ellipse in Parameterdarstellung:
$$\begin{align}x'' &= a \cos t + x_0 \ \quad y'' &= b \sin t + y_0\end{align}$$
Quadratischer Abstand von O:
$$\begin{align}d^2(t) &= \left( a \cos t + x_0 \right)^2 + \left( b \sin t + y_0 \right)^2
&= a^2 \cos^2 t + 2a x_0 \cos t + x_0^2 + b^2 \sin^2 t + 2b y_0 \sin t + y_0^2\end{align}$$
Zur Bestimmung des Minimums:
$$\displaystyle \frac{\mathrm d d^2(t)}{\mathrm d t} = -2a^2 \sin t \cos t - 2a x_0 \sin t + 2b^2 \sin t \cos t + 2b y_0 \cos t = 0$$
Die Lösungen t₁ und t₂ dieser Gleichung ergeben den nächsten und den entferntesten Punkt der Ellipse von O. Wenn sowohl d²(t₁) > 1 als auch d²(t₂) > 1, schneiden oder berühren sich Ellipse und Einheitskreis nicht.
Um nur das Minimum zu erhalten, noch folgende Überlegung:
Liegt der Mittelpunkt der Ellipse im 1. Quadranten, also wenn x₀ ≥ 0 und y₀ ≥ 0, dann liegt der O nächste Punkt im linken unteren Viertel der Ellipse, also im Bereich π ≤ t ≤ ³⁄₂π.
Für den 2. Quadranten (x₀ ≤ 0, y₀ ≥ 0): rechts unten, ³⁄₂π ≤ t ≤ 2π.
Für den 3. Quadranten (x₀ ≤ 0, y₀ ≤ 0): rechts oben, 0 ≤ t ≤ ½π.
Für den 4. Quadranten (x₀ ≥ 0, y₀ ≤ 0): links oben, ½π ≤ t ≤ π.
Man kann also ξ = −|x₀| und ζ = −|y₀| nehmen und die Lösung von
$$-2a^2 \sin t \cos t - 2a \xi \sin t + 2b^2 \sin t \cos t + 2b \zeta \cos t = 0$$
für t im Bereich [0, ½π] bestimmen.
Fehlt nur noch der Weg, die (Näherungs-)Lösung dieser Gleichung zu bestimmen. An der Stelle kann jetzt jemand anders übernehmen.
LLAP 🖖
Hallo Gunnar,
Dadurch haben wir das Problem vereinfacht…
Bis dahin verfolgst Du den gleichen Ansatz wie ich gestern Nacht. Danke für die mathematische Formulierung :)
Bevor man das Minimum anwendet, muss man aber sicherstellen, dass der Mittelpunkt des Einheitskreises außerhalb der Ellipse liegt. Durch Einsetzen von $$(x'',y'')=(0,0)$$ in deine 8. Gleichung müsste sich das feststellen lassen, es müsste dafür $$(\frac{x_0}{a})^2+(\frac{y_0}{b})^2 \gt 1$$ erfüllt sein. Andernfalls würde ich vermuten, dass das Minimum zu einem falschen Ergebnis führt.
Die Quadrantenprüfung müsste man optimieren können, indem man die "untere" Ellipse zum Einheitskreis transformiert (Referenzpunkt wäre der Mittelpunkt des Hüll-Rechtecks).
Ob die Minimumsuche deiner trigonometrischen Funktion meiner Abfragekette überlegen ist, wäre nun die spannende Frage. Bei mir ist etliches an Abständen zu bestimmen und Schnittpunkte zu finden. Bei Dir könnte man noch optimieren:
$$\begin{align} & &-2a^2 \sin t \cos t - 2a \xi \sin t + 2b^2 \sin t \cos t + 2b \zeta \cos t &= 0
\Longleftrightarrow & &(b^2 - a^2) \sin t \cos t - a \xi \sin t + b \zeta \cos t &= 0 \end{align}$$
Es sieht aber trotzdem recht mühsam aus, darauf Newton anzuwenden (da müsste man noch einmal ableiten).
Rolf
@@Rolf B
Bevor man das Minimum anwendet, muss man aber sicherstellen, dass der Mittelpunkt des Einheitskreises außerhalb der Ellipse liegt.
Nö, muss man nicht.
Du hast insofern recht, dass
Wir suchen den Punkt der Ellipse, der am nächsten am Mittelpunkt des Kreises, also dem Koordinatenursprung O liegt. Wenn dessen Abstand 1 ist, berühren sich Ellipse und Kreis; ist er kleiner als 1, dann schneiden sie sich.
falsch ist. Die Ellipse kann vollständig innerhalb des Einheitskreises liegen; dann gibt es keine Schnittpunkte.
Für die Kollisionserkennung ist aber nicht relevant, ob Kreis und Ellipse (die Kurven, Ränder) gemeinsame Punkte haben, sondern ob die Flächen gemeinsame Punkte haben.
Meine Formulierung war falsch; ich hätte sagen müssen: Wenn dessen Abstand 1 ist, berühren sich Ellipse und Kreis; ist er kleiner als 1, dann überlappen sie sich.
LLAP 🖖
@@Gunnar Bittersmann
Bevor man das Minimum anwendet, muss man aber sicherstellen, dass der Mittelpunkt des Einheitskreises außerhalb der Ellipse liegt.
Nö, muss man nicht.
Öhm, muss man doch. Es kann ja auch sein, dass der Einheitskreis vollständig innerhalb der Ellipse liegt; dann gibt es keine Schnittpunkte, wohl aber eine Überlappung.
LLAP 🖖
Hallo Gunnar,
Wir stauchen das Koordinatensystem: x″ = x′ / a₁; y″ = y′ / b₁. In diesem Koordinatensystem sind die Ellipsen beschrieben durch
$$x''^2 + y''^2 = 1$$ und $$\displaystyle \left(\frac{ x'' - a_1 \left(x_2 - x_1 \right)}{a_1 a_2} \right)^2 + \left(\frac{ y'' - b_1 \left(y_2 - y_1 \right)}{b_1 b_2} \right)^2 = 1$$
Ich glaube, dass du dich hier irrst: x′ ist ja durch a₁x″ zu ersetzen, usw.
Es müsste also lauten
$$\displaystyle \left(\frac{x''- \frac{1}{a_1} \left(x_2 - x_1 \right)}{\frac{a_2}{a_1}} \right)^2 + \left(\frac{y''- \frac{1}{b_1} \left(y_2 - y_1 \right)}{\frac{b_2}{b_1}} \right)^2 = 1$$
Oder bin's ich, der sich täuscht?
@@ottogal
Ich glaube, dass du dich hier irrst: x′ ist ja durch a₁x″ zu ersetzen, usw.
Es müsste also lauten$$\displaystyle \left(\frac{x''- \frac{1}{a_1} \left(x_2 - x_1 \right)}{\frac{a_2}{a_1}} \right)^2 + \left(\frac{y''- \frac{1}{b_1} \left(y_2 - y_1 \right)}{\frac{b_2}{b_1}} \right)^2 = 1$$
Herrje, ja.
Statt ×a₁ und ×b₁ also jeweils /a₁ und /b₁ in den Formeln für x₀, a₀, y₀ und b₀.
Oder bin's ich, der sich täuscht?
Auf jeden Fall täuscht sich der TeX-Renderer. Wieso bitte sind die Klammern unterschiedlich‽
(Vermutlich, weil das b mit Oberlänge höher ist als das a. Blöd ist’s aber trotzdem, dass strukturell identische Terme unterschiedlich aussehen.)
LLAP 🖖
Hallo Felix, hallo in die Runde,
das Folgende ist wahrscheinlich eher nicht weiterführend für die ursprüngliche Fragestellung. Jedenfalls ist es eine interessante Beziehung für sich berührende Ellipsen, deshalb stelle ich es vor.
Bekanntlich (? 😉) gilt:
Die Normale in einem Ellipsenpunkt ist die Winkelhalbierende der Brennstrahlen zu diesem Punkt.
(Die "Normale" ist die zur Tangente senkrechte Gerade im Berührpunkt; "Brennstrahlen" nennt man die Verbindungsstrecken des Ellipsenpunkts mit den Brennpunkten.)
Siehe dazu z.B. Brennpunkteigenschaft bei Wikipedia.
"Anwendung" findet dies z.B. beim so gen. "Flüstergewölbe". Das ist ja auch für den Musiker von Interesse...
Berühren sich zwei Ellipsen in einem Punkt T, so haben sie in diesem die Tangente und daher auch die Normale gemeinsam.
Die Normale in T zur einen Ellipse muss daher auch in der anderen Ellipse den Winkel zwischen den Brennstrahlen zu T halbieren.
In meinem GeoGebra-Blatt "Tangentiale Ellipsen" sind der Punkt T und die Brennpunkte F1 und F2 der ersten sowie F3 und F4 der zweiten Ellipse verschiebbar; F4 ist jedoch in der Bewegung so eingeschränkt, dass der Winkel zwischen den Brennstrahlen von F4 und F3 ebenfalls von der Normalen halbiert wird.
Schaut mal rein...
Viele Grüße
ottogal
Hallo ottogal,
Spannende Sache; ich habe gerade diese Idee noch etwas in Geogebra durchexerziert. Es wäre ja schön, wenn man sagen könnte, dass die Lage von T (außerhalb/auf Umfang/innerhalb) auf die Lage der Ellipsen schließen ließe (Disjunkt/Punktberührung/Überlappung). Aber leider lässt deine Konstruktion mit T als gemeinsamem Berührpunkt nur bestimmte Ellipsenlagen zu, die Umkehrung funktioniert nicht. Ich kann Ellipsen konstruieren, die sich berühren und T nicht der Berührpunkt ist. Und man kann es so konstruieren, dass die Ellipsen disjunkt sind, und T wahlweise in der einen, der anderen oder dazwischen liegt.
Ich hatte noch eine andere Konstruktion gebastelt, die aber ebenfalls nur in Sonderfällen funktioniert: https://www.geogebra.org/m/t9KE5dxv (Gerade G1 durch Brennpunkt 1 von Ellipse 1 und Brennpunkt 1 von Ellipse 2, analog Brennpunkt 2, Schnittpunkte der Geraden mit der Ellipsenkontur bestimmen, Schnittpunkte von Gerade 1 mit den Brennpunkten 2 verbinden, Schnittpunkte von Gerade G2 mit den Brennpunkten 1 verbinden. Schnittpunkte dieser Verbinder bestimmen, Gerade G3 durch diese Schnittpunkte. Die so konstruierte Gerade SCHEINT immer durch die kürzeste Verbindung zwischen den Ellipsen zu gehen, wenn die Ellipsen sich nicht oder nur leicht überschneiden UND die Geraden 1 und 2 nicht „über kreuz“ liegen. Es gibt aber genügend Ellipsenlagen, wo die Ellipsen sich berühren und G3 knapp am Berührpunkt vorbei geht. Und es gibt etliche Lagen, wo G3 komplett in der Wallachei verschwindet.)
Ist das ein Geogebra Quirk, oder jage ich da einem Phantom nach?
Rolf
Hallo Rolf
Aber leider lässt deine Konstruktion mit T als gemeinsamem Berührpunkt nur bestimmte Ellipsenlagen zu, die Umkehrung funktioniert nicht.
Ja, es ging mir um sich berührende Ellipsen – nicht um die Entscheidung, welche gegenseitige Lagen zwei Ellipsen haben. (Insofern ein für Felix' Problem nicht sonderlich hilfreicher Beitrag.)
Ich hatte noch eine andere Konstruktion gebastelt, die aber ebenfalls nur in Sonderfällen funktioniert: https://www.geogebra.org/m/t9KE5dxv
...
Ist das ein Geogebra Quirk, oder jage ich da einem Phantom nach?
Um ehrlich zu sein, mir kommt das ein wenig vor wie Fischen im Trüben. Ich sehe nicht, welche Überlegungen dazu führten, wie du die Gerade $$g_3$$ ermittelst – außer die Vermutung, dass man damit irgendwie in die Mitte kommt und so die Hoffnung hegen kann, dort die evtl. Überschneidung der Ellipsen entscheiden zu können. (Aber vielleicht hab ich dich nur nicht richtig verstanden.)
Es ist schon interessant, wie knifflich die Geschichte ist.
Hallo ottogal,
das ist auch rein experimentell entstanden; ich habe keine Herleitung dafür. Für die Idee Einheitskreis plus Ellipse funktioniert es absolut prima. Ich bin beim tiefen Zoomen zwar auch nicht sicher, dass es exakt trifft, aber für eine praxistaugliche Sprite-Kollisionserkennung würde es reichen.
Die Nummer mit den zwei Ellipsen und $$g_3$$ war ein Experiment, um das auf 2 Ellipsen zu erweitern. Dein Begriff „Vermutung“ trifft es genau. Vielleicht beweist oder widerlegt dann in 200 Jahren die RolfB.-Vermutung und kassiert einen Preis dafür, nachdem irgendwer eine Randnotiz verfasst hat, er habe einen tollen Beweis aber gerade keine Zeit, ihn aufzuschreiben 😂 😂 😂.
Deswegen ja die Frage, ob ich einem Phantom nachjage.
Rolf
Für die Idee Einheitskreis plus Ellipse funktioniert es absolut prima.
Du hast Recht, das sieht verblüffend gut aus.
Dein Begriff „Vermutung“ trifft es genau. Vielleicht beweist oder widerlegt dann in 200 Jahren die RolfB.-Vermutung und kassiert einen Preis dafür, nachdem irgendwer eine Randnotiz verfasst hat, er habe einen tollen Beweis aber gerade keine Zeit, ihn aufzuschreiben 😂 😂 😂.
😀😀😀
Wie errechne ich, ob sich zwei Ellipsen schneiden?
Ich finde die Frage ja irgendwie spannend, muss aber zugeben, dass ich bei der Mathe hier dazu tendentiell aussteige. Bei Kreisen und Rechtecke komme ich noch mit 😉
Aber, ich wollte das Netz dazu auch mal gefragen und bin spontan auf Folgendes gestoßen, sieht mir sehr spannend aus!
Hallo Ingrid,
die Kollisionsabfrage löse ich jetzt so (live-Beispiel zum Testen dauert leider noch):
function doCollideElliptically (element1, element2) {
var ellipse1 = {
a: element1.offsetWidth,
b: element1.offsetHeight,
m: {
x: element1.offsetLeft + Math.floor(element1.offsetWidth / 2),
y: element1.offsetTop + Math.floor(element1.offsetHeight / 2)
}
},
ellipse2 = {
a: element2.offsetWidth,
b: element2.offsetHeight,
m: {
x: element2.offsetLeft + Math.floor(element2.offsetWidth / 2),
y: element2.offsetTop + Math.floor(element2.offsetHeight / 2)
}
},
isPixelInEllipse = function (pixel, ellipse) {
return (
Math.pow(pixel.x - ellipse.m.x, 2) / Math.pow(ellipse.a, 2)
+ Math.pow(pixel.y - ellipse.m.y, 2) / Math.pow(ellipse.b, 2)
<= 1
);
},
sharedPixels = [],
i, x, y;
// get pixels of intersection
for (
y = element1.offsetTop;
y < element1.offsetTop + element1.offsetHeight;
y++
) {
for (
x = element1.offsetLeft;
x < element1.offsetLeft + element1.offsetWidth;
x++
) {
// pixel inside both boxes?
if (
x >= element2.offsetLeft
&& x < element2.offsetLeft + element2.offsetWidth
&& y >= element2.offsetTop
&& y < element2.offsetTop + element2.offsetHeight
) {
sharedPixels.push({x:x, y:y});
}
}
}
// do shared pixels belong into both ellipses?
if (sharedPixels.length) {
for (i = 0; i < sharedPixels.length; i++) {
if (
isPixelInEllipse(sharedPixels[i], ellipse1)
&& isPixelInEllipse(sharedPixels[i], ellipse2)
) {
return true;
}
}
}
return false;
}
Allen an dieser sehr faszinierenden und umfangreichen Diskussion Beteiligten meinen herzlichen Dank für alle Anregungen, insbesondere auch die, die nicht (un)mittelbar zur Lösung beigetragen haben. Zusätzlich zu einer funktionierenden Kollisionsberechnung auf Ellipsenbasis habe ich jetzt ein besseres Verständnis, was es mit Ellipsen alles auf sich hat und welche Komplexitäten das Thema mit sich bringt. Es ist definitiv nicht Bestandteil dessen, was in der Schule an algebraischen und geometrischen Inhalten vermittelt wird.
Liebe Grüße,
Felix Riesterer.
Hallo Felix,
da haben wir uns den Wolf diskutiert über eine halbwegs mathematische Lösung - und was machst Du? Du tastest die Pixel ab. Naaaa gut. Sicherlich ist das für deine Schülerinnen (will ich doch hoffen!) und Schüler der eingängigste Weg.
Möglicherweise haben jetzt 3 Leute gepostet während ich das hier geschrieben habe, ich habe einige Male oben den roten Punkt gesehen :) Also bin ich ggf. redundant. Egal.
Deine Implementierung halte ich für verbesserungsfähig. Natürlich weiß ich nicht, wieviel davon durch die Verständnisgrenzen deiner Kids bedingt ist, aber WIE du die Pixel abtastest ist echt umständlich. Und deine "istPixelInEllipse" Funktion ist falsch, meine ich, du müsstest durch die Länge der HALB-Achse dividieren.
istPixelInEllipse Methode gebraucht werden. Man kann da fein mit ECMASCript Features spielen (class, let, closures), aber ich glaube das wird für Schüler zu viel. Also lieber basic bleiben...if (sharedPixels.length) ist unnötig. Das Objekt ist da, length ist definiert, es ist nur im Zweifelsfall 0. Und dann bricht die for-Schleife vor dem ersten Durchlauf ab.function Ellipse(domNode) {
this.left = domNode.offsetLeft;
this.top = domNode.offsetTop;
this.right = this.left + domNode.offsetWidth;
this.bottom = this.top + domNode.offsetHeight;
this._a = domNode.offsetWidth / 2;
this._b = domNode.offsetHeight / 2;
this._cx = this.left + this._a;
this._cy = this.top + this._b;
}
Ellipse.prototype = {
intersectRect: function(otherEllipse) {
let result = {
left: Math.max(this.left , otherEllipse.left ),
top: Math.max(this.top , otherEllipse.top ),
right: Math.min(this.right , otherEllipse.right ),
bottom: Math.min(this.bottom, otherEllipse.bottom)
};
return (result.right >= result.left && result.bottom >= result.top)
? result
: null;
},
contains: function(x, y) {
return Math.pow((x - this._cx)/this._a, 2)
+ Math.pow((y - this._cy)/this._b, 2)
<= 1;
}
};
function doCollideElliptically (element1, element2) {
let ell1 = new Ellipse(element1);
let ell2 = new Ellipse(element2);
let schnitt = ell1.intersectRect(ell2);
if (schnitt) {
for (let x=schnitt.left; x < schnitt.right; x++) {
for (let y=schnitt.height; y < schnitt.height; y++) {
if (ell1.contains(x,y) && ell2.contains(x,y)) return true;
}
}
}
return false;
}
Wenn Du deinen Kids Closures zumuten kannst, dann kannst Du contains vom Prototypen in den Konstruktor verlegen und damit die Unterstrich-Properties (pseudo-private) durch Closure-Variablen ersetzen. Statt cx und cy kannst Du natürlich auch ein Objekt c mit Eigenschaften x und y machen - aber wie gesagt, das ist ein Hotspot deiner Lösung und muss SCHNELL sein. Daher noch die fastContains Methode dazu; ich gehe davon aus, dass eine einfache Multiplikation viel schneller ist als das generische Math.pow().
function Ellipse(domNode) {
… left/top/right/bottom
let a = domNode.offsetWidth / 2, b = domNode.offsetHeight / 2;
let cx = this.left + a, cy = this.top + b;
this.contains = function(x,y) {
return Math.pow((x - cx)/a, 2) + Math.pow((y - cy)/b, 2) <= 1;
}
this.fastContains = function(x,y) {
let dx = (x-cx)/a, dy = (y-cy)/2;
return dx*dx + dy*dy <= 1;
}
}
Das war jetzt viel Zeug - und möglicherweise enthält es Fehler. Zum Testen hatte ich jetzt keine Gelegenheit. Nimm davon mit, was Du und Deine Kids verdauen können 😀
Rolf
hallo
function Ellipse(domNode) {
this.left = domNode.offsetLeft;
this.top = domNode.offsetTop;
this.right = this.left + domNode.offsetWidth;
this.left = this.top + domNode.offsetHeight;
hier wohl eher this.bottom + domNode.offsetHeight;
Hallo beatovich,
thx, fixed.
Rolf
Hi,
- Und dann ist die Endebedingung der for-Schleife sofort erfüllt.
Eine for-Schleife hat keine Ende-Bedingung. Sie endet nicht, wenn die gegebene Bedingung erfüllt ist - sie läuft so lange, wie die Bedingung erfüllt ist. Ist also eine "Weitermachen"-Bedingung.
cu,
Andreas a/k/a MudGuard
Hallo Andreas,
danke. Ich habe die Formulierung geändert.
Irgendwie hatte sich der Begriff bei mir eingefressen. Es gibt da durchaus unterschiedliche Deutungen, aber nach allen habe ich ihn falsch benutzt. Z.B. unterscheiden manche Autoren zwischen Anfangs- und Ende-Bedingung, im Sinne von abweisender (while) und einleitender (do {...} while) Schleife. Andere verwenden Ende-Bedingung so wie Du: if (bedingung) then SCHLUSS.
Rolf