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

Algorithm for Determing the Spatial Relationship between Two Polygons

作　　者：朱雅音[1] 万丰[1] 王化文[1] 

机构地区：[1]武汉大学计算机学院,武汉430072

出　　处：《计算机工程与应用》2003年第1期91-93,108,共4页Computer Engineering and Applications

摘　　要：阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。This paper presents a new idea about deviding edges of a polygon into odd edges and even edges,based on the spatial relationship between each edge of one polygon and another polygon,edges of both input polygons are devided into four types:interior edges,exterior edges,overlap edges,and intersect edges then,an algorithm for determing the spatial relationship between two polygons is put forward?The algorithm runs in time O((n+m)log(n+m))in worst presented case,where n and m are the vertex number of the two polygons separately?The algorithm is supported by mathematical theorems ,without the need to study special cases,is easy to be programed.The main idea of this paper is also useful in determing the spatial relationship between two polyhedra.

关 键 词：任意简单多边形 空间关系 算法 计算几何 数学理论 时间复杂度 

分 类 号：O18[理学—数学] TP301.6[理学—基础数学]