DouglasPeuckerReduction

DouglasPeuckerReduction.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 simplified " +
                         "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 lineString = new List<Point> { 
            new Point(0, 0), new Point(20,30), new Point(50, 50), 
            new Point(60, 45), new Point(100, 50), new Point(50, 100) };

        var simplified = DouglasPeuckerReduction(lineString, 10);

        DrawLineString(ctx, lineString, "blue", 4);
        DrawLineString(ctx, simplified, "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>
    /// Uses the Douglas Peucker algorithim to reduce the number of points.
    /// </summary>
    /// <param name="Points">The points.</param>
    /// <param name="Tolerance">The tolerance.</param>
    /// <returns></returns>
    public static IList<Point> DouglasPeuckerReduction(IList<Point> Points, double Tolerance)
    {
        if (Points == null || Points.Count < 3)
            return Points;

        int firstPoint = 0;
        int lastPoint = Points.Count - 1;
        var pointIndexsToKeep = new List<int>();

        //Add the first and last index to the keepers
        pointIndexsToKeep.Add(firstPoint);
        pointIndexsToKeep.Add(lastPoint);

        //The first and the last point can not be the same
        while (Points[firstPoint].Equals(Points[lastPoint]))
        {
            lastPoint--;
        }

        DouglasPeuckerReduction(Points, firstPoint, lastPoint, Tolerance, ref pointIndexsToKeep);

        var returnPoints = new List<Point>();
        pointIndexsToKeep.Sort();
        foreach (int index in pointIndexsToKeep)
        {
            returnPoints.Add(Points[index]);
        }

        return returnPoints;
    }

    /// <summary>
    /// Douglases the peucker reduction.
    /// </summary>
    /// <param name="points">The points.</param>
    /// <param name="firstPoint">The first point.</param>
    /// <param name="lastPoint">The last point.</param>
    /// <param name="tolerance">The tolerance.</param>
    /// <param name="pointIndexsToKeep">The point indexs to keep.</param>
    private static void DouglasPeuckerReduction(IList<Point> points, int firstPoint, int lastPoint, double tolerance, ref List<int> pointIndexsToKeep)
    {
        double maxDistance = 0;
        int indexFarthest = 0;

        for (int index = firstPoint; index < lastPoint; index++)
        {
            double distance = PerpendicularDistance(points[firstPoint], points[lastPoint], points[index]);
            if (distance > maxDistance)
            {
                maxDistance = distance;
                indexFarthest = index;
            }
        }

        if (maxDistance > tolerance && indexFarthest != 0)
        {
            //Add the largest point that exceeds the tolerance
            pointIndexsToKeep.Add(indexFarthest);

            DouglasPeuckerReduction(points, firstPoint, indexFarthest, tolerance, ref pointIndexsToKeep);
            DouglasPeuckerReduction(points, indexFarthest, lastPoint, tolerance, ref pointIndexsToKeep);
        }
    }

    /// <summary>
    /// The distance of a point from a line made from point1 and point2.
    /// </summary>
    /// <param name="pt1">The PT1.</param>
    /// <param name="pt2">The PT2.</param>
    /// <param name="p">The p.</param>
    /// <returns></returns>
    public static double PerpendicularDistance(Point Point1, Point Point2, Point Point)
    {
        //Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)|   *Area of triangle
        //Base = √((x1-x2)²+(x1-x2)²)                               *Base of Triangle*
        //Area = .5*Base*H                                          *Solve for height
        //Height = Area/.5/Base

        double area = Math.Abs(.5 * (Point1.X * Point2.Y + Point2.X * Point.Y + Point.X * Point1.Y - Point2.X * Point1.Y - Point.X * Point2.Y - Point1.X * Point.Y));
        double bottom = Math.Sqrt(Math.Pow(Point1.X - Point2.X, 2) + Math.Pow(Point1.Y - Point2.Y, 2));
        double height = area / bottom * 2;

        return height;
    }
}

/// <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;
}