连接不相交线段集成简单多边形新算法  

New Algorithm of Joining a Set of Segments into a Simple Polygon

作　　者：金辉 刘润涛[2] JIN Hui;LIU Run-tao(School of Sciences, Harbin University of Science and Technology, Harbin 150080,China;Institute of Information and Scientific Computing Technology, Harbin University of Science and Technology, Harbin 150080,China)

机构地区：[1]哈尔滨理工大学理学院,黑龙江哈尔滨150080 [2]哈尔滨理工大学信息与科学计算技术研究所,黑龙江哈尔滨150080

出　　处：《哈尔滨理工大学学报》2018年第6期138-145,共8页Journal of Harbin University of Science and Technology

基　　金：国家自然科学基金(11871181)

摘　　要：针对连接平面上n条线段构成简单多边形问题,给出了线段集能连接成一个简单多边形的一个充分条件。证明了对线段集S的端点进行Delaunay三角剖分可以找到端点的最近点或次最近点。以此为根据,给出了线段加入到简单多边形使得到的多边形总长度最小的方法,进而给出了连接给定线段集成一个简单多边形的算法。对新算法进行了时间复杂度分析,并给出了算法的正确性证明。通过实例对算法进行了对比,表明新算法可以得到更好的结果。For the problem of how to link a set of segments to a simple polygon with the shortest whole length,a sufficient condition that a given set of segments can be joined into a simple polygon is given.It is proved that the nearest point or second nearest point of the end point can be obtained in Delaunay triangulation for the end points of a set of segments S.Based on this result,the method of joining a segment into a polygon is given for getting the polygon with the shortest length.Then,a new algorithm for joining a set of segments into a simple polygon with shorter whole length is presented.The analysis is done on the time complexity for new algorithm.The correctness of new algorithm is proved.The comparison and analysis are done for the new algorithm to show that better result can be obtained with the new algorithm.

关 键 词：线段集 简单多边形 DELAUNAY三角剖分 四边形边长增值 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]