using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    public struct cvPoint
    {
        public int X;
        public int Y;
        public cvPoint(int x, int y)
        {
            X = x;
            Y = y;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            var points = new List<cvPoint>();
            points.Add(new cvPoint(1, 1));
            points.Add(new cvPoint(2, 2));
            points.Add(new cvPoint(3, 3));
            points.Add(new cvPoint(4, 3));
            points.Add(new cvPoint(5, 3));
            points.Add(new cvPoint(6, 3));
            points.Add(new cvPoint(5, 3));
            points.Add(new cvPoint(6, 3));
            points.Add(new cvPoint(7, 3));
            points.Add(new cvPoint(8, 3));
            var epsilon = 0.8d;
            var filteredPoints = new List<cvPoint>();
            DouglasPeucker(points, epsilon, ref filteredPoints);
            Console.WriteLine("Filtered points：");
            foreach (var f in filteredPoints)
            {
                Console.WriteLine(string.Format("{0},{1}", f.X, f.Y));
            }
            Console.ReadKey();
        }
        private static double distanceToSegment(cvPoint p, cvPoint start, cvPoint end)
        {
            var m1 = ((double)(end.Y - start.Y)) / ((double)(end.X - start.X));
            var c1 = start.Y - m1 * start.X;
            var interPointX = 0d;
            var interPointY = 0d;
            if (m1 == 0)
            {
                interPointX = p.X;
                interPointY = c1;

            }
            else
            {
                var m2 = -1 / m1;
                var c2 = p.Y - m2 * p.X;
                interPointX = (c1 - c2) / (m2 - m1);
                interPointY = m2 * interPointX + c2;
            }
            return Math.Sqrt(Math.Pow(p.X - interPointX, 2) + Math.Pow(p.Y - interPointY, 2));
        }

        private static void DouglasPeucker(IList<cvPoint> PointList, double epsilon, ref List<cvPoint> filteredPoints)
        {
            var dmax = 0d;
            int index = 0;
            int length = PointList.Count;
            for (int i = 1; i < length - 1; i++)
            {
                var d = distanceToSegment(PointList[i], PointList[0], PointList[length - 1]);
                Console.WriteLine(string.Format("{0}.distence:{1}", i, d));
                if (d > dmax)
                {
                    index = i;
                    dmax = d;
                }
            }
            Console.WriteLine(string.Format("dMax:{0}", dmax));
            // If max distance is greater than epsilon, recursively simplify
            if (dmax > epsilon)
            {
                filteredPoints.Add(PointList[0]);
                filteredPoints.Add(PointList[index]);
                filteredPoints.Add(PointList[length - 1]);
                DouglasPeucker(PointList.Take(index + 1).ToList(), epsilon, ref filteredPoints);
                DouglasPeucker(PointList.Skip(index + 1).Take(PointList.Count - index - 1).ToList(), epsilon, ref filteredPoints);
            }
        }
    }
}