确定两个任意简单多边形空间关系的算法

• 作者: 万丰 朱雅音 王化文
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 多边形 空间关系 计算几何
• 年，卷（期）: 2003,（1）
• 所属期刊栏目: 学术探讨
• 页码范围: 91-93,108
• 页数: 4页
• 分类号: TP301.6
• 字数: 3460字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2003.01.030

摘要

阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数.该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现.算法的主要思想对确定两个简单多面体空间关系亦有参考价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王化文	武汉大学计算机学院	12	449	7.0	12.0
2	朱雅音	武汉大学计算机学院	3	73	3.0	3.0
3	万丰	武汉大学计算机学院	5	296	5.0	5.0