Iterative version of Ramer–Douglas–Peucker line simplification algorithm

LineSimplification.cs

using System;
using System.Collections.Generic;
using System.Drawing;

//https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

namespace Math.Helpers
{
    public static class RamerDouglasPeuckerAlgorithm
    {
        public static List<PointF> Simplify(List<PointF> points, float epsilon)
        {
            var output = new List<PointF>();
            if (points.Count >= 2)
                RamerDouglasPeuckerIterative(points, epsilon, output);
            else
                output.AddRange(points);
            return output;
        }

        private static void RamerDouglasPeuckerIterative(List<PointF> points, float epsilon, List<PointF> output)
        {
            var start = 0;
            var end = points.Count - 1;

            while (start < end)
            {
                output.Add(points[start]);

                var newEnd = end;

                while (true)
                {
                    var maxDistanceIndex = 0;
                    var maxDistance = 0.0f;

                    for (var i = start + 1; i < newEnd; i++)
                    {
                        var d = PerpendicularDistance(points[i], points[start], points[newEnd]);
                        if (d > maxDistance)
                        {
                            maxDistanceIndex = i;
                            maxDistance = d;
                        }
                    }

                    if (maxDistance <= epsilon)
                        break;

                    newEnd = maxDistanceIndex;
                }

                start = newEnd;
            }

            output.Add(points[end]);
        }

        private static float PerpendicularDistance(PointF pt, PointF lineStart, PointF lineEnd)
        {
            var dx = lineEnd.X - lineStart.X;
            var dy = lineEnd.Y - lineStart.Y;

            // Normalize
            var mag = (float) Math.Sqrt(dx * dx + dy * dy);
            if (mag > 0.0f)
            {
                dx /= mag;
                dy /= mag;
            }
            var pvx = pt.X - lineStart.X;
            var pvy = pt.Y - lineStart.Y;

            // Get dot product (project pv onto normalized direction)
            var pvdot = dx * pvx + dy * pvy;

            // Scale line direction vector and subtract it from pv
            var ax = pvx - pvdot * dx;
            var ay = pvy - pvdot * dy;

            return (float) Math.Sqrt(ax * ax + ay * ay);
        }
    }
}