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

• 作者: 周培德 李斌 王树武
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: 线段集 凸壳 简单多边形 简单多边形链 算法 复杂性
• 年，卷（期）: 2002,（6）
• 所属期刊栏目: 图形算法与技术
• 页码范围: 522-525
• 页数: 4页
• 分类号: TP301
• 字数: 3732字
• 语种: 中文
• DOI: 10.3321/j.issn:1003-9775.2002.06.007

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王树武	北京理工大学计算机科学与工程系	5	22	3.0	4.0
2	周培德	北京理工大学计算机科学与工程系	28	414	12.0	20.0
3	李斌	北京理工大学计算机科学与工程系	18	50	3.0	6.0