道格拉斯抽稀算法 Java_道格拉斯—普克(Douglas一Peukcer)节点抽稀算法

落日映苍穹つ 2022-11-09 12:42 432阅读 0赞

Douglas一Peukcer算法由D.Douglas和T.Peueker于1973年提出，简称D一P算法，是眼下公认的线状要素化简经典算法。现有的线化简算法中，有相当一部分都是在该算法基础上进行改进产生的。它的长处是具有平移和旋转不变性，给定曲线与阂值后，抽样结果一定。

算法的基本思路是:对每一条曲线的首末点虚连一条直线,求所有点与直线的距离,并找出最大距离值dmax ,用dmax与限差D相比:若dmax

算法的具体过程如下:

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

(2) 选其最大者与阈值相比較,若大于阈值,则离该直线距离最大的点保留,否则将直线两端点间各点所有舍去，如图3(2)，第4点保留。

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

![cdd7051b4c1f82c66c94c9e3dc80d08d6b8.jpg][]

利用递归的方法遍历所有的点进行道格拉斯抽稀。

验证数据如图。

![978a0328d22af08c144f8b3ef4c847e6.png][]

其中，黑色的线为原始线状数据，其他颜色为进行抽稀元算时所做辅助线。

ArrayList myar = new ArrayList();//存入原始数据

ArrayList newar = new ArrayList(); //存入抽稀后的数据

public class canshu//记录直线参数的类

\{public doublek;public doubleb;

\}public class zuobiao//坐标数据类

\{public doublex;public doubley;

\}public canshu xielv(zuobiao shou, zuobiao wei)//求斜率

\{doublek, b;

canshu newcs= newcanshu();

k= (wei.y - shou.y) / (wei.x -shou.x);

b= shou.y - k \*shou.x;

newcs.k=k;

newcs.b=b;returnnewcs;

\}public double distance(zuobiao dot,canshu cs)//求点到直线距离

\{double dis =(Math.Abs (cs.k \* dot.x - dot.y + cs.b)) / Math.Sqrt(cs.k \* cs.k + 1);returndis;

道格拉斯算法如下：

public void Douglas(int number1, intnumber2)

\{int max=0;//定义拥有最大距离值的点的编号

canshu myc = newcanshu();

myc= xielv((zuobiao)myar\[number1\], (zuobiao)myar\[number2-1\]);double maxx = distance((zuobiao)myar\[number1+1\], myc);//假设第二个点为最大距离点

double yuzhi = Convert.ToInt32(textBox1.Text);//设阈值

for (int i = number1 + 1; i < number2 - 1; i++)//从第二个点遍历到最后一个点前方的点

\{if (distance((zuobiao)myar\[i\], myc) > yuzhi && distance((zuobiao)myar\[i\], myc) >= maxx)//找出拥有最大距离的点

max=i;

maxx=distance((zuobiao)myar\[i\], myc);

\}if(max==0)//若不存在最大距离点，则只将首尾点存入arraylist，结束这一次的道格拉斯抽稀

newar.Add((zuobiao)myar\[number2-1\]);return;

\}else if (number1 + 1 == max&&number2-2!=max)//如果第二个点是最大距离点，则以下一个点和尾点作为参数进行道格拉斯抽稀释

Douglas(max+1, number2);

\}else if (number2 - 2 == max&&number1+1!=max)//如果倒数第二个点是最大距离点，则以首点和倒数第三点作为参数进行道格拉斯抽稀

lt;/span>\{

Douglas(0, max+1);

\}else if (number1 + 1 == max && number2 - 2 == max)//如果首点尾点夹住最大距离点，则将最大距离点和尾点存入arraylist

newar.Add((zuobiao)myar\[max\]);

newar.Add((zuobiao)myar\[max+1\]);return;

\}else\{

Douglas(number1, max+1);

Douglas(max, number2);

不同阈值的运行情况如图：

![4a391060adb3f5b5ad9d61598e8dff1d.png][]

![0371e4f14b87d3a23132463f053f5369.png][]

![d79f91a88014e347ad548180e20b20a7.png][]

[cdd7051b4c1f82c66c94c9e3dc80d08d6b8.jpg]: /images/20221023/0c1878d866aa40a69c7c27489d23f8ad.png
[978a0328d22af08c144f8b3ef4c847e6.png]: /images/20221023/07321767340742dfb2870df6a179b0b3.png
[4a391060adb3f5b5ad9d61598e8dff1d.png]: /images/20221023/7c604457b763464b9ab5b3f5ea807ad2.png
[0371e4f14b87d3a23132463f053f5369.png]: /images/20221023/84d65bcf068c43759e0392d96ad3dcd8.png
[d79f91a88014e347ad548180e20b20a7.png]: /images/20221023/9cf4e06ee7014c2f84211c9a262abd82.png