Kreislinien berechnen

[MudGuard]

Hi,

Btw, kennst Du (oder jemand anders) zufällig den Algorithmus, mit dem man einen Kreis nur durch Addition und Subtraktion beschreiben kann?[1] Ich habe mir dafür schon mal die Finger wund gesucht, leider erfolglos.

"Kennen" ist übertrieben. Aber ich kann mich da an was erinnern (war noch zu C64-Zeiten).
Da ging es darum, einen Kreis Punkt für Punkt zu zeichnen.
Da gab es einen Algorithmus, mit dem ermittelt wurde, ob für den nächsten Punkt ein Schritt in X-, in Y- oder in beiden Richtungen erforderlich ist.
Das genaue Verfahren weiß ich aber nicht mehr, war aber relativ leicht in Assembler zu implementieren, muß also ohne Sinus/Cosinus ausgekommen sein.

Da wurde - wenn ich mich richtig erinnere - einmal das Quadrat des Radius berechnet (die einzige Multiplikation).

Und dann für den ersten Punkt (der war x = r, y = 0) dieser Wert für x^2 gespeichert und 0 für y^2.

Dann wurde für die weiteren Schritte jeweils berechnet (per (a+1)^2 = a^2 + 2a + 1), wie sich dieser Wert für x - 1 alleine, y + 1 alleine und x - 1  und y + 1 zusammen verändert und das Ergebnis noch jeweils mit dem Radiusquadrat verglichen.

Da x^2 (bzw. y^2) ja schon berechnet war, reichen für die Berechnung der weiteren Punkte also tatsächlich Addition und Subtraktion (2a ist zwar theoretisch eine Multiplikation, die sich aber trivial auf eine Addition zurückführen läßt).

Je nachdem, welches der 3 Ergebnisse die geringste Abweichung hatte, wurde x - 1, y + 1 oder beide verwendet.

Abgebrochen wurde, wenn x = 0 erreicht war.

Damit war ein Viertelkreis berechnet. Die anderen Viertelkreise ergaben sich jeweils durch Spiegelung der Koordinaten.

cu,
Andreas