Algorithmus von Cohen-Sutherland

 /*----------------------------------------------------------------------------------------  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 zweimal 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;     }      // muss hier nochmal getestet werden, sonst werden Linien, die über Eck außerhalb liegen nicht korrekt behandelt     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  }