【摘要】 提出了把多边形的边分为奇偶边的新思想 ,根据输入多边形A ,B之间边的拓扑关系 ,划分A ,B边为内边、外边、重叠边 3种 ,揭示A ,B与它们的交、并、差之间边的本质联系 ,进而描述了确定任意两个简单多边形交、并、差算法 算法的时间复杂度为O((n +m +k)log(n +m +k) ) ,其中n ,m分别是A ,B的顶点数 ,k是两多边形的交点数 算法建立在数学理论基础之上 ,很好地处理了布尔运算的奇异情形 ,比如重叠边 ,边与边相交于边的顶点等情形 本算法易于编程实现更多还原

【Abstract】 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更多还原