平面域中散乱点的Delaunay 三角化算法

《平面域中散乱点的Delaunay 三角化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛平面域中散乱点的Delaunay三角化算法高溪唐琎（中南大学信息科学与工程学院湖南长沙410075）摘要：基于三角网生长算法和分治算法的思想，提出并实现了一个平面域散乱点的三角网格重构算法。算法首先利用分治算法的思想将散乱点集进行分割，然后在四个极值点确定初始三角形的基础上，基于边的扩展原则构造新的三角形，使网格不断向周围扩展直到所有的待扩展的边全部能构成三角形为止，最终构造出整个散乱点集的三角网

2、格。关键词：散乱点集；Delaunay三角化；网格重构；中图法分类号：TP242.6+2文献标识码：ADelaunayTriangulationAlgorithminDishevelledPointsofPlanarDomainGAOXITANGJIN(SchoolofInformationscienceandEngineering,CentralSouthUniversity,Changsha410075,China）Abstract:Basedonideasoftriangulationnetworkgr

3、owthalgorithmandpartitionalgorithm,atriangularmeshreconstructionalgorithmindishevelledpointsofplanardomainispresentedandrealized.Thealgorithmfirstsegmentsthesetofdishevelledpointsusingtheideaofpartitionalgorithm.Thenseekstartingtriangularsonthebaseoffourext

4、rimumpoints,searchesanewtriangularwiththeprincipleofedgeextending,makingthemeshenlargeuntiledgecoveringalldishevellpoints.Atlastthetriangularmeshofdishevelledpointsisreconstructed.Keywords:Dishevelledpoints;DelaunayTriangulationAlgorithm;Meshreconstruction;

5、1引言三角化是移动机器人在未知环境中进行地图重建必不可少的部分，机器人在未知环境中通过雷达、红外线等等获取环境中的信息（一些杂乱无章的散乱点，每个点都有一个距离值，表示该点与当时测量仪器的距离），然后如何利用这些散乱的点重塑位置环境的三维立体模型是关键部分，此处便用到了散乱点的三角化算法。Delaunay三角化算法是一种常用的算法，它特点是剖分结果的每个三角形都尽量避免成为狭长三角形，散乱点集的Delaunay三角化再逆向工程中有着十分广泛的应用，常见的[1]Delaunay算法主要有三种：逐点插入法、分治算

6、法、三角网生长法。[2]目前针对三角化的研究主要有：Boll和Vemuri，Brinkley和Schmitt等采用参数表示法，将三维数据映射到二维参数域上，在二维进行曲面重构，然后将结果映射回三维空间；[3]Bowyer和Watson采用Delaunay三角剖分化，通过将二维的Delaunay三角剖分推广到三[4]维进行网络重构；Bernaridini的BPA算法通过种子三角形不断向周围扩展，从而构成最终的三角形网格等等，这些研究都表明了平面上散乱点三角化的重要性。本文利用分治算法的分割思想和三角网生长法的扩

7、展思想提出了一种新的三角化算法，并通过编程证明了该算法的可行性。2算法设计2.1基本数据结构由于散乱点的三角化是一个动态的逐步扩展的过程，所以需要用到动态数据的存储。本文采用的是C++库里的模板类CArray，该类可以动态地添加和删除任一元素。算法里的散乱点可由二维坐标表示，记为（x，y）。在平面域中散乱点的三角化中，为了有效地实现算法功能，需要若干相关数据结构作为算法支持。为了便于理解算法思想以下列出了算法中关键的数据结构。http://www.elecfans.com电子发烧友http://bbs.ele

8、cfans.com电子技术论坛CMyPoint{longx;//散乱点的横坐标longy;//散乱点的纵坐标}CMyedge{CMyPointm_point1;//边的起始点CMyPointm_point2;//边的终点intflag;//标识该边使用的次数可取：0，1，2intindexoftri;//标识该边所属三角形在CTriangleArray中的索引值}Cmytriangle{CMyPoi