3.4 Kreis

Problem:

Gegeben Mittelpunkt (x,y) und Radius r . Bestimme die ``anzuschaltenden'' Pixel für einen Kreis mit Radius r um den Punkt (x,y) .

Betrachte zunächst den Verlauf eines Kreises um (0,0) im 2. Oktanten (Abbildung 3.8 ).
Für einen Punkt (x,y) sei F(x,y) = x ² + y ² - r ²

Verlauf des Kreises im 2. Oktanden

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 (siehe Abbildung 3.9 ).

Testpunkt M für Entscheidungsvariable

= F(x + 1,y - )

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 4 · · r Punkte. Verglichen mit dem Kreisumfang von 2 · · r 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--; }
        }
}

Vom Bresenham-Algorithmus erzeugte Kreise