Pixelgrafik     Bresenham - Linienalgorithmus

---

Bresenham - Kreis

Auch für krummlinig begrenzte Figuren gilt analog zum Linienalgorithmus die Bedingung, dass eine Berechnung von Gleikommazahlen den Algorithmus verlangsamt. Um jedoch hierbei zu einer Entscheidungsgröße zu gelangen, besteht die Notwendigkeit eine Invariante zu formulieren. Diese besteht in dem Beginn der Zeichnung, welcher auf P(0,y) festgesetzt wird. Die Bestimmung der Entscheidungsgrößen erfolgt hier über die implizite Kreisgleichung.

Es besteht die Möglichkeit die schraffierten Teile separat zu implementieren und dabei die Symmetrie des Kreises auszunutzen. Im folgenden Teilbeispiel wurde als Mittelpunkt der Wert P(200|200) angenommen. Die Parameter a und b dienen der späteren Spiegelung um die Restsektoren zu erzeugen.

  Aufgabe zum Kreisalgorithmus

 

 

01 ....... 02 03 def sector (parent, x, y, r, 200, 200, a, b, color) : 04 05 bsp = punkt() # Instanzierung der Klasse Punkt 06 07 e = 8*x + 4*y + 5 # * 4 08 while x <= y: 09 bsp.set_point(parent, a*x + 200. b*y + 200, color) 10 11 e < 0 : 12 x+= 1 13 e = e + 2*x + 3 14 else : 15 x += 1 16 y -= 1 17 e = e + 2*x - 2*y + 5 18 19 sector (0,100, 100, 200, 200, 1. 1, "yellow" 20 ............

Bresenham - Ellipse

Zur Implementierung der Ellipse ist vergleichbar zum Kreis ein symmetrisches Vorgehen notwendig. Allerdings wird in diesem Beispiel der Aufwand erheblich reduziert. Es wurde nur ein Sektor implementiert. Alle anderen sind direkt durch Spiegelungen erreichbar. Die Spiegelungen an den Achsen ergeben sich dabei relativ zum Mittelpunkt der Ellipse. Die Spiegelung an den Hauptachsen erolgt dabei über eine Kontrollgröße.

Eine mathematische Kurzdarstellung der Invariante y' = -1 sei gegeben.

  Herleitung des Algorithmus

Die Implementierung ähnelt dem Vorgehen beim Kreis. Allerdings ist im Gegensatz zum Kreis der Tangentenübergang für m = -1 als Bedingung für den Übergang zu einem anderen Sektor entscheidend. Damit ist die Implementierung der Ellipse der gegenüber dem Kreis allgemeinere Fall und schließt diesen ein. Screenshot und Source liegen vor.

  SOURCE