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

摘要

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