Ellipsen überfordern mich - bitte um Hilfe

[Rolf B]

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.

• Sei (l₁, t₁, r₁, b₁) das eine Hüllrechteck, und (l₂, t₂, r₂, b₂) das andere (Buchstaben stehen für left,top,right,bottom).
• Die Intersektion zweier Rechtecke muss man nicht pixelweise finden. Die Intersektion ist das Rechteck (left=max(l₁,l₂), top=max(t₁,t₂), right=min(r₁,r₂), bottom=min(b₁,b₂)). Wenn dieses Rechteck entartet (also Breite oder Höhe negativ), ist die Intersektion leer.
• In der "inEllipse" Funktion machst Du zu viel pow pow. pow ist teuer, und istPixelInEllipse ist ein Hotspot deiner Funktion. Statt $$\frac{(x-x_0)^2}{a^2}$$ rechnest Du besser $$(\frac{x-x_0}{a})^2$$.
• Wenn Du schon Ellipsenobjekte aus den HTML Elementen baust, dann könntest Du auch richtig damit arbeiten. Es könnte sinnvoll sein, dafür eine Konstruktor-Funktion zu schreiben. Und die erzeugt dann gleich ein paar Werte auf Halde, die für die 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...
• Es ist Unsinn, erst die Pixel der Schnittmenge in ein Array zu legen und das Array dann abzuklappern. Da kannst Du auch gleich die Prüfung machen. Vielleicht willst Du das als Beispiel für Aufgabentrennung haben, aber dann besser so, dass Du die Schnittintervalle berechnest und die Prüfschleife über die Schnittintervalle laufen lässt.
• Ein Test 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