Der Midpoint-Circle-Algorithmus

Bresenhams Linienalgorithmus zeichnet eine gerade Linie auf einem Pixelraster nur mit Ganzzahl-Arithmetik, indem er einen Fehlerterm statt einer reellwertigen Steigung verfolgt. Der Midpoint-Circle-Algorithmus wendet denselben Trick auf Kreise an: keine Gleitkommazahlen, keine Trigonometrie, keine Quadratwurzeln — nur Ganzzahl-Additionen und eine laufende Entscheidungsvariable.

Die Idee

Ein Kreis hat eine Symmetrie, die eine Linie nicht hat: Spiegelt man einen Punkt an einer der beiden Achsen oder tauscht x und y, erhält man einen weiteren Punkt auf demselben Kreis. Der Algorithmus muss also nur die Punkte für einen 45°-Bogen berechnen — sagen wir, von der Spitze des Kreises bis zu dem Punkt, an dem der Bogen die Diagonale kreuzt — und kann jeden davon kostenlos in die anderen sieben Positionen spiegeln.

Entlang dieses Achtel-Bogens rückt x bei jedem Schritt um genau ein Pixel vor, genauso wie im Fall flacher Steigungen bei Bresenhams Linienalgorithmus, während y entweder gleich bleibt oder um eins abnimmt. Die Frage bei jedem Schritt ist dieselbe Art von Frage: Ist der echte Kreis näher an der aktuellen Zeile oder an der darunter? Der Mittelpunkt (Midpoint) im Namen des Algorithmus ist der Punkt genau zwischen diesen beiden Kandidaten-Pixeln — zu prüfen, auf welcher Seite des echten Kreises dieser Mittelpunkt liegt, entscheidet, welches Pixel gewählt wird, und diese Prüfung lässt sich über eine Ganzzahl-Entscheidungsvariable d ausdrücken, die nur +, - und Vergleiche mit null zum Aktualisieren braucht.

Implementierung

#include "plot.hpp"

void plot_circle_points(int cx, int cy, int x, int y) {
    PlotPixel(cx + x, cy + y);
    PlotPixel(cx - x, cy + y);
    PlotPixel(cx + x, cy - y);
    PlotPixel(cx - x, cy - y);
    PlotPixel(cx + y, cy + x);
    PlotPixel(cx - y, cy + x);
    PlotPixel(cx + y, cy - x);
    PlotPixel(cx - y, cy - x);
}

void midpoint_circle(int cx, int cy, int r) {
    int x = 0;
    int y = r;
    int d = 1 - r;

    while (x <= y) {
        plot_circle_points(cx, cy, x, y);
        x++;
        if (d < 0) {
            d += 2 * x + 1;
        } else {
            y--;
            d += 2 * x - 2 * y + 1;
        }
    }
}

void frame() {
    PlotBackground(250, 250, 250);
    PlotColor(30, 100, 200);
    midpoint_circle(320, 240, 180);
}

plot_circle_points ist die achtfache Spiegelung: Gegeben einen Punkt (x, y) relativ zum Mittelpunkt, zeichnet sie alle acht symmetrischen Positionen auf einmal. midpoint_circle ist die Schleife, die den Achtel-Bogen durchläuft — d startet bei 1 - r (der Midpoint-Test für den allerersten Schritt) und wird entweder um 2x + 1 oder um 2x - 2y + 1 aktualisiert, je danach, ob der Mittelpunkt innerhalb oder außerhalb des echten Kreises lag — genau wie Bresenhams Linienalgorithmus seinen Fehlerterm um 2*dy oder 2*dy - 2*dx aktualisiert. Ändere Radius oder Mittelpunkt im Code oben und drücke "Compile & Run", um einen anderen Kreis zu sehen.

Schritt für Schritt durchgerechnet

Für einen Kreis mit Radius 5 um den Ursprung startet die Schleife bei x = 0, y = 5, d = 1 - 5 = -4:

Der Achtel-Bogen ist (0,5) (1,5) (2,5) (3,4), genau dort endend, wo x die Diagonale erreicht, also zu y aufschließt. Diese vier Punkte in alle acht Oktanten zu spiegeln — x/y tauschen und Vorzeichen umkehren — ergibt den vollständigen Kreisumriss (mit ein paar Pixeln, die genau an den Achsenkreuzungen aufeinanderfallen, wo ein gespiegelter Punkt mit dem Original zusammenfällt), alles aus vier Midpoint-Tests.

Warum derselbe Trick zweimal funktioniert

Sowohl Bresenhams Linienalgorithmus als auch der Midpoint-Circle-Algorithmus reduzieren eine reellwertige Frage — "welchem Pixel ist die Kurve tatsächlich am nächsten?" — auf das Vorzeichen eines Ganzzahl-Ausdrucks, der inkrementell aktualisiert werden kann, statt bei jedem Schritt neu berechnet zu werden. Der Linienalgorithmus kommt mit einem einzigen Fehlerterm aus, weil eine Linie über ihre gesamte Länge eine Steigung hat; der Kreisalgorithmus braucht zusätzlich die achtfache Symmetrie, weil sich die Steigung eines Kreises ständig ändert — aber jeder der acht gespiegelten Oktanten teilt dieselbe flache, monotone Form, die eine einzige inkrementell aktualisierte Entscheidungsvariable ausreichen lässt.

Dieselbe Midpoint-Idee lässt sich noch weiter ausdehnen — Ellipsen brauchen zwei Entscheidungsbereiche statt einem (die Steigung überschreitet die Grenze zwischen flach und steil an einer anderen Stelle als bei einem Kreis), aber die zugrunde liegende Technik, eine echte Kurve mit einem Ganzzahl-Mittelpunkt zu vergleichen, überträgt sich direkt.

Fazit

Wo Bresenhams Algorithmus "welche Zeile ist am nächsten" in einen laufenden Vergleich verwandelt, verwandelt der Midpoint-Circle-Algorithmus "welche Zeile ist am nächsten, auf einem Achtel eines Kreises" in dieselbe Art von Vergleich — und lässt dann die Symmetrie den Rest der Arbeit kostenlos erledigen. Ein gutes Beispiel dafür, wie weit sich mit ein wenig Geometrie eine Technik strecken lässt, die ursprünglich für eine viel einfachere Form gebaut wurde.