New Algorithm of Joining a Set of Segments into a Simple Polygon - JIN Hui; LIU Run-tao (Journal of Harbin University of Science and Technology)
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.