Thomas Schödel
13.08.2003

Der Mittelpunktlinien-Algorithmus von Bresenham

Die Fallunterscheidung ist eine Methode zur Lösung mathematischer Problemstellungen. Exempel, bei denen die Lösung eines Spezialfalls auf die anderen Fälle übertragen werden kann, sind in diesem Zusammenhang besonders reizvoll. Insbesondere dann, wenn sie einen geometrischen Sachverhalt beschreiben. Der für die Darstellung von Linienobjekten durch Rasterausgabegeräte verwendete Mittelpunktlinienalgorithmus von Bresenham ist ein solches Beispiel.
 

Auf einem Blatt Papier lassen sich zwei gegebene Punkte S und T mit (S ungleich T) stets durch eine Linie miteinander verbinden - vorausgesetzt, man verfügt über Lineal und Zeichengerät. Dies ist möglich, da man die Spitze des (gut gespitzten) Bleistifts zu jeder beliebigen Stelle des Papierblatts bewegen kann. Rasterausgabegeräte, wie beispielsweise Computermonitore und Drucker, verfügen - im übertragen Sinn - nicht über diese Eigenschaft. Daher werden Verfahren zur effizienten Diskretisierung von Linien benötigt. Der von Jack Bresenham 1965 formulierte Mittelpunktlinienalgorithmus beschreibt ein solches Verfahren. Es wird aufgrund seiner hohen Effizienz auch heute noch in Grafikwerkzeugen implementiert. Mithilfe von Arbeitsblättern und einem kleinen interaktiven Programm beschäftigen sich die Lernenden in dieser Unterrichtseinheit mit den "Treppen steigenden Linien". Die Programmdatei kann für Demonstrationszwecke und/oder zur selbständigen Schülerarbeit eingesetzt werden. Die in den Arbeitsblättern enthaltenen Abbildungen stehen in einem direkten Bezug zu dem Softwareprodukt. Zusätzlich werden die Dateien eines Delphi-Projektes zur Verfügung gestellt, um (bei vorhandenen Voraussetzungen) eine Integration der informatischen Modellierung im Mathematikunterricht zu motivieren.

Kompetenzen

Inhaltliche Lernziele

Die Schülerinnen und Schüler sollen

  • das Verfahren der Fallunterscheidung zur Lösung eines Problems beschreiben und anwenden können.
  • wissen, dass Grafikobjekte für ihre Darstellung mithilfe von Rasterausgabegeräten diskretisiert werden müssen.
  • die auftretenden trivialen Fälle bei der gerasterten Darstellung von Linien (Geradenstücken) ermitteln und Lösungsmöglichkeiten benennen können.
  • die Herleitung des Mittelpunktlinienalgorithmus von Bresenham für einen Spezialfall kennen.
  • die hergeleitete Form des Mittelpunktlinienalgorithmus von Bresenham auf einen weiteren Spezialfall übertragen können.
  • begründen können, weshalb der betrachtete Algorithmus zur gerasterten Ausgabe von Linienobjekten besonders effektiv ist.
  • den Mittelpunktlinienalgorithmus von Bresenham durch ein informatisches Modell veranschaulichen (optional).

Ziele aus dem Bereich der Medienkompetenz

Die Schülerinnen und Schüler sollen

  • wissen, dass die Ausgabe von grafischen Objekten auf dem Computermonitor, auf dem Display grafikfähiger Taschenrechner und mithilfe von Druckern nur in gerasterter Form erfolgen kann.
  • wissen, dass für eine nicht gerasterte Ausgabe von Grafikobjekten ein Plotter eingesetzt werden kann.

Kurzinformation zum Unterrichtsmaterial

ThemaDer Mittelpunktlinien-Algorithmus von Bresenham - Wenn Linien Treppen steigen ...
AutorThomas Schödel
FächerInformatik, Mathematik
ZielgruppeGymnasium ab Klasse 9
Zeitraum4 bis 6 Unterrichtsstunden
Technische VoraussetzungenPC und Beamer; ein Rechner pro zwei Lernende
Programmierumgebung (optional)Delphi, Java, ...
Verlaufsplan"Wenn Linien Treppen steigen"

Didaktisch-methodischer Kommentar

Der Mittelpunktlinienalgorithmus von Bresenham kann im Mathematikunterricht bei der Betrachtung von Fallunterscheidungen oder im Informatikunterricht im Zusammenhang mit dem Schwerpunkt Grafik/Grafikverarbeitung thematisiert werden. Die zum Download angebotenen Materialien demonstrieren am Beispiel der grafischen Abbildung von Linien (Geradenstücken) die Notwendigkeit der Diskretisierung von Grafikobjekten bei ihrer Darstellung mithilfe von Rasterausgabegeräten. Weiterhin wird eine Variante für die Herleitung des Mittelpunktlinienalgorithmus von Bresenham anhand eines Spezialfalls vorgestellt. Zudem werden Möglichkeiten zur Übertragung des gefundenen Verfahrens auf die weiteren Fälle angegeben. Die Ausführungen sollen zur Thematisierung des Mittelpunktlinienalgorithmus von Bresenham im Mathematikunterricht anregen. Die auf der folgenden Seite angebotenen Materialien ergänzen das Programm zum Mittelpunkt-Linienalgorithmus, das unter Download (siehe unten) für den Einsatz unter Windows (bresenham_exe.zip) sowie Delphi (bresenham_delphi.zip) heruntergeladen werden kann.

Download

Allgemeine Infos und Materialien

bresenham_materialien.zip
 

Bresenham für Windows-Nutzer

bresenham_exe.zip
 

Bresenham für Versierte

bresenham_delphi.zip
 

Internetadresse

Informationen zum Autor

Thomas Schödel ist Lehrer für Mathematik, Chemie und Informatik und stellvertretender Schulleiter am Landesgymnasium für Hochbegabte Schwäbisch Gmünd.

  • Mehr Infos im Autorenverzeichnis
    Hier können Sie Kontakt mit Herrn Schödel aufnehmen. Zudem finden Sie hier eine Liste mit allen Lehrer-Online-Beiträgen des Autors.
Unsere Empfehlungen für Sie
 
 
Impressum | Datenschutz | Über uns | RSS-Feeds | Seite bookmarken:  del.icio.us Yahoo! My Web google Bookmarks Digg Mister Wong OneView MerklisteEmpfehlenDruckenSeitenanfang
Nicht redaktionelle Inhalte nach § 6 TMG von anderen Anbietern als Lehrer-Online werden durch den Namen des Anbieters gekennzeichnet.