sebadorn.de

Herausfinden, ob ein Punkt in einer Ellipse liegt

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.

Read more

PHP und OOP: Teil 2, Sichtbereiche (public, protected, private)

PHP Turtle

Read more

X-Factor und die Roten Augen in der Küche

Diese Folge von X-Factor war verantwortlich für ein Kind­heitstrauma von mir. Als kleiner Junge habe ich die Serie mit meiner Mutter geschaut und hatte keine Probleme mit den gruseligen Geschichten. Ja, damals waren sie gruselig und heute würde ich das Adjektiv in Anführungs­zeichen setzen, doch die Rede ist von früher. Die Geschichte von den Roten Augen hat mir eine Heidenangst eingejagt, dass ich die Knie anzog und den Kopf darin begrub.

Damals habe ich die Auflösung – WAHR oder FALSCH? – nicht mitbekommen; stimmt nicht ganz: ich wollte sie nicht sehen. Ich mein, die hätte ja WAHR sein können! Also Mutti gefragt, obwohl mir klar war, dass sie so oder so verneinen würde.

Es wurde Zeit, sich der inneren Angst zu stellen und die Wahrheit – oder doch „Wahrheit“ – zu erfahren. Das Alter hat den Spuk stark entmystifiziert und über der Folge liegt ein Schleier von billiger Produktion. Ich habe sie nochmal gesehen, die Roten Augen, kenne die Antwort und werde trotzdem gut ein­schlafen können.


5/7 – Elektrotechnik/GDS

Die unangenehmste Prüfung ist jetzt auch geschafft. Unangenehm, weil ich mich schon lange nicht mehr dazu aufraffen kann, etwas Physikbezogenes zu lernen. Diese Unmotivation geht zurück in die Oberstufe, wo ich zwar noch im Physikkurs war, diesen aber nicht ins Abi einbringen werden würde. Ich hätte auch nicht gedacht, damit noch mal im Studium konfrontiert zu werden in der Gestalt von Elektrotechnik bzw. Grundlagen der Signalverarbeitung. (Ich weiß, ist nicht das Gleiche. Der Kurs heißt GDS und zu 99% haben wir Elektrotechnik gemacht. Daher.)

Gut, solange ich nicht nachschreiben muss – und so schlecht ist es nun auch wieder nicht gelaufen – ist dieses Kapitel abgeschlossen. Hurray!


Mandelbrot-Menge b/w

Mandelbrot-Menge mit 16 Iterationen xmin: -2.0 | ymin: -2.0 | length: 4 | dimension: 450 | maxIt: 16

Mwahaha! Es läuft!

Ohne online nachzuschlagen hätte ich es aber vermutlich auch nicht geschafft. Den mathematischen Weg habe ich von Wikipedia. Aber was nützt mir das Ergebnis, wenn ich nicht verstehe, warum das so ist? Ja, einige Zeit des Pen-and-Paper-Grübelns waren die Folge.

Um zu prüfen, ob ein Programmabschnitt das macht, was er sollte, habe ich auch Fremdcode eingesetzt und geschaut, ob immernoch der gleiche Murks rauskommt. War dies der Fall, hat es nicht an diesem Abschnitt gelegen und ich konnte den Fehler woanders suchen.

Die schönste Suche waren eineinhalb Stunden nur um dann festzustellen, dass da lediglich ein „=“ zu viel war.

Matheteil

Ausgangspunkt ist diese rekursive Folge:
zn+1 = zn2 + c, z0 = 0

c ist eine komplexe Zahl und besteht aus einem Realteil Re(c) und Imaginärteil Im(c).
c = Re(c) + Im(c)
c = a + ib
i = sqrt(-1)

Betrachtet man nun z2 sieht das wie folgt aus:
z0 = 0 ? c0 = 0
z1 = 0 * 0 + c1
z2 = c1 * c1 + c2

Dies wollen wir nun aufteilen in den Realteil und Imaginärteil.
Schauen wir erst einmal auf die Rechenregeln für komplexe Zahlen:
c1 * c2 = (a1a2 - b1b2) + i(a1b2 + b1a2)
c1 + c2 = (a1 + a2) + i(b1 + b2)

Dann machen wir mal. Erst die Multiplikation:
c1 * c1 = (a1a1 - b1b1) + i(a1b1 + b1a1)
c1 * c1 = (a12 - b12) + i(2 * a1b1)

Nun noch die Addition:
c12 + c2 = (a12 - b12 + a2) + i(2 * a1b1 + b2)

Die 1. Klammer beinhaltet den Realteil, die 2. Klammer den Imaginärteil.
Re(z2) = a12 - b12 + a2
Im(z2) = 2 * a1b1 + b2

Wisst ihr was? Das formulieren wir mal allgemein:
Re(zn) = an-12 - bn-12 + an
Im(zn) = 2 * an-1bn-1 + bn

Warum haben wir das gemacht?

Im Programm müssen wir an einer wichtigen Stelle überprüfen, ob der Betrag von zn kleiner Zwei ist. Ach, wo ich ohnehin gerade dabei bin …

Formel allgemein:
|c| = sqrt(a2 + b2)
c2 = a2 + b2

Unsere Bedingung:
Gilt |zn| < 2 bzw. gilt zn2 < 4?

Zu überprüfen gilt also folgendes:
Re(zn) * Re(zn) + Im(zn) * Im(zn) < 4

Java

Der eben beschriebene Teil kann dann so aussehen:

public static int pixelValue(
	double coordX, double coordY, int maxIt) {

	int stepsGone = -1;
	double	OldReZ = 0,
		OldImZ = 0,
		NewReZ = 0,
		NewImZ = 0;

	while(NewReZ*NewReZ + NewImZ*NewImZ < 4
	&& stepsGone < maxIt) {

		OldReZ = NewReZ;
		OldImZ = NewImZ;

		NewReZ = OldReZ*OldReZ - OldImZ*OldImZ + coordX;

		NewImZ = 2*OldReZ*OldImZ + coordY;

		stepsGone++;
	}
	return maxIt - stepsGone;
}

coordX und coordY sind die aktuelle Position im Koordinatensystem. (Diese Methode wird in einer Schleife aufgerufen, die alle Koordinaten nach und nach abklappert.)

maxIt (= Iterationen) ist die Beschränkung, wie oft die Schleife durchlaufen werden soll. Da das Ergebnis in einem Graustufenbild gespeichert wird, wirkt sich diese Zahl auch auf die Anzahl verschiedener Grautöne und somit die Detailgenauigkeit aus.

Zurückgegeben wird der Grauwert des Pixels für die aktuelle Koordinate.

Zum Schluss gesagt …

So, ich hoffe, es hilft jedem mit dieser Aufgabe. Und lasst euch Eines gesagt sein: Mal eben aus dem Ärmel schütteln kann ich so etwas auch nicht. Die Formeln nachzuvollziehen hat mich mit am längsten aufgehalten. Eine große Hilfe beim Programmieren war mir dann der fertige Fremdquellcode (siehe nächster Punkt), den ich zu Vergleichs- und Testzwecken heranziehen konnte.

Hilfen für mich – Hilfen für dich

Java-Code: easy-coding.de/java-mandelbrot-menge-t464.html
Wiki: de.wikipedia.org/wiki/Mandelbrot-Menge#Iteration_eines_Bildpunktes