Cohen-Sutherland-Algorithmus

Der Algorithmus von Cohen-Sutherland ist ein Algorithmus zum Clipping von Linien an einem Rechteck. Er ist nach seinen Erfindern Dan Cohen und Ivan Sutherland benannt. Der Algorithmus gilt als populärster, wenn auch nicht effizientester für seine Zwecke. Er eignet sich besonders für Fälle, in denen ein hoher Anteil der zu clippenden Linien inner- oder außerhalb des Rechtecks liegt.

Schritte

Zuerst werden für die beiden Endpunkte der zu zeichnenden Linie vier Flags ermittelt, die gesetzt werden, wenn sich der Endpunkt links vom Rechteck, rechts davon, darüber oder darunter befindet.

Ist keines der Flags gesetzt, dann liegen beide Endpunkte innerhalb des Rechtecks, es ist kein Clipping notwendig und die Linie kann einfach gezeichnet werden.

Illustration Clipping Maske

Wenn dieser triviale Fall nicht eintritt, werden im nächsten Schritt die einander entsprechenden Flags beider Endpunkte angesehen. Ist mindestens eines dieser Flags bei beiden Endpunkten gesetzt, so befindet sich die gesamte Linie außerhalb des Rechtecks und die Linie braucht nicht gezeichnet zu werden.

Wenn auch dieser einfache Fall nicht auftritt, wird der Schnittpunkt einer (beliebigen) Rechteck-Seite mit dem Liniensegment berechnet und der überlappende Teil erneut getestet (und evtl. gekürzt), bis schließlich beide Punkte innerhalb des Rechtecks liegen.

Implementierung

Das folgende Programm gibt ein Beispiel einer Implementierung des Cohen-Sutherland-Algorithmus' in C++, anhand dessen man die Funktionsweise gut nachvollziehen kann.

/*----------------------------------------------------------------------------------------
Clipping der zwei X,Y Koordinaten einer Linie innerhalb eines zweidimensionalen 
Clipping Rechtecks XMin,YMin,XMax,YMax nach Cohen Sutherland.

Nach Ablauf der Funktion sind die Koordinaten der beiden Punkte so geclippt, dass sie
innerhalb des Clipping Rechtecks liegen und der Linie entsprechen, die übrig bleibt,
wenn man die außerhalb liegenden Teile abschneidet.
 
Falls kein Teil der Linie das Clipping Rechteck überstreicht, liefert die Funktion den
Wert FALSE zurück.
 
x1,y1   : Koordinate des Anfangspunktes der Linie
x2,y2   : Koordinate des Endpunktes     der Linie
return  : FALSE Linie ist komplett geclippt und braucht nicht gezeichnet zu werden.
          TRUE  Die Koordinaten sind geclippt und die Linie kann jetzt gezeichnet werden
------------------------------------------------------------------------------------------*/
#define CLIPLEFT  1  // Binär   0001
#define CLIPRIGHT 2  //         0010
#define CLIPLOWER 4  //         0100
#define CLIPUPPER 8  //         1000

int clipline(int &x1,int &y1,int &x2,int &y2)
{
int K1=0,K2=0;             // Variablen mit je 4 Flags für rechts, links, oben, unten.
int dx,dy;

 dx=x2-x1;                 // Die Breite der Linie vorberechnen für spätere Koordinaten Interpolation
 dy=y2-y1;                 // Die Höhe   der Linie vorberechnen für spätere Koordinaten Interpolation
 
// Die folgende Abfrage setzt die Flags CLIPLEFT,CLIPRIGHT,CLIPUP,CLIPDOWN, falls die Koordinate
// auf einer oder zwei Seiten außerhalb des Clip Rechtecks liegt. Ein Punkt kann nicht gleichzeitig
// rechts und links (bzw. oben und unten) außerhalb liegen, daher können nur maximal 2 Flags gesetzt sein.
// Es gibt 9 Möglichkeiten. Davon sind 8 ungleich 0 und zeigen an, dass die Koordinate geclippt werden muss. 

if(y1<YMin) K1 =CLIPLOWER;  // Ermittle, wo der Anfangspunkt außerhalb des Clip Rechtecks liegt.
if(y1>YMax) K1 =CLIPUPPER;  // Es werden entweder CLIPLOWER oder CLIPUPPER und/oder CLIPLEFT oder CLIPRIGHT gesetzt
if(x1<XMin) K1|=CLIPLEFT;   // Es gibt 8 zu clippende Kombinationen, je nachdem in welchem der 8 angrenzenden
if(x1>XMax) K1|=CLIPRIGHT;  // Bereiche des Clip Rechtecks die Koordinate liegt.

if(y2<YMin) K2 =CLIPLOWER;  // Ermittle, wo der Endpunkt außerhalb des Clip Rechtecks liegt.
if(y2>YMax) K2 =CLIPUPPER;  // Wenn keines der Flags gesetzt ist, dann liegt die Koordinate
if(x2<XMin) K2|=CLIPLEFT;   // innerhalb des Rechtecks und muss nicht geändert werden.
if(x2>XMax) K2|=CLIPRIGHT;

// Schleife nach Cohen Sutherland, die maximal 2 mal durchlaufen wird

 while(K1 || K2)    // muss wenigstens eine der Koordinaten irgendwo geclippt werden ?
 {

// wenn beide Koordinaten entweder links, rechts, über oder unter dem Clipping Rechteck liegen
// ist kein Teil der Linie sichtbar, daher ist keine weitere Berechnung notwendig.
// Die geclippte Linie ist unsichtbar.
 
   if(K1 & K2)      // logisches AND der beiden Koordinaten Flags ungleich 0 ?
     return FALSE;  // beide Punkte liegen jeweils auf der gleichen Seite außerhalb des Rechtecks

   if(K1)                       // schnelle Abfrage, muss Koordinate 1 geclippt werden ?
   {
     if(K1 & CLIPLEFT)          // ist Anfangspunkt links außerhalb ?
     {                          // ja
       y1+=(XMin-x1)*dy/dx;     // berechne y1 durch lineare Interpolation, dx kann hier nie 0 sein
       x1=XMin;                 // setze x1 an den linken Rand des Clip Rechtecks
     }  
     else if(K1 & CLIPRIGHT)    // ist Anfangspunkt rechts außerhalb ?
     {                          // ja
       y1+=(XMax-x1)*dy/dx;     // berechne y1 durch lineare Interpolation, dx kann hier nie 0 sein
       x1=XMax;                 // setze x1 an den rechten Rand des Clip Rechtecks
     }
     if(K1 & CLIPLOWER)         // ist Anfangspunkt unterhalb des Rechtecks ?
     {                          // ja
       x1+=(YMin-y1)*dx/dy;     // berechne x1 durch lineare Interpolation, dy kann hier nie 0 sein
       y1=YMin;                 // setze y1 an den unteren Rand des Clip Rechtecks
     }
     else if(K1 & CLIPUPPER)    // ist Anfangspunkt oberhalb des Rechtecks ?
     {                          // ja
       x1+=(YMax-y1)*dx/dy;     // berechne x1 durch lineare Interpolation, dy kann hier nie 0 sein
       y1=YMax;                 // setze y1 an den oberen Rand des Clip Rechtecks
     }
     K1 = 0;                    // Erst davon ausgehen, dass der Punkt jetzt innerhalb liegt,
                                // falls das nicht zutrifft, wird gleich korrigiert.
     if(y1<YMin) K1 =CLIPLOWER; // ermittle erneut, wo der Anfangspunkt jetzt außerhalb des Clip Rechtecks liegt
     if(y1>YMax) K1 =CLIPUPPER; // Für einen Punkt, bei dem im ersten Durchlauf z.B. CLIPLEFT gesetzt war,
     if(x1<XMin) K1|=CLIPLEFT;  // kann im zweiten Durchlauf z.B. CLIPLOWER gesetzt sein
     if(x1>XMax) K1|=CLIPRIGHT;
   }

   if(K1 & K2)      // logisches AND der beiden Koordinaten Flags ungleich 0 ?
     return FALSE;  // beide Punkte liegen jeweils auf der gleichen Seite außerhalb des Rechtecks

   if(K2)                       // schnelle Abfrage, muss Koordinate 2 geclippt werden ?
   {                            // ja
     if(K2 & CLIPLEFT)          // liegt die Koordinate links außerhalb des Rechtecks ?
     {                          // ja
       y2+=(XMin-x2)*dy/dx;     // berechne y durch lineare Interpolation, dx kann hier nie 0 sein
       x2=XMin;                 // setze die x Koordinate an den linken Rand
     }
     else if(K2 & CLIPRIGHT)    // liegt die Koordinate rechts außerhalb des Rechtecks ?
     {                          // ja
       y2+=(XMax-x2)*dy/dx;     // berechne y durch lineare Interpolation, dx kann hier nie 0 sein
       x2=XMax;                 // setze die x Koordinate an den rechten Rand
     }
     if(K2 & CLIPLOWER)         // liegt der Endpunkt unten außerhalb des Rechtecks ?
     {                          // ja
       x2+=(YMin-y2)*dx/dy;     // berechne x durch lineare Interpolation, dy kann hier nie 0 sein
       y2=YMin;                 // setze die y Koordinate an den unteren Rand 
     }
     else if(K2 & CLIPUPPER)    // liegt der Endpunkt oben außerhalb des Rechtecks ?
     {                          // ja
       x2+=(YMax-y2)*dx/dy;     // berechne x durch lineare Interpolation, dy kann hier nie 0 sein
       y2=YMax;                 // setze die y Koordinate an den oberen Rand 
     }
     K2 = 0;                    // Erst davon ausgehen, dass der Punkt jetzt innerhalb liegt,
                                // falls das nicht zutrifft, wird gleich korrigiert.
     if(y2<YMin) K2 =CLIPLOWER; // ermittle erneut, wo der Endpunkt jetzt außerhalb des Clip Rechtecks liegt
     if(y2>YMax) K2 =CLIPUPPER; // Ein Punkt, der z.B. zuvor über dem Clip Rechteck lag, kann jetzt entweder
     if(x2<XMin) K2|=CLIPLEFT;  // rechts oder links davon liegen. Wenn er innerhalb liegt wird kein
     if(x2>XMax) K2|=CLIPRIGHT; // Flag gesetzt.
   }
 }             // Ende der while Schleife, die Schleife wird maximal zweimal durchlaufen.
 return TRUE;  // jetzt sind die Koordinaten geclippt und die gekürzte Linie kann gezeichnet werden
}

Weblinks

• Skript
• Beschreibung (englisch)