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

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

作　　者：周培德[1] 王树武[1] 李斌[1] 

机构地区：[1]北京理工大学计算机科学与工程系,北京100081

出　　处：《计算机辅助设计与图形学学报》2002年第6期522-525,共4页Journal of Computer-Aided Design & Computer Graphics

摘　　要：提出一个如何连接平面上 n条线段成一简单多边形或者简单多边形链的实际问题 ,并证明了连接平面上线段集 S成一简单多边形链的一个充分条件—— S中有一条线段连接凸壳 CH(S)中不相邻顶点 .提出了连接平面上线段集 S成一简单多边形或者简单多边形链的算法 ,其基本思想是首先逐层计算线段集 S的凸壳 ,并将这些凸壳改变为简单多边形 ;然后计算各多边形之间的交点 ,进而删去这些交点 ;最后合并若干个简单多边形为一个简单多边形 .当 S中线段数目 n较大时 ,用分治思想设计分治算法 ,较好地求解了这个问题 .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.

关 键 词：线段集 凸壳 简单多边形 简单多边形链 算法 复杂性 计算机 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]