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

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

Connecting Non-intersecting Line Segments into a Simple Polygon (Line)

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.