Betrachte zunächst den Verlauf eines Kreises um (0, 0) im 2. Oktanten.
Für einen Punkt (x, y) sei
F(x, y) = x2 + y2 - r2
Es gilt:
Verwende F als Entscheidungsvariable dafür, ob y erniedrigt werden muß, wenn x erhöht wird. F wird angewendet auf die Mitte M zwischen Zeile y und y - 1.
= F(x + 1, y -
)
Falls |
![]() ![]() ![]() |
![]() ![]() ![]() ![]() |
|
Idee: | Entscheide anhand von ![]() ![]() |
Also ergibt sich:
void bresenham_kreis_1 ( // zeichnet Kreis um Punkt 0,0 int r) // mit Radius r { double delta; int x, y; x=0; y=r; delta = 5.0/4.0 - r; while (y>=x) { set_pixel (new Point(x,y)); if (delta < 0.0 ) { delta += 2*x + 3.0; x++; } else { delta += 2*x - 2*y + 5.0; x++; y--; } } }
Substituiere delta durch d := delta - 1/4.
Dann ergibt sich
als neue Startbedingung: d := 5/4 - r - 1/4 = 1 - r
als neue if-Bedingung: if (d < 0)
Da d
nur ganzzahlige Werte annimmt, reicht der Vergleich mit 0.
Weitere Verbesserung:
Ersetze 2x + 3 durch dx mit Initialwert dx = 3;
Ersetze 2x - 2y + 5 durch dxy mit Initialwert
dxy = -2*r + 5
Es ergibt sich:
void bresenham_kreis_2 ( // zeichnet Kreis um Punkt 0,0 int r) // mit Radius r { int x, y, d, dx, dxy; x=0; y=r; d=1-r; dx=3; dxy=-2*r+5; while (y>=x) { set_pixel (new Point(x,y)); if (d < 0) { d += dx; dx += 2; dxy += 2; x++; } else { d += dxy; dx += 2; dxy += 4; x++; y--; } } }
Um den ganzen Kreis zu zeichnen, wird die Symmetrie zum Mittelpunkt ausgenutzt.
Die Anzahl der erzeugten Punkte des Bresenham-Algorithmus für den vollen Kreis
beträgt
4r . Punkte.
Verglichen mit dem Kreisumfang vom 2r
liegt dieser Wert um 10% zu tief.
/*************************************************************************************/ /* */ /* Bresenham-Algorithmus zum Zeichnen eines Kreises */ /* */ /*************************************************************************************/ private void bresenham_kreis ( // zeichnet mit Bresenham-Algorithmus Point p, // einen Kreis um den Punkt p int r) // mit Radius r { int x,y,d,dx,dxy; x=0; y=r; d=1-r; dx=3; dxy=-2*r+5; while (y>=x) { set_pixel( new Point( p.x+x, p.y+y) ); // alle 8 Oktanden werden set_pixel( new Point( p.x+y, p.y+x) ); // gleichzeitig gezeichnet set_pixel( new Point( p.x+y, p.y-x) ); set_pixel( new Point( p.x+x, p.y-y) ); set_pixel( new Point( p.x-x, p.y-y) ); set_pixel( new Point( p.x-y, p.y-x) ); set_pixel( new Point( p.x-y, p.y+x) ); set_pixel( new Point( p.x-x, p.y+y) ); if (d<0) { d=d+dx; dx=dx+2; dxy=dxy+2; x++; } else { d=d+dxy; dx=dx+2; dxy=dxy+4; x++; y--; } } }