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

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

针对连接平面上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.