Sortierung der Kanten nach ihrem größten y -Wert ergibt:
ABCFDEGHIJ
Für die momentane Scan-Linie gilt: aktive Kanten sind BDEF
Die sortierten x -Werte der Schnittpunkte
x1,x2,...,xn
ergeben die zu zeichnenden Segmente
(x1,x2),(x3,x4),...
Die Sortierung der Kanten nach ihren größten y -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 y -Wert von der Scan-Line überstrichen wird, und wird wieder entfernt, wenn die Scan-Line den anderen Endpunkt überstreicht.
Allgemein gilt, daß ein Punkt genau dann im Inneren des Polygons liegt, wenn ein von ihm ausgehender Halbstrahl die Polygonkanten ungeradzahlig oft schneidet.
Sonderfälle
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.
Dadurch wird sichergestellt, daß die Paare (x1,x2),(x3,x4),... der sortierten x -Werte der Schnittpunkte die zu zeichnenden Segmente im Inneren korrekt darstellen.
Kohärenz-Eigenschaft
Die Schnittpunkte für Scan-Line yi + 1 lassen sich mit Hilfe der Schnittpunkte von Scan-Line yi bestimmen:
Es gilt: Steigung der Geraden lautet
s = (yi - yi + 1)/(xi - xi + 1) .
Wegen
yi - yi + 1 = 1 ergibt sich
xi + 1 = xi - 1/s .
Vom Scan-Line-Algorithmus gefülltes Polygon
In der folgenden Methode scan_line_fill wird als Datenstruktur für die Liste der Polygonkanten die Klasse Edge verwendet.
/** Klasse zur Implementation einer verzeigerten Kantenliste. */
public class Edge {
/** groesste y-Koordinate der Kante. */
public int y_top;
/** Schnittpunkt der Scan-Line mit der Kante. */
public double x_int;
/** y-Ausdehnung der Kante. */
public int delta_y;
/** inverse Steigung 1/s der Kante. */
public double delta_x;
/** naechste Kante in der Kantenliste. */
public Edge next;
/** Erzeugt ein Objekt vom Typ Kante mit den uebergebenen Parametern.
* next ist die naechste Kante in der Liste. */
public Edge( int y_top,
double x_int,
int delta_y,
double delta_x,
Edge next) {
this.y_top = y_top;
this.x_int = x_int;
this.delta_y = delta_y;
this.delta_x = delta_x;
this.next = next;
}
/** Erzeugt ein Objekt vom Typ Kante mit den uebergebenen Parametern. */
public Edge( int y_top,
double x_int,
int delta_y,
double delta_x) {
this(y_top, x_int, delta_y, delta_x, null);
}
/** Erzeugt ein leeres Objekt vom Typ Kante. */
public Edge() {
this(0, 0.0, 0, 0.0, null);
}
}
/****************************************************************************************/
/* */
/* fuellt mit dem Scan-Line-Algorithmus das Innere eines Polygons */
/* */
/****************************************************************************************/
private void Insert( /* fuegt in die Liste eine Kante ein */
Edge edges, /* Beginn der Kantenliste */
Point P1, Point p2, /* einzufuegende Kante (P1,P2) */
int y_next) /* Behandlung von Sonderfaellen: */
/* siehe Prozedur Next_y */
{
int max_y, dy;
double x2, dx, max_x;
Point P2 = new Point(p2);
dx=(double)(P2.x-P1.x)/(double)(P2.y-P1.y);
x2=(double) P2.x;
if ((P2.y > P1.y) && (P2.y < y_next)) { P2.y--; x2=x2-dx; } // Sonderfaelle
if ((P2.y < P1.y) && (P2.y > y_next)) { P2.y++; x2=x2+dx; }
dy=P2.y-P1.y;
if (dy>0) { max_y = P2.y;
max_x = (double)x2;
dy++;
} else { max_y=P1.y;
max_x=(double)P1.x;
dy=1-dy;
}
Edge edge1 = edges; // Hilfsobjekt
while (edge1.next.y_top >= max_y) edge1 = edge1.next;
Edge newedge = new Edge(max_y, max_x, dy, dx, edge1.next); // einfuegen
// sortiert nach
edge1.next = newedge; // max_y
}
private int Next_y( /* liefert den y-Wert des naechsten Knoten laengs der Grenze */
/* dessen y-Koordinate verschieden ist von P[k].y */
int k, /* Index des Punktes */
Point[] Points, /* Liste von Punkten */
int n) /* Anzahl der Punkte */
{
int compare_y, new_y;
compare_y = Points[k].y;
do {
k = (k+1)%n;
new_y = Points[k].y;
} while (new_y == compare_y);
return(new_y);
}
private int Edge_Sort( /* erzeugt nach y sortierte Kantenliste */
/* und liefert den kleinsten y-Wert */
int n, /* Anzahl der Punkte */
Point[] P, /* Punkteliste */
Edge edges) /* Kantenliste */
{
int bottom_y;
Point P1;
Edge edge1 = new Edge();
edges.next=edge1;
edge1.next=null;
edges.y_top=Integer.MAX_VALUE;
edge1.y_top=-Integer.MAX_VALUE;
P1 = P[n-1];
bottom_y = P1.y;
for (int k=0; k<n; k++) {
if (P1.y != P[k].y) Insert(edges,P1,P[k],Next_y(k,P,n));
else set_dither_line(P1,P[k].x);
if (P[k].y < bottom_y) bottom_y = P[k].y;
P1 = P[k];
}
return (bottom_y);
}
private Edge Update_List_Ptr( /* aktualisiert den Zeiger auf die letzte */
/* aktive Kante und gibt ihn zurueck */
/* wegen Dekrementieren der Scan-Line */
/* werden einige Kanten aktiv */
int scan,
Edge l_act_edge)
{
while (l_act_edge.next.y_top >= scan) l_act_edge=l_act_edge.next;
return(l_act_edge);
}
private Edge Sort_Intersections ( /* sortiert die aktive Kantenliste */
Edge edges, /* Beginn der Kantenliste */
Edge l_act_edge) /* Ende der Kantenliste */
/* Liefert den ggf. modifizierten Zeiger */
/* auf die letzte aktive Kante zurueck */
{
Edge edge1, edge2, edge3;
edge2 = edges.next;
do {
edge1=edges;
while (edge1.next.x_int < edge2.next.x_int)
edge1=edge1.next;
if (edge1 != edge2) { // tausche edge1.next und edge2.next
edge3 = edge2.next.next;
edge2.next.next = edge1.next;
edge1.next = edge2.next;
edge2.next = edge3;
if (edge1.next==l_act_edge) l_act_edge=edge2;
} else edge2 = edge2.next;
} while (edge2 != l_act_edge);
return (l_act_edge);
}
private void Fill( /* generiert fuer je zwei Schnittpunkte */
/* aus der Kantenliste den Zeichne-Aufruf */
Edge edges, /* Beginn der aktuellen Kantenliste */
Edge l_act_edge, /* Ende der aktuellen Kantenliste */
int scan) /* Scanline */
{
Point Q = new Point();
do {
edges = edges.next;
Q.x = (int) (edges.x_int+0.5);
Q.y = scan;
edges = edges.next;
set_dither_line(Q,(int)(edges.x_int+0.5) );
} while (edges != l_act_edge);
}
private Edge Update_Edges( /* aktual. die aktiven Kanten in der Kantenliste */
Edge edges, /* beginnend bei edges */
Edge l_act_edge) /* und endend bei l_act_edge */
/* Kanten mit delta_y=0 werden entfernt. Der ggf. */
/* modifizierte Zeiger auf die letzte aktive Kante */
/* wird zurueckgegeben */
{
Edge prev_edge;
prev_edge = edges;
do {
edges = prev_edge.next;
if (edges.delta_y > 1) {
edges.delta_y--;
edges.x_int = edges.x_int - edges.delta_x;
prev_edge = edges;
} else
{
prev_edge.next = edges.next;
if (edges == l_act_edge) l_act_edge = prev_edge;
edges = null; /* dispose edges */
} /* if */
} while (prev_edge != l_act_edge);
return (l_act_edge);
}
private void scan_line_fill( /* Fuellt das Innere eines Polygons */
int NumPoints, /* Anzahl der Punkte */
Point[] Points) /* Liste von Punkten */
{
Edge l_act_edge;
int scan, bottom_y;
Edge edges = new Edge();
bottom_y = Edge_Sort(NumPoints, Points, edges);
l_act_edge = edges.next;
for (scan = edges.next.y_top; scan >= bottom_y; scan--) {
l_act_edge = Update_List_Ptr(scan, l_act_edge);
l_act_edge = Sort_Intersections(edges, l_act_edge);
Fill (edges, l_act_edge, scan);
l_act_edge = Update_Edges(edges, l_act_edge);
}
/* dispose dummies edges.next und edges */
edges.next = null;
edges = null;
}