sebadorn

Herausfinden, ob ein Punkt in einer Ellipse liegt

Informatik von Seba

Ein Artikel darüber, wie man herausfindet, ob ein Punkt (von einem Mausklick) innerhalb einer bestimmten geometrischen Form (hier: einer Ellipse) liegt, diese sich aber nicht im Koordinaten-Ursprung befinden und noch dazu rotiert wurden.

Das Ziel

Auf einer <canvas>-Fläche befinden sich mehrere Figuren. Klickt man auf die Fläche, soll die getroffene Figur ausgewählt werden. Die Figuren können sich sonstwo befinden und wurden unter Umständen auch rotiert.

Das Ellipsen-Objekt

Zum Zeichnen eines Ellipsen-Objektes werden ein paar Informationen benötigt. Dies sind meine Variablennamen und ihre Bedeutung:

x, y, width, height
Geben die Position auf dem Canvas und Breite/Höhe an.
rotate
Rotationswinkel, der angewendet werden soll. Als Einheit werden Rad verwendet (360° = 2π rad).
ctx
Der 2D-Kontext des Canvas, dessen Funktionen zum Zeichen verwendet werden.

Zeichnen der Ellipse

Der folgende Code stammt von Web Reflection: ellipse and circle for canvas 2d context.

draw: function() {
	var hB = ( this.width / 2 ) * .5522848,
		vB = ( this.height / 2 ) * .5522848,
		eX = this.x + this.width,
		eY = this.y + this.height,
		mX = this.x + this.width / 2,
		mY = this.y + this.height / 2;

	this.applyRotation();

	this.ctx.beginPath();
	this.ctx.moveTo( this.x, mY );
	this.ctx.bezierCurveTo( this.x, mY - vB, mX - hB, this.y, mX, this.y );
	this.ctx.bezierCurveTo( mX + hB, this.y, eX, mY - vB, eX, mY );
	this.ctx.bezierCurveTo( eX, mY + vB, mX + hB, eY, mX, eY );
	this.ctx.bezierCurveTo( mX - hB, eY, this.x, mY + vB, this.x, mY );
	this.ctx.closePath();

	this.ctx.fill();
}

Die Rotation wende ich in einer eigenen Funktion auf den Canvas-Kontext selbst an. Damit sich die Ellipse dabei nicht verschiebt, muss ihr Mittelpunkt zuerst in den Koordinaten­ursprung verschoben werden mit translate(x, y). Danach wird sie rotiert und wieder an ihre vorherige Position gesetzt.

applyRotation: function() {
	if( this.rotate != 0 ) {
		var xShift = this.x + parseInt( this.width / 2 ),
			yShift = this.y + parseInt( this.height / 2 );

		this.ctx.translate( xShift, yShift );
		this.ctx.rotate( this.rotate );
		this.ctx.translate( -xShift, -yShift );
	}
}

Wundert sich schon jemand, warum erst nach (xShift, yShift) und später nach (-xShit, -yShift) verschoben wird? Von der Logik her muss es natürlich andersherum sein und so geschieht es intern auch. Bei Funktionen wie translate() und rotate() werden entsprechend Matrizen multipliziert. Eine Besonderheit bei der Matrizenmultiplikation ist es, dass die Faktoren in umgekehrter Reihenfolge aufgelistet werden müssen, als sie dann Anwendung finden.

Liegt der Punkt innerhalb?

Ellipse mit (cx/cy), rx und ry.

Nach einigen vergeblichen Suchen und Versuchen stieß ich auf die passende mathematische Formel (Quelle). Sei (px, py) die Koordinate des Klicks, (cx, cy) der Mittelpunkt der Ellipse und rx und ry der Radius auf der entsprechenden Achse. Hier ist keine Rotation berücksichtigt! Dann gilt für einen Punkt (px, py) innerhalb der Ellipse:

(px - cx)² / rx² + (py - cy)² / ry² <= 1

Das implementieren wir nun in einer Funktion. Wie gesagt, Rotation wird dabei noch nicht berücksichtigt, sehr wohl aber Verschiebung.

posInside: function( px, py ) {
	var wh = this.width / 2,
		hh = this.height / 2,
		cx = this.x + wh,
		cy = this.y + hh;

	var rotatedCoord = this.rotateCoordinate( px, py );
	px = rotatedCoord.px;
	py = rotatedCoord.py;

	var part1 = Math.pow( ( px - cx ) / wh, 2 ),
		part2 = Math.pow( ( py - cy ) / hh, 2 );

	if( part1 + part2 <= 1 ) {
		return true;
	}

	return false;
}

Rotation der Klick-Koordinate

Um die Rotation der Ellipse noch mit einzubeziehen, bin ich hergangen und habe den Klick-Punkt um den Mittelpunkt der Ellipse in gleichem Maße wie die Ellipse selbst rotiert. Die Formel (Quelle) lautet:

px = cx + (px - cx) * cos(-α) - (py - cy) * sin(-α)
py = cy + (px - cx) * sin(-α) + (py - cy) * cos(-α)

Dabei ist α die Rotation des Elementes in rad. Der Wert ist negativ, da in der Formel und dem Code zuvor von einer unrotierten Ellipse ausgegangen wurde – was eine Rotation zurück in die Ursprungslage bedeutet.

rotateCoordinate: function( px, py ) {
	if( this.rotate != 0 ) {
		var cx = this.x + this.width / 2,
			cy = this.y + this.height / 2,
			px_translate = px - cx,
			py_translate = py - cy,
			rotateCos = Math.cos( -this.rotate ),
			rotateSin = Math.sin( -this.rotate );

		px = cx + px_translate * rotateCos - py_translate * rotateSin,
		py = cy + px_translate * rotateSin + py_translate * rotateCos;
	}

	return { px: px, py: py };
}

Das war es.

4 Kommentare

  1. avatar Twaldigas
    Also ich habe mir das jetzt bestimmt drei oder vier Mal durchgelesen und so ganz sehe ich noch nicht durch. Könntest du vielleicht mal eine Beispielseite Uploaden?

    Das mit der Rotation und der Ellipse ist mir irgendwie nicht so ganz klar. Also ich verstehe schon, was der Kern des Programm ist, was das Problem war und was du letztendlich erreichen willst. Ich weiß aber leider nicht genau, was du unter Rotation verstehst.

    Ansonsten sehr ausführlich. Nicht schlecht, dass du dich so stark damit auseinandergesetzt hast. Musstest du das auch in dein Projekt einbauen?

    Gruß Twaldigas
  2. avatar Seba
    Ja, ich habe das für mein Thesis-Projekt gebraucht. Sonst hätte ich mich damit sehr wahrscheinlich gar nicht erst auseinandergesetzt.

    Mit Rotation meine ich, dass das Element gedreht wurde. In diesem Fall z.B., dass die längliche Ellipse aus dem Bild schief steht und von links unten nach rechts oben verläuft.

    Eine kleine Demo wäre nicht schlecht, da hast du Recht. Ergänze ich vielleicht noch bei Zeit. Überhaupt sollte ich mehr anschauliche Demos zu Artikeln packen – ich habe noch genug Material für den einen oder anderen JavaScript-Artikel. :/
  3. avatar tms
    Vorzeichenfehler in der zweiten Zeile der Formel. Es müsste
    px = cx + (px – cx) * cos(-?) – (py - cy) * sin(-?)
    py = cy + (px – cx) * sin(-?) + (py – cy) * cos(-?)
    heißen
  4. avatar Seba
    Stimmt, danke für den Hinweis. Wird gleich korrigiert.

Und jetzt du

Do not fill in these four fields:







Name, Mail und URL sind freiwillige Angaben. E-Mail-Adressen werden weder veröffentlicht noch weitergegeben. Verwendbares HTML: <a href=""> <abbr title=""> <blockquote> <cite> <code> <del> <i> <em> <b> <strong>

[](/lyrauhh)