确定两个任意简单多边形交、并、差的算法  

An Algorithm for Determining the Intersection, Union, and Difference of Any Two Polygons

作　　者：朱雅音[1] 王化文[1] 万丰[1] 于雷易[2] 

机构地区：[1]武汉大学计算机学院,武汉430072 [2]武汉大学遥感与信息工程学院,武汉430072

出　　处：《计算机研究与发展》2003年第4期576-583,共8页Journal of Computer Research and Development

摘　　要：提出了把多边形的边分为奇偶边的新思想 ,根据输入多边形A ,B之间边的拓扑关系 ,划分A ,B边为内边、外边、重叠边 3种 ,揭示A ,B与它们的交、并、差之间边的本质联系 ,进而描述了确定任意两个简单多边形交、并、差算法 算法的时间复杂度为O((n +m +k)log(n +m +k) ) ,其中n ,m分别是A ,B的顶点数 ,k是两多边形的交点数 算法建立在数学理论基础之上 ,很好地处理了布尔运算的奇异情形 ,比如重叠边 ,边与边相交于边的顶点等情形A new idea about dividing edges of a polygon into odd edges and even edges is presented Based on the topology relationship between each edge of one polygon and another polygon, edges of both input polygons are divided into three types: interior edges, exterior edges, and overlap edges, and then an algorithm for determining intersection, union, and difference of the two polygons is put forward The algorithm runs in time O((n+m+k) log (n+m+k) ) in a worst presented case, where n and m are the vertex number of the two polygons respectively, and k is the number of intersection points Supported by mathematical theorems, the algorithm well resolves the problems in special cases, such as overlapped edges, edges intersection at the vertex of edges, etc The algorithm is easy to implement

关 键 词：计算机图形学 简单多边形 交并差算法 数学理论 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]