The Bresenham Algorithm

Sorry, your browser does not support java.

Dieses Applet visualisiert das Zeichnen einer Linie durch den Bresenham-Algorithmus. Das Rasterbild kann in verschiedenen Vergrößerungsstufen betrachtet werden und zu einzelnen Linienpunkten werden die zwei im Algorithmus zur Wahl stehenden nächsten Rasterpunkte dargestellt, sowie ihr Mittelpunkt M.
Linie
Koordinaten
  • Der Start- und Endpunkt der Linie kann direkt mit der Maus verschoben werden. Die Eingabefelder in der Kopfzeile ermöglichen eine genauere Wahl der Koordinaten.
Rastergröße
  • Die Größe eines einzelnen Rasterpunktes läßt sich mit dem Schiebebalken einstellen.
Algorithmus
Nächste Wahl
  • Die Entscheidungsvariable E, die nichts anderes als der vertikale Abstand vom Mittelpunkt M der beiden zur Wahl stehenden Rasterpunkte ist, entscheidet anhand ihres Vorzeichens über den nächsten Linienpunkt. Die Wahlmöglichkeiten werden mitsamt des Ergebnisses dargestellt.
Iteration
  • Der Rekorder stellt für alle vorhandenen Linienpunkte den Algorithmus dar. Durch Anwahl von < und > wird auf den letzten bzw. nächsten Rasterpunkt gesprungen; |< und >| springen zum Start- und Endpunkt der Linie.

  • Der Algorithmus läßt sich anhand der Checkbox auto animieren. Die Richtung der Animation kann durch Drücken von < und > festgelegt und der Ablauf mithilfe der Checkbox fast beschleunigt werden.
1. Schritt: Die Linie
Geben Sie mit der Maus geeignete Koordinaten der Linie ein und lesen Sie sie in den Eingabefeldern ab. Modifizieren Sie dort direkt die Werte.

Drücken Sie auf die Rekordertasten < und >, um den Ablauf des Bresenham-Algorithmus kennenzulernen. Stellen Sie den Ablauf mit auto auf automatischen Weiterschalten.

2. Schritt: Der Algorithmus
Vergrößern Sie nun den Zoom und damit die Darstellung der Rasterpunkte. Schalten Sie wieder durch nochmaliges Drücken von auto in den Einzelschritt-Modus und plazieren die Linie geeignet.
Betrachten Sie, welche beiden Rasterpunkte für den jeweils aktuellen Linienpunkt zur Wahl stehen und wie die Lage des Mittelpunktes M der beiden Rasterpunkte diese Wahl entscheidet. Sie werden bemerken, daß allein das Vorzeichen des Abstandes E, der die vertikale Entfernung von M zur realen Linie darstellt, darüber entscheidet. Wie läßt sich E inkrementell berechnen? Sehen Sie dazu seinen Startwert und einen Zwischenwert an.
Verallgemeinern Sie schließlich ihre Überlegungen auf Linien mit beliebigen Steigungen und Richtungen. Insbesondere sind Linien mit Steigungen > 1 interessant und solche, deren Startpunkt rechts von ihrem Endpunkt liegt.