中国地质大学(武汉)空间数据结构实习报告

1、空间数据结构实习报告学生姓名：孙国欢班 学 号：113131-05指导老师：周琪中国地质大学信息工程学院2015年10月线简化算法的程序实现及比较研究一、 实习内容：程序实现两种或以上的线简化算法，并比较各种算法的优劣。二、 实习要求：程序实现以下四种线简化算法中的两种或以上。三、 实习原理i. 基于点数的线简化算法（Num of points）ii. 基于长度的线简化算法（Length）iii. 基于角度的线简化算法（Angle）iv. 基于垂距的线简化算法 (Perpendicular distance）v. Douglas-Peucker（1988）vi. Whirlpool（1980）

2、四、 实习过程与成果过程分析：这次空间数据结构实习主要是围绕几个课上讲的基本算法和Douglas-Peucker、Whirlpool算法来实现线简化算法。我做了基于点数的线简化算法、基于长度的线简化算法、基于角度的线简化算法、Douglas-Peucker和Whirlpool算法。前三个算法的思想十分明确，是利用C+中的点的坐标结合基本函数可以实现。Douglas-Peucker算法的基本思路是对每条曲线的首末点虚线连接一条直线，求所有点与直线的距离并求出最大距离Dmax，再用Dmax与限差d相比较然后进行取舍。Whirlpool算法则是利用每个点设定r值画圆进行分类和取舍，成果展示：基于点数

3、的线简化算法 point=3 基于长度的线简化算法 length=40 基于角度的线简化算法 angle=90°DP算法 垂距d=20 Whirlpool算法 r=40基于点数的线简化算法 point=3 基于长度的线简化算法 length=60 基于角度的线简化算法 angle=75°DP算法 垂距d=30 Whirlpool算法 r=50-分界线-基于点数的线简化算法 point=3 基于长度的线简化算法 length=50 基于角度的线简化算法 angle=60° Whirlpool算法 r=40 DP算法得线简化结果为点（39,62）-分界线-基于点数的线

4、简化算法 point=4 基于长度的线简化算法 length=40 基于角度的线简化算法 angle=90° DP算法 垂距d=20 Whirlpool算法 r=30 -分界线-基于点数的线简化算法 point=3基于长度的线简化算法 length=30 基于角度的线简化算法 angle=60° DP算法 垂距d=30 Whirlpool算法 r=25 五、 思考与感想实习思考：针对基于点数的线简化算法、基于长度的线简化算法、基于角度的线简化算法、Douglas-Peucker和Whirlpool算法，我共采取了五组实验数据，分别表示五种图形数据。源数据1是一个普通的弯折直

5、线图，源数据2是一个起伏相当明显且角度多变的图形，源数据3是一个闭合的多边形，源数据4是一个近乎一端开口的矩形，源数据5是一个弯折且有重叠的折线图。我认为这五种情况的线性矢量数据采用不同的线简化算法产生的结果也决然不同。其中值得一提的是源数据3（闭合多边形）在Douglas-Peucker算法下简化为一个点，这与DP算法的原理有关，所有除首尾的点被舍去因而结果简化完只有一个顶点。而源数据4（一端开口的近矩形）在基于角度的线简化算法去angle=90°时完全简化成一个矩形，也反映了基于角度的线简化算法的原理使其去了四方顶点。比较我所探索的这五种线简化方法：基于点数的线简化算法、基于长度

6、的线简化算法、基于角度的线简化算法、Douglas-Peucker和Whirlpool算法。我认为它们都具有鲜明的优劣势。 基于点数的线简化算法：取相对应的隔点数并保留首尾点，方便快捷但效果一般 基于长度的线简化算法：取相对应的点与点的距离并保留首尾点，刨去了冗余的点，简化效果良好。 基于角度的线简化算法：取相对应的点与点的角度并保留首尾点，基本上择弯取直，简化效果良好。 Douglas-Peucker算法：求所有点与对每条曲线的首末点连接的直线的距离并求出最大距离Dmax，再用Dmax与垂距d比较后取舍。舍去了一些线性矢量数据上的点，形成了鲜明的结果，但是过程比较冗杂。 Whirlpool算

7、法：对设定的半径r给每个点作圆并进行取舍，使线性矢量数据的点的分布更加清晰，刨去了密集区的重复点，但不简便。实习感想：通过这次空间数据结构实习，我学到了很多。在此次实习中，我对这门课有了更加深刻的认识，学会了把所学的理论知识和实践联系起来。对于我来说不仅是设计算法来实现线简化算法，最为珍贵的是在我准备这次实习所巩固的以前不熟悉的知识。它培养了我们由书面文字要求到转化这种要求到现实模型的能力，即很大程度上培养了我们的建模能力，分析问题，总结归纳问题的能力。这次实习也遇到了一些难关，但它们给了我们思索的机会。我们通过克服这一个个困难，让我们重新又对目前脑子里所掌握的知识进行审理，进行了再次的纠正或者完善，这些都是书本上学不来的。理论联系实际就在这里自然地得到实现。这对我们巩固已学知识，锻炼实践动手能力大有裨益。在这次实习中，我觉得我最大的收获就是学会了为了实现这些算法，我该如何去构建这样的框架。实习的这几周，我从只理解书面上的线简化算法原理，到现在实现这样的过程，中间也遇到了很多困难和挫折。在程序的编写过程中，也出现了很多错误，经过我认真修改，查阅资料，向老师和同学们请教，终于把那些错误都改正过来，最终使程序能够结合要求的算法正确的运行。我再通过绘制excel表格来进一步了解各种不同的线简化算法会出现什么样的结果。所以说，这