C#实现道格拉斯普克算法

道格拉斯-普克算法是将曲线近似表示为一系列点，并减少点的数量的一种算法。

算法的基本思路是:对每一条曲线的首末点虚连一条直线,求所有点与直线的距离,并找出最大距离值dmax ,用dmax与阈值D（阈值是自己设定的）相比:若dmax <D,这条曲线上的中间点全部舍去;若dmax ≥D,保留dmax 对应的坐标点,并以该点为界,把曲线分为两部分,对这两部分重复使用该方法。阈值越大保留的点越少，根据自己想要保留的情况来设定阈值。

详细步骤：

（1）在曲线首尾两点间虚连一条直线,求出其余各点到该直线的距离，如右图（1）。

（2）选其最大者与阈值相比较,若大于阈值,则离该直线距离最大的点保留,否则将直线两端点间各点全部舍去，如右图（2），第4点保留。

（3）依据所保留的点,将已知曲线分成两部分处理,重复第1、2步操作，迭代操作，即仍选距离最大者与阈值比较,依次取舍,直到无点可舍去，最后得到满足给定精度限差的曲线点坐标，如图（3）、（4）依次保留第6点、第7点，舍去其他点,即完成线的化简。

C#实现部分代码：

       ArrayList myar = new ArrayList();//存入原始数据  
       ArrayList yssj = new ArrayList();//原始数据的坐标
       Dictionary<int, double> d = new Dictionary<int, double>();//原始数据的坐标
       Dictionary<double, double> m = new Dictionary<double, double>();//抽稀之后数据的坐标，这个主要是为了在chart上画图
       ArrayList newar = new ArrayList(); //存入抽稀后的数据的坐标

        public class canshu//记录直线参数的类  
        {
            public double k;
            public double b;
        }

        public class zuobiao//坐标数据类  
        {
            public double x;
            public double y;

        }
        public canshu xielv(zuobiao shou, zuobiao wei)//求斜率  
        {
            double k, b;
            canshu newcs = new canshu();
            k = (wei.y - shou.y) / (wei.x - shou.x);
            b = shou.y - k * shou.x;
            newcs.k = k;
            newcs.b = b;
            return newcs;
        }

        public double distance(zuobiao dot, canshu cs)//求点到直线距离  
        {
            double dis = (double)(Math.Abs(cs.k * dot.x - dot.y + cs.b)) / (double)Math.Sqrt(cs.k * cs.k + 1);//点（x0，y0）到直线Ax+By+c=0的距离d=|Ax0+By0+c|/(A2+B2)1/2
            return dis;
        }
        public void Douglas(int number1, int number2)
        {
            int max = 0;//定义拥有最大距离值的点的编号  
            canshu myc = new canshu();
            myc = xielv((zuobiao)yssj[number1], (zuobiao)yssj[number2-1]);
            max = 0;
            double maxx = distance((zuobiao)yssj[number1 + 1], myc);//假设第二个点为最大距离点  
           
            double yuzhi = Convert.ToSingle(textBox1.Text);//设阈值
            
            for (int i = number1 + 1; i < number2 - 1; i++)//从第二个点遍历到最后一个点前方的点  
            {
                if (distance((zuobiao)yssj[i], myc) > yuzhi && distance((zuobiao)yssj[i], myc) >= maxx)//找出拥有最大距离的点  
                {
                    max = i;
                    maxx = distance((zuobiao)yssj[i], myc);
                }
            }
            if (max == 0)//若不存在最大距离点，则只将首尾点存入arraylist，结束这一次的道格拉斯抽稀  
            {
                if (!newar.Contains((zuobiao)yssj[number2-1]))
                {
                    newar.Add((zuobiao)yssj[number2 - 1]);
                    return;
                }
            }
            else if (number1 + 1 == max && number2 - 2 != max)//如果第二个点是最大距离点，则以下一个点和尾点作为参数进行道格拉斯抽稀释  
            {
                newar.Add((zuobiao)yssj[max]);
                Douglas(max, number2);
            }
            else if (number2 - 2 == max && number1 + 1 != max)//如果倒数第二个点是最大距离点，则以首点和倒数第三点作为参数进行道格拉斯抽稀  
            {
                newar.Add((zuobiao)yssj[max]);
                Douglas(number1, max + 1);
            }
            else if (number1 + 1 == max && number2 - 2 == max)//如果首点尾点夹住最大距离点，则将最大距离点和尾点存入arraylist  
            {
                newar.Add((zuobiao)yssj[max]);
                return;
            }
            else
            {
                newar.Add((zuobiao)yssj[max]);
                Douglas(number1, max + 1);
                Douglas(max, number2);
            }

        }

实现效果图：

选取了一个点比较少的图，别的图数据都好几万个点，就从中截取了一段数据进行节点抽稀。