An Algorithm for Connecting Non-Intersecting Line Segments into a Simple Polygon (Line)
Zhou Pei-de · Journal of Engineering Graphics · 2002
In this paper a practical problem is presented, i.e. how to connect n line segments in the plane into a simple polygon or a simple polygonal line.And it has proved a sufficient condition which connects line segment set S in the plane into a simple polygonal line: there is a segment in S connecting non-adjacent vertices in convex hull CH(S). Otherwise an algorithm is also presented for connecting line segment set S in the plane into a simple polygon (line), its basic idea is first to compute the convex hull of line segment set S layer by layer, and change these convex hulls into simple polygons; then compute the points of intersection between polygons, there after delete these points of intersection; finally merge some simple polygons into a simple polygon. when the number n of line segments in S is larger, the divide-and conquer algorithm can be designed using the thought of the divide-and-conquer. This problem is better solved. Solving this problem by using computers has practical value.