# Cohen-Sutherland Line Clipping in C#

While busy working on TrueNorth, I implemented this based on the the Wikipedia Article.
The Extents class, and the PointDType are simple structures to contain the view window, and the double precision coordinates respectively.

```    /// <summary>
/// The Cohen Sutherland line clipping algorithm
/// http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm
/// </summary>
public class CohenSutherland
{
/// <summary>
/// Bitfields used to partition the space into 9 regiond
/// </summary>
private const byte INSIDE = 0; // 0000
private const byte LEFT = 1;   // 0001
private const byte RIGHT = 2;  // 0010
private const byte BOTTOM = 4; // 0100
private const byte TOP = 8;    // 1000

/// <summary>
/// Compute the bit code for a point (x, y) using the clip rectangle
/// bounded diagonally by (xmin, ymin), and (xmax, ymax)
/// ASSUME THAT xmax , xmin , ymax and ymin are global constants.
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
private static byte ComputeOutCode(Extents extents, double x, double y)
{
// initialised as being inside of clip window
byte code = INSIDE;

if (x < extents.Left)           // to the left of clip window
code |= LEFT;
else if (x > extents.Right)     // to the right of clip window
code |= RIGHT;
if (y < extents.Bottom)         // below the clip window
code |= BOTTOM;
else if (y > extents.Top)       // above the clip window
code |= TOP;

return code;
}

/// <summary>
/// Cohen–Sutherland clipping algorithm clips a line from
/// P0 = (x0, y0) to P1 = (x1, y1) against a rectangle with
/// diagonal from (xmin, ymin) to (xmax, ymax).
/// </summary>
/// <param name="x0"></param>
/// <param name="y0""</param>
/// <param name="x1"></param>
/// <param name="y1"></param>
/// <returns>a list of two points in the resulting clipped line, or zero</returns>
public static List<PointDType> CohenSutherlandLineClip(Extents extents,
PointDType p0, PointDType p1)
{
double x0 = p0.X;
double y0 = p0.Y;
double x1 = p1.X;
double y1 = p1.Y;

// compute outcodes for P0, P1, and whatever point lies outside the clip rectangle
byte outcode0 = CohenSutherland.ComputeOutCode(extents, x0, y0);
byte outcode1 = CohenSutherland.ComputeOutCode(extents, x1, y1);
bool accept = false;

while (true)
{
// Bitwise OR is 0. Trivially accept and get out of loop
if ((outcode0 | outcode1) == 0)
{
accept = true;
break;
}
// Bitwise AND is not 0. Trivially reject and get out of loop
else if ((outcode0 & outcode1) != 0)
{
break;
}
else
{
// failed both tests, so calculate the line segment to clip
// from an outside point to an intersection with clip edge
double x, y;

// At least one endpoint is outside the clip rectangle; pick it.
byte outcodeOut = (outcode0 != 0) ? outcode0 : outcode1;

// Now find the intersection point;
// use formulas y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
if ((outcodeOut & TOP) != 0)
{   // point is above the clip rectangle
x = x0 + (x1 - x0) * (extents.Top - y0) / (y1 - y0);
y = extents.Top;
}
else if ((outcodeOut & BOTTOM) != 0)
{ // point is below the clip rectangle
x = x0 + (x1 - x0) * (extents.Bottom - y0) / (y1 - y0);
y = extents.Bottom;
}
else if ((outcodeOut & RIGHT) != 0)
{  // point is to the right of clip rectangle
y = y0 + (y1 - y0) * (extents.Right - x0) / (x1 - x0);
x = extents.Right;
}
else if ((outcodeOut & LEFT) != 0)
{   // point is to the left of clip rectangle
y = y0 + (y1 - y0) * (extents.Left - x0) / (x1 - x0);
x = extents.Left;
}
else
{
x = double.NaN;
y = double.NaN;
}

// Now we move outside point to intersection point to clip
// and get ready for next pass.
if (outcodeOut == outcode0)
{
x0 = x;
y0 = y;
outcode0 = CohenSutherland.ComputeOutCode(extents, x0, y0);
}
else
{
x1 = x;
y1 = y;
outcode1 = CohenSutherland.ComputeOutCode(extents, x1, y1);
}
}
}

// return the clipped line
return (accept) ?
new List<PointDType>()
{
new PointDType(x0,y0),
new PointDType(x1, y1),
} : null;

}
}
```
Posted in Blog and tagged , , , .

## One Comment

1. simonjohnroberts

Cases where both points lie outside the line but would pass thru the rectangle. Struggling to visualise the best way to do this effectively :)

Thanks for the code