连接不相交线段成简单多边形(链)的算法

提出一个实际问题，即如何连接平面上h条线段成一简单多边形或者简单多边形链，并证明了连接平面上线段集S成一简单多边形链的一个充分条件，S中有一条线段连接凸壳CH（S）中不相邻顶点，另外还提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先逐层计算线段集S的凸壳，并将这些凸壳改变多边形；然后计算各多边形之间的交点，进而删去这些交点。最后合并若干个简单多边形为一个简单多边形，当S中线段数目n较大时，用分治思想可以设计分治算法，较好地求解了这个问题，利用计算机求解这个问题上有实际应用价值。

An Algorithm for Connecting Non-Intersecting Line Segments into a Simple Polygon (Line)

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.