prev up inhalt next


4.2 Scan-Line-Verfahren für Polygone

Idee:
Bewege eine waagerechte Scan-Line schrittweise von oben nach unten über das Objekt, und berechne die Schnittpunkte der Scan-Line mit dem Objekt.
1.
Sortiere alle Kanten nach ihrem größten y -Wert.
2.
Bewege die Scan-Line vom größten y -Wert bis zum kleinsten y -Wert.
3.
Für jede Position der Scan-Line


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;
}


prev up inhalt next