Abtastlinien-Methode

Prinzip:

• wir arbeiten mit Abtastlinien (scanlines) von unten nach oben (oder in sonst einer Koordinatenrichtung)
• wir berechnen für jede Abtastlinie die Schnittpunkte mit dem Rand des Objekts
  (die Anzahl der Schnittpunkte ist bei geschlossenen Kurven immer gerade sofern Berührungspunkte korrekt behandelt werden)
• wir füllen jeden zweiten Abschnitt zwischen den Schnittpunkten beginnend mit dem ersten Abschnitt

Für ein einfaches Polygon verfahren wir also wie folgt:

1. wir sortieren die Ecken lexikografisch nach $y$-Koordinate und $x$-Koordinate
2. beginnend mit der kleinsten $y$-Koordinate
3. aktualisieren wir die Liste der Kanten, die von der Abtastlinie geschnitten werden, es treten vier mögliche Fälle auf:
   • zwei Kanten werden eingefügt
   • zwei Kanten werden gelöscht
   • eine Kante wird eingefügt und eine Kante wird gelöscht
   • horizontale Kanten werden ignoriert
4. wir setzen alle Pixel in dieser Abtastlinie für die schneidenden Kanten (z.B. mit einem leicht modifizierten Bresenham-Algorithmus)
5. wir füllen jeden zweiten Zwischenraum
   (falls keine Kanten mehr geschnitten werden, ist man fertig)
6. wir fahren mit der nächsten Abtastlinie bei 4. fort, falls nächste Abtastlinie keine Ecke enthält
7. wir fahren mit der nächsten Abtast-Linie bei 3. fort falls nächste Abtastlinie Ecken enthält

Die Abtastlinien-Datenstruktur hält also eine geordnete Liste von Item, die alle notwendigen Parameter und lokale Variablen einer Bresenham-Linien-Zeichen-Funktion enthält:

Für andere Objekte verfährt man analog!