Bresenham-Algorithmus

Für einen Punkt $(x, y)$ sei $F (x, y) = x^{2} + y^{2} - r^{2}$

Es gilt:

$$\begin{eqnarray*} F(x, y)&=&0\mbox{ f\uml {u}r } (x, y) \mbox{ auf dem Kreis,}\\... ...>&0\mbox{ f\uml {u}r } (x, y) \mbox{ au\ss{}erhalb des Kreises,} \end{eqnarray*}$$

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.6 ).

Abbildung 3.6: Testpunkt M für Entscheidungsvariable

$\Delta = F(x + 1, y - \frac{1}{2})$

Falls	$\Delta < 0 \Rightarrow M$ liegt innerhalb $\Rightarrow (x + 1, y)$ ist ideal
	$\Delta \geq 0 \Rightarrow M$ liegt außerhalb $\Rightarrow (x + 1, y -1)$ ist ideal
Idee:	Entscheide anhand von $\Delta$, ob $y$ erniedrigt werden muß oder nicht, und rechne neues $\Delta$ aus.

$$\begin{eqnarray*} \mbox{Sei \lq\lq altes'' } \Delta & =\ F(x + 1, y - \frac{1}{2})& =... ...} + (r - \frac{1}{2})^{2} - r^{2}=\ \frac{5}{4} - r\hspace*{3cm} \end{eqnarray*}$$

Also ergibt sich:

public void drawBresenhamCircle1(CGCanvas cgc) {
  int xh, yh;
  double delta;
    
  xh = 0;                                      // Koordinaten retten
  yh = r;                        
  delta = 5.0/4.0 - r;

  while(yh >= xh) {                          // Fuer jede x-Koordinate
    cgc.setPixel(xh, yh);                    // Pixel im 2. Oktanden setzen

    if (delta < 0.0) {                       // Falls noch im Kreis
      delta+=2*xh + 3.0;                     // Abweichung aktualisieren
      xh++;                                  // naechste x-Koordinate
    }
    else {                                   // aus dem Kreis gelaufen
      delta+=2*xh - 2*yh + 5.0;              // Abweichung aktualisieren
      xh++;                                  // naechste x-Koordinate
      yh--;                                  // naechste y-Koordinate
    }
  }
}

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 2xh + 3 durch dx mit Initialwert dx = 3;
Ersetze 2xh - 2yh + 5 durch dxy mit Initialwert dxy = -2*r + 5
Es ergibt sich:

public void drawBresenhamCircle2(CGCanvas cgc) {
  int xh, yh, d, dx, dxy;
    
  xh = 0;                                    // Koordinaten retten
  yh = r;                        
  d = 1 - r;                                 // Startbedingung einstellen
  dx = 3;
  dxy = -2*r + 5;

  while(yh >= xh) {                          // Fuer jede x-Koordinate
    cgc.setPixel(xh, yh);                    // Pixel im 2. Oktanden setzen

    if (d < 0) {                             // Falls noch im Kreis
      d += dx; dx += 2; dxy += 2; xh++;      // Entscheidungsvariablen setzen
    }
    else {
      d +=dxy; dx += 2; dxy += 4; xh++; yh--;// Entscheidungsvariablen setzen
    }
  }
}

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 \cdot \sqrt{2} \cdot r$ Punkte. Verglichen mit dem Kreisumfang von $2 \cdot \pi \cdot r$ liegt dieser Wert um 10% zu tief.

public void draw(CGCanvas cgc) {
  int xh, yh, d, dx, dxy;
    
  xh = 0;                                      // Koordinaten retten
  yh = r;                        
  d = 1-r;
  dx = 3;
  dxy = -2*r + 5;

  while(yh >= xh) {                          // Fuer jede x-Koordinate
    cgc.setPixel(x+xh, y+yh);                // alle 8 Oktanden werden
    cgc.setPixel(x+yh, y+xh);                // gleichzeitig gesetzt
    cgc.setPixel(x+yh, y-xh);
    cgc.setPixel(x+xh, y-yh);
    cgc.setPixel(x-xh, y-yh);
    cgc.setPixel(x-yh, y-xh);
    cgc.setPixel(x-yh, y+xh);
    cgc.setPixel(x-xh, y+yh);

    if (d < 0) {                                 // Falls noch im Kreis
      d+=dx; dx+=2; dxy+=2; xh++;                // passend aktualisieren
    }
    else {                                       // Aus dem Kreis gelaufen
      d+=dxy; dx+=2; dxy+=4; xh++; yh--;         // passend aktualisieren
    }
  }
}

Abbildung 3.7: Vom Bresenham-Algorithmus erzeugte Kreise

Demonstration der Laufzeitunterschiede