Algorithmus von Cohen-Sutherland

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 des Rechtecks, 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

bool 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,CLIPUPPER,CLIPLOWER, 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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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 …   Deutsch Wikipedia

  • Algorithmus von Sutherland-Hodgman — Der Algorithmus von Sutherland Hodgman ist ein nach Ivan Sutherland und Gary W. Hodgman benannter Algorithmus der Computergrafik zum Clipping von Polygonen. Inhaltsverzeichnis 1 Grundversion 1.1 Pseudo Code 2 Erweiterte Version …   Deutsch Wikipedia

  • Cohen — ist ein jüdischer Familienname. Der Familienname hat die höchste Verbreitung vergleichbar mit Müller und Schmidt in der deutschsprachigen Welt oder mit Smith in der englischsprachigen Welt. Herkunft und Bedeutung Cohen ist der biblische Name von… …   Deutsch Wikipedia

  • Sutherland-Hodgeman — Der Algorithmus von Sutherland Hodgman ist ein Algorithmus der Computergrafik zum Clipping von Polygonen. Inhaltsverzeichnis 1 Grundversion 2 Erweiterte Version 3 Literatur 4 Weblinks …   Deutsch Wikipedia

  • Sutherland Hodgman — Der Algorithmus von Sutherland Hodgman ist ein Algorithmus der Computergrafik zum Clipping von Polygonen. Inhaltsverzeichnis 1 Grundversion 2 Erweiterte Version 3 Literatur 4 Weblinks …   Deutsch Wikipedia

  • Ivan Sutherland — 2008 Ivan Edward Sutherland (* 16. Mai 1938 in Hastings, Nebraska) ist ein Pionier der Computergrafik. Sein Programm Sketchpad, das er im Rahmen seiner Doktorarbeit 1963 am MIT entwickelte, gilt als eine der ersten interaktiven Grafikanwendungen …   Deutsch Wikipedia

  • Liste bedeutender Personen für die Informatik — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf… …   Deutsch Wikipedia

  • Clipping (Computergrafik) — Als Clipping oder Abschneiden (englisch to clip = „abschneiden“, „kappen“) bezeichnet man in der Computergrafik das Abschneiden von Grundobjekten am Rand eines gewünschten Bildschirmausschnittes oder Fensters. Ein Fenster kann dabei ein… …   Deutsch Wikipedia

  • Liste bekannter Ingenieure — Siehe auch: Liste von Erfindern, Liste der Biographien, Kategorie:Ingenieur, Erfinder, Konstrukteur, Liste Persönlichkeiten der Elektrotechnik A Ingenieur Lebensdaten Erfindungen, Leistungen, ingenieurwissenschaftliche Tätigkeiten Roman Abt… …   Deutsch Wikipedia

  • Liste bedeutender Ingenieure — Siehe auch: Liste von Erfindern, Liste der Biographien, Kategorie:Ingenieur, Erfinder, Konstrukteur, Liste Persönlichkeiten der Elektrotechnik Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”