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

摘要：

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

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

所属期刊栏目：23

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：109-114