Algorithmus von Bresenham
Folien in diesem Satz (4)
-
Beispiel Fall 1: Erster Oktant (0°-45°)
- Normalerweise 8 Fälle!
- Für unseren Fallt gilt:
- dx = x2 - x1 > 0
- dy = y2 - y1 > 0
- (y2 - y1)/(x2 - x1) <= 1
- x wird in jedem Schritt inkrementiert!
- y wird dann inkrementiert, wenn es den Fehler minimiert (siehe nächste Folie)
-
- Prinzip des Algorithmus:
- In jedem Schritt wird x um eins erhöht. Dann wird der Fehler zur ursprünglichen Gerade berechnet. Ist dieser grösser als 0,5 bedeutet dass, dass wir einen kleineren Fehler machen, wenn wir y auch inkrementieren. So wird für jeden Schritt entschieden, ob y gleich bleibt oder um eins erhöht wird. Ein Beispiel ist links abgebildet.
-
- Der Fehler am Anfang nach dem ersten Schritt ist dy/dx.
- Nach jedem weiteren horizontalen Schritt ändert sich der Fehler erneut um dy/dx. Wenn wir einen diagonalen Schritt machen, also y inkrementieren, verändert sich der Fehler wie folgt: dy/dx - 1
- Damit der Computer keine Fliesskommazahlen berechnen muss, können wir alles mit 2dx multiplizieren. Dann kann er das ganze nur mit Hilfe von Integern berechnen:
- Veränderung des Fehlers nach horizontalem Schritt: 2dy
- Veränderung des Fehlers nach diagonalem Schritt: 2(dy-dx)
-
- // Runde x1, x2, y1, y2 und berechne dx, dy
- // Setze e = (Fehler - 1/2)*2dx = (dy/dx - 1/2)*2dx
- e = 2dy-dx
- loop: for i=0 to dx do
- setpixel(x,y)
- if e>0
- y = y+1
- e = e - 2dx
- x = x + 1
- e = e + 2dy
- endloop