Cohen-Sutherland's algorithm
The Cohen-Sutherland algorithm is an algorithm for clipping lines on a rectangle . It is named after its inventors Danny Cohen and Ivan Sutherland . The algorithm is considered the most popular, if not the most efficient for its purposes. It is particularly suitable for cases in which a large proportion of the lines to be clipped are inside or outside the rectangle.
steps
First, four flags are determined for the two end points of the line to be drawn, which are set when the end point is to the left of the rectangle, to the right of it, below or above it. If neither of the flags is set, then both end points lie within the rectangle, no clipping is necessary and the line can simply be drawn.
If this trivial case does not occur, the flags of both endpoints that correspond to one another are examined in the next step. If at least one of these flags is set at both end points, the entire line is outside the rectangle and the line does not need to be drawn.
If this simple case does not occur either, the intersection point of any (any) side of the rectangle with the line segment is calculated and the overlapping part is tested again (and possibly shortened) until both points are finally within the rectangle.
implementation
The following program gives an example of an implementation of the Cohen-Sutherland algorithm in C ++, which can be used to understand how it works.
/*----------------------------------------------------------------------------------------
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;
}
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
}
Web links
- Description (English)
- JavaScript implementation (with source code)
- Java applet