Abstract:
Sufficient condition to connect line segment set
S in the plane into a simple polygonal line is proved.An algorithm is also presented for connecting line segment set
S in the plane into a simple polygon.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,and locally modify the line connections to delete these points of intersection;finally merge some simple polygons into a larger simple polygon.When the number
n of line segments in
S is large,divide-and conquer algorithm is applied to solve the problem.