CohenSutherlandClipping

CohenSutherlandClipping.cs

using System;
using System.Collections.Generic;
using JSIL;
using JSIL.Meta;

public static class Program
{
    public static void Main()
    {
        Console.WriteLine("The red line is the clipped " +
                         "version of the blue line");

        dynamic document = Builtins.Global["document"];
        dynamic window = Builtins.Global["window"];

        var canvas = document.createElement("canvas");
        var ctx = canvas.getContext("2d");
        var body = document.getElementsByTagName("body")[0];
        body.appendChild(canvas);
      	var rect = new Rect(20, 20, 60, 60);
      
        ctx.fillStyle = "grey";
	    ctx.fillRect(rect.Left, rect.Top, rect.Right - rect.Left, rect.Bottom-rect.Top);

        var lineString = new List<Point> { 
            new Point(0, 0), new Point(50, 50), 
            new Point(100, 50), new Point(50, 100) };

        var clipped = CohenSutherlandClipping.Clip(rect, lineString);

        DrawLineString(ctx, lineString, "blue", 4);
      	foreach(var clippedString in clipped)
          DrawLineString(ctx, clippedString, "red", 2);
    }

    public static void DrawLineString(dynamic ctx, IList<Point> lineString, string color, double width)
    {
        ctx.lineWidth = width;
        ctx.strokeStyle = color;
        ctx.beginPath();
        ctx.moveTo(lineString[0].X, lineString[0].Y);
        for (int i = 1; i < lineString.Count; i++)
            ctx.lineTo(lineString[i].X, lineString[i].Y);
        ctx.stroke();
    }

    /// <summary>
    /// <para>
    /// Cohen-Sutherland clipping - initially taken from 
    /// http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland.
    /// </para>
    /// </summary>
    public class CohenSutherlandClipping
    {
        #region private constants
        private const int INSIDE = 0; // 0000
        private const int LEFT = 1;   // 0001
        private const int RIGHT = 2;  // 0010
        private const int BOTTOM = 4; // 0100
        private const int TOP = 8;    // 1000
        #endregion

        #region private methods
        /// <summary> Compute the bit code for a point using the given clip rectangle. </summary>
        /// <param name="r"> Clip rectangle. </param>
        /// <param name="p"> Point to compute the bit code for. </param>
        /// <returns> The bit code. </returns>
        private static int ComputeOutCode(Rect r, Point p)
        {
            int code = INSIDE;                   // initialized as being inside of clip window

            if (r.Left - p.X > 1e-4)             // to the left of clip window
                code |= LEFT;
            else if (p.X - r.Right > 1e-4)        // to the right of clip window
                code |= RIGHT;
            if (r.Top - p.Y > 1e-4)              // below the clip window
                code |= BOTTOM;
            else if (p.Y - r.Bottom > 1e-4)      // above the clip window
                code |= TOP;

            return code;
        }
        #endregion

        #region public methods
        /// <summary> Cohen–Sutherland clipping algorithm; clips the line specified by p0 to p1
        /// against the clipping rectangle specified by clipRect. </summary>
        /// <param name="clipRect"> Clipping rectangle. Be sure that the rectangle 
        /// satisfies the conditions left &lt;= right and top &lt;= bottom. </param>
        /// <param name="p0"> Line start point. </param>
        /// <param name="p1"> Line end point. </param>            
        /// <returns> Boolean value showing whether the line is visible in the rectangle (true) or not (false). </returns>
        public static bool Clip(Rect clipRect, ref Point p0, ref Point p1)
        {
            // compute outcodes for P0, P1, and whatever point lies outside the clip rectangle
            int outcode0 = ComputeOutCode(clipRect, p0);
            int outcode1 = ComputeOutCode(clipRect, p1);

            while (true)
            {
                if (0 == (outcode0 | outcode1))
                {
                    // logical or is 0 (both points inside). 
                    // Trivially accept and get out of loop
                    return true;
                }
                else if (0 != (outcode0 & outcode1))
                {
                    // logical and is not 0 (both points outside, no part visible). 
                    // Trivially reject and get out of loop.
                    return false;
                }
                else
                {
                    // failed both tests, so calculate the line segment to clip
                    // from an outside point to an intersection with clip edge
                    Point p = new Point();

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

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

                    // Now we move outside point to intersection point to clip
                    // and get ready for next pass.

                    if (outcodeOut == outcode0)
                        outcode0 = ComputeOutCode(clipRect, p0 = p);
                    else
                        outcode1 = ComputeOutCode(clipRect, p1 = p);
                }
            }
        }

        public static List<List<Point>> Clip(Rect clipRect, List<Point> lineString)
        {
            Point pCurrent = new Point(double.NaN, double.NaN);
            var result = new List<List<Point>>();
            List<Point> currentLineString = null;
            for (int i = 0; i < lineString.Count - 1; i++)
            {
                Point p0 = lineString[i];
                Point p1 = lineString[i + 1];

                if (Clip(clipRect, ref p0, ref p1))
                {
                    if (p0.X != pCurrent.X || p0.Y != pCurrent.Y)
                    {
                        currentLineString = new List<Point>();
                        result.Add(currentLineString);
                        currentLineString.Add(p0);
                    }

                    currentLineString.Add(p1);
                    pCurrent = p1;
                }
            }

            return result;
        }

        #endregion
    }
}

/// <summary>
/// A generic point with double coordinates, you can use the point from your
/// Graphics/GIS framweork instead (e.g. System.Windows.Point)
/// </summary>
public struct Point
{
    public Point(double x, double y)
    {
        this.X = x;
        this.Y = y;
    }

    public double X;
    public double Y;
}

/// <summary>
/// A generic rect with double coordinates, you can use the rect from your
/// Graphics/GIS framweork instead (e.g. System.Windows.Rect)
/// </summary>
public struct Rect
{
    public Rect(double x, double y, double width, double height)
    {
        this.Left = x;
        this.Top = y;
        this.Right = x + width;
        this.Bottom = y + height;
    }

    public double Left;
    public double Top;
    public double Right;
    public double Bottom;
}