Abbildung
4.4
zeigt eine Scanline beim Durchqueren eines Polygons.
Die Sortierung der Kanten nach ihrem größten -Wert ergibt die
Folge
. Die zur Zeit aktiven Kanten sind
.
Die sortierten
-Werte der Schnittpunkte
ergeben die zu zeichnenden Segmente
Die Sortierung der Kanten nach ihren größten -Werten ermöglicht
den einfachen Aufbau und die effiziente Aktualisierung einer Liste von aktiven Kanten.
Eine Kante wird in diese Liste aufgenommen, wenn der Endpunkt mit dem größeren
-Wert
von der Scan-Line überstrichen wird, und wird wieder entfernt, wenn die Scan-Line den anderen
Endpunkt überstreicht.
Horizontale Kanten werden nicht in die Kantenliste aufgenommen. Für sie wird eine Linie gezeichnet.
Trifft die Scan-Line auf einen Polygoneckpunkt, dessen Kanten beide oberhalb oder beide unterhalb liegen, so zählt der Schnittpunkt doppelt. Trifft die Scan-Line auf einen Polygoneckpunkt, dessen Kanten oberhalb und unterhalb liegen, so zählt der Schnittpunkt nur einfach (siehe Abbildung 4.5 ).
Dadurch wird sichergestellt,
daß die Paare
der sortierten
-Werte der Schnittpunkte die zu zeichnenden
Segmente im Inneren korrekt darstellen.
Abbildung
4.6
zeigt,
wie die Schnittpunkte für Scan-Line sich mit Hilfe
der Schnittpunkte von Scan-Line
bestimmen lassen.
Es gilt: Die Steigung der Geraden lautet
.
Wegen
ergibt sich
.