一种求含孔洞多边形交、并、差集的新方法

赵 军，郝永兴

(兰州交通大学机电工程学院，甘肃 兰州 730070)

多边形的交、并、差集运算是计算几何、计算机图形学的一个基本问题。对这一问题的研究在多个领域具有重要的理论与实践意义，诸如GIS系统中进行叠加分析、几何造型中隐藏线的消除、线路板中电子元件的布局和线性规划等。目前，针对这一问题国内外也进行了不少研究，提出过一些算法[1-10]，其中有些不能处理含孔洞多边形。周培德[5]提出了一种较为可行的针对含孔洞多边形的算法，其算法复杂度为O(n2logn)。朱雅音等[6]通过扫描线法并利用多边形的拓扑信息确定任意多边形的交、并、差集，其算法复杂度为O((n+m+k)log(n+m+k))，其中m，n是多边形顶点数，k是两多边形的交点数。刘红军等[7]以两多边形差集为基础解决了布尔运算问题，可以解决多边形含孔洞问题，但算法中多边形求交后每段线段的中点需要进行点包含运算，使其算法复超过O(n2)。朱二喜[8]提出图形内角的概念，并利用它确定两个任意多边形的交并差，算法复杂度为O(k(n+m))+O(n+m+k)。崔璨和王结臣[9]基于梯形剖分求解多边形布尔运算，所提算法可以处理含孔洞多边形，时间复杂度为O(nlogm)，m为位于同一扫描条带上小线段的平均数。本文在文献[10]的基础上进一步提出一种解决含孔洞多边形布尔运算的方法，通过构造的一条双向“桥边”，使内环顶点序列并入外环顶点序列中，以消除内环，将多环顶点序列转换为单环，以便利用不含孔洞多边形布尔运算的交并差算法。针对两个多边形环包含嵌套的奇异情况，通过多边形和点的包含性来确定嵌套关系。……