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

摘要：

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

关键词：多边形、空间关系、计算几何

所属期刊栏目：39

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

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

页数：共4页

页码：91-93,108