一种利用图形内角的多边形布尔运算新算法

２０１　１年　第２期　工程图学学报　

Ｊ０ＵＲＮＡＬ　ＯＦ　ＥＮＧＩＮＥＥＲＩＮＧ　ＧＲＡＰＨＩＣＳ　２０１　１　Ｎｏ．２　

一种利用图形内角的多边形布尔运算新算法　

朱二喜　一，　何援军２　

（１．江苏信息职业技术学院计算机工程系，江苏无锡２１４１０２　

２．上海交通大学计算机科学与工程系，上海２００２４０）　

摘　要：现有的平面多边形布尔运算在一般情况下可以快速地获得正确结果，但如　

遇到奇异情况，则会产生错误。因此，采用图形内角概念分析奇异情况，并在原有交点遍历　

算法框架基础上给出一种全局化的奇异处理算法。与其他的多边形布尔运算算法相比，该算　

法对奇异的分析更为简洁有效，且具有高效性和鲁棒性。　

关键词：计算几何；多边形布尔运算；图形内角布尔运算；奇异情况　

中图分类号：ＴＰ　３９１　

文献标识码：Ａ　文章编号：１００３—０１５８（２０１１）０２—００１０—１０　

Ａ　Ｎｅｗ　Ａｌｇｏｒｉｔｈｍ　ｏｆ　Ｐｏｌｙｇｏｎｓ’Ｂｏｏｌｅａｎ　Ｏｐｅｒａｔｉｏｎｓ　Ｕｓｉｎｇ　Ｉｎｔｅｒｉｏｒ　Ａｎｇｌｅ　

ＺＨＵ　Ｅｒ—ｘｉ　一，ＨＥ　Ｙｕａｎ－ｊｕｎ２　

（１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆＣｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉａｎｇｓｕ　Ｉｎｓｔｉｔｕｔｅ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｘｉ　Ｊｉａｎｇｓｕ　２１４１０２，Ｃｈｉｎａ；　

２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈａｎｇｈａｉ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２００２４０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｕｒｒｅｎｔ　ａｌｇｏｒｉｔｈｍｓ　ｏｆ　ｔｈｅ　ｐｏｌｙｇｏｎｓ’ｂｏｏｌｅａｎ　ｏｐｅｒａｔｉｏｎｓ　ｃａｎ　ｇｉｖｅ　ｃｏｒｒｅｃｔ　

ｒｅｓｕｌｔｓ　ｒａｐｉｄｌｙ　ｅｎｏｕｇｈ　ｉｎ　ｇｅｎｅｒａｌ　ｃａｓｅｓ．Ｂｕｔ　ｔｈｅｒｅ　ａｒｅ　ｅｒｒｏｒｓ　ｗｈｅｎ　ｉｔ　ｃｏｍｅｓ　ｔｏ　ｑｕｅｅｒ　ｃｏｎｄｉｔｉｏｎｓ．　

Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｍｅｔｈｏｄ　ｔｏ　ａｎａｌｙｚｅ　ｑｕｅｅｒ　ｃｏｎｄｉｔｉｏｎｓ　ｕｓｉｎｇ　ｃｏｎｃｅｐｔ　ｏｆ　ｇｒａｐｈｉｃ　ｉｎｔｅｒｉｏｒ　ａｎｇｌｅ，　

ａｎｄ　ｇｉｖｅｓ　ａ　ｎｅｗ　ｏｖｅｒａｌｌ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｑｕｅｅｒ’Ｓ　ｔｒｅａｔｍｅｎｔ　ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｔｈｅ　ｏｒｉｇｉｎａｌ　

ｉｎｔｅｒｓｅｃｔｉｏｎ—ｔｒａｖｅｒｓａｌ　ａｌｇｏｒｉｔｈｍｓ’ｆｒａｍｅｗｏｒｋ．Ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｏｔｈｅｒ　ａｌｇｏｒｉｔｈｍｓ　ｏｆ　ｐｏｌｙｇｏｎｓ’　ｂｏｏｌｅａｎ　ｏｐｅｒａｔｉｏｎｓ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ｉｓ　ｍｏｒｅ　ｓｉｍｐｌｅ　ａｎｄ　ｅｆｆｅｃｔｉｖｅ　ｆｏｒ　ａｎａｌｙｓｉｓ　ｏｆ　ｑｕｅｅｒ　

ｃｏｎｄｉｔｉｏｎｓ．　

Ｋｅｙ　ｗｏｒｄｓ：ｃｏｍｐｕｔａｔｉｏｎａｌ　ｇｅｏｍｅｔｒｙ；ｐｏｌｙｇｏｎｓ’ｂｏｏｌｅａｎ　ｏｐｅｒａｔｉｏｎ；ｇｒａｐｈｉｃ　ｉｎｔｅｒｉｏｒ　ａｎｇｌｅ’Ｓ　

ｂｏｏｌｅａｎ　ｏｐｅｒａｔｉｏｎｓ；ｑｕｅｅｒ　ｃｏｎｄｉｔｉｏｎｓ　

平面多边形的布尔运算是计算几何、计算机　

图形学中的基础问题之一，在几何和实体造型中　

有着广泛的应用价值，特别是机械绘图工具　

ＡｕｔｏＣＡＤ、ＵＧ等等中重要算法：同时也是ＧＩＳ　叠加分析的理论基础，因此，设计一个稳定而有　

效的多边形布尔运算的算法是非常必要的。　

该文提出一种非常有效的任意多边形布尔　

运算算法，可以对任意平面多边形（凹或凸、有　

收稿日期：２００９—１２—０１　作者简介：朱二喜（１９８１一），男，江苏无锡人，助教，硕士，主要研究方向为几何计算的理论与算法。

　第２期　朱二喜等：一种利用图形内角的多边形布尔运算新算法　

洞或无洞、自相交）进行交并差的操作。该算法　

基于一种对几何模型进行数学形式化的建模，无　

需考虑布尔运算中各种奇异情况，从而使模型有　

较高的效率和较强的鲁棒性，能够在计算几何　

学、计算机图形学、地理信息系统、地质灾害预　

测评估及土木工程等领域中得到广泛应用。　

１　国内外研究现状　

在多边形布尔运算领域里，有很多现有的成　

果，多数按照多边形集合运算和剪切的形式提　

出。Ｍ．ｄｅ　Ｂｅｒｇ的理论　给出了布尔运算很多有用　

的思想，比如平面扫描算法、子区域划分的叠合　

算法、表示多边形的数据结构等。Ｒｉｖｅｒｏ［２］和　

Ｖａｔｔｉ［３］所著的理论是其中最有价值的两篇。在文　

献［３］的论文中，作者对当时已有的相关算法和论　

文做了详尽的总结，其中提到了《Ａｎ　ｅｆｆｉｃｉｅｎｔ　

ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｌｉｎｅ　ａｎｄ　ｐｏｌｙｇｏｎ　ｃｌｉｐｐｉｎｇ》　、　（（Ｒｅｅｎｔｒａｎｔ　ｐｏｌｙｇｏｎ　ｃｌｉｐｐｉｎｇ））［　、（（Ｖｅｃｔｏｒ　ａｎｄ　

ｒａｓｔｅｒ　ｈｉｄｄｅｎ　ｓｕｒｆａｃｅ　ｒｅｍｏｖａｌ　ｕｓｉｎｇ　ｐａｒａｌｌｅｌ　

ｃｏｎｎｅｃｔｅｄ　ｓｔｒｉｐｅｓ））ＩｏＪ、何援军教授提出的基于结点　

特征值的二维布尔运算Ｉ７】，这四篇论文可以对非　

凸的，带有内环的多边形之间的集合运算进行有　

效的操作，但是不能胜任白相交的多边形之问的　集合运算。而在ＷｅｉｌｅｒＩｓ－９］两篇论文中所提到的算　

法则可以对非凸的，带有内环的，且自相交的多　

边形进行集合运算。在Ｖａｔｔｉ的论文中还提到了　

判断一个点在多边形内部还是外部的方法，其理　论基础来源于Ｆｏｌｅｙ等人【Ｊ　ＵＪ提出的Ｗｉｎｄｉｎｇ　

Ｎｕｍｂｅｒ概念。Ｒｉｖｅｒｏ和Ｆｅｉｔｏ【ｌｕ提出了一个全新　的算法，该算法用到了Ｒｉｖｅｒｏ［　］中简单链的概　

念，这个算法将用简单链表示的两个多边形进行　运算后，得出了一个同样用简单链表示的结果多　

边形，与Ｇｒｅｉｎｅｒ【ｊｌｊＪ的方法一样，这个算法也是　

可以对自相交的，有孔洞的，凹的多边形进行运　

算的。　

该文主要从图形内角新概念开始，对多边形　

布尔运算进行重新全局化建模，实现其算法，将　

布尔运算中奇异情况在图形内角新概念下进行　

了讨论和研究，并处理完善。　

２图形内角提出及其布尔运算的定义　

角的定义是从一点出发，引出两条射线，由　这两条射线所围成的区域称作角域，而这角域所　

对应的角就是这一点与两条射线所构成的角（如　

图１所示），两条射线就是角域的边界，称之为　

角边。不失一般性，由封闭图形边界走向的定义，　

图形的外边界为逆时针走向，内边界为顺时针走　

向，即当人沿着封闭图形的边界行走时，他的左　

手指向图形的内部，右手指向图形的外部。如果　

角边为外边界，角域的边界也为逆时针走向；如　

果角边为内边界，角域的边界也为顺时针走向；　

即当人沿着角域的角边行走时，他的左手指向角　

域的内部，右手指向角域的外部。　

定义１　图形内角　设Ｅ１与　是图形　的　

两条相邻边，如果Ｅ　与　的夹角　封闭多边　

形区域内，称　为图形　的图形内角（如图１所　

示）；否则称之为图形外角。　

Ｄ　

Ｃ　

图１　图形内角不意图　

２．１　多边形的顶点、边与角的关系　

设　１，Ｙ１），Ｂ（ｘ２，Ｙ２），Ｏ（ｘ３，Ｙ３）是一个图形的　

环上的连续三个顶点所示，有　、Ｄ两点构成的　

多边形的一边ＡＯ，有Ｄ、　两点构成多边形的　

一边ＯＢ，ＡＯ、ＯＢ是多边形两条相邻的边。ＡＯ、　

ＯＢ同时形成了一个图形内角，记为　。　

ＩＡｏｌＺ＝（ＸＩ＿Ｘ３）　＋（ｙｌ－ｙ３）　

ｌ０８１　＝（Ｘ２－Ｘ３）　＋（Ｙ２－－Ｙ３）　（１）　

Ｉ　『２＝（Ｘ１－Ｘ２）　＋（Ｙｌ－Ｙ２）　

ｃｏ　：　ｆ±！　垒！：二』　皇』：　

２ｌＡＯＩＩＯＢＩ　记为ｆ　

上式ｔＥ［０，１］，　为ａｒｃｃｏｓｔ，ｎ＋ａｒｃｃｏｓｔ。再借助　

于点与直线的关系；　

点在ＡＯ的负区域，　∈（０。，ｌ８０。），　为　

ａｒｃｃｏｓｔ；　Ｂ点在ＡＯ的正区域，　∈（１８０。，３６０。１，　为　

兀＋ａｒｃｃｏｓｔ。　因此，在多边形中，连续的三个顶点可以确　

定两条相邻的边，并且也可以确定有这两条相邻　

的边所构成的图形内角的大小。图形内角与顶点　

存在内在联系，所以在确定图形内角的布尔运算　

时，只需要考虑多边形相邻的顶点就可以了。

　工程图学学报　２０１１年　

２．２图形内角布尔运算　

两条直线相交，交点不在两条直线端点上，　

这样构成了四个角（如图２所示），也形成了四　

个角域，这四个角域有明显的特征。由直线标准　

方程的定义，一点到直线的距离Ｄ的公式，很好　

地判断该点与直线的关系。并且由Ｄ的符号决定　

该点是在直线的正区域、负区域还是直线上。　

平面上任何点Ｐ（Ｘｐ，Ｙｐ）Ｎ直线Ｅ：Ａｘ＋Ｂｙ＋　

Ｃ＝０的距离可表示为　

ｎ　（ＡＸｐ＋　＋Ｃ）　ｆ２、　一—　一　…　

当Ｄ＞０时，表示Ｐ点在直线Ｅ的正区域，记　

为Ｅｐ＋；Ｄ＜０时，表示尸点在直线Ｅ的负区域，记　

为　；Ｄ＝０时，表示Ｐ点在直线Ｅ上，记为　。　

通过点与直线的距离的符号位，对这四个角　

的特征进行如图２分类。１，２，３，４角域都具有　

不同的特征，直线Ｅ１与　，包括四个角的共同　

顶点０点也各具各自的特征。　

图２两条直线形成的角　

可以通过表１来详细描述上面的特征，这样　

判断点Ｐ　，　落在两条直线所构成的四个角域的　

哪个位置上（包括Ｅ１和　直线上）。　

表１点与直线所形成角的关系　

在这样的情况下，判断一点Ｐ（ｘ，　）是否在一　

个图形内角的角域内，可以用如下判别表达式：　

Ａ０８＋＆＆　０Ｐ＿＆＆Ｄ　）ｌ　ｌ　ＡＯＢ＋＆＆ＮＯＴ　

Ｏｐ＋＆＆ＯＢｐ＋）　（３）　

下面定理１给出两角的布尔运算理论基础。　定理１记　是确的角域，　是　的角　

域，且口、贿共同的顶点，如果　

当中的点都在　中，这时称确包含　。　

如果　当中的点都不在　中，这时称　是确　

在３６０。下的补集，记为　。　

（１）　ｕ　是｛　，　）ｌ　）∈　Ｖ　）∈　｝　

所形成的角域所对应的角；　

（２）　ａＮ腽｛　，Ｙ）Ｉ　，　∈　八　，　∈　）　

所形成的角域所对应的角；　

（３）　腥｛　，Ｙ）Ｉ　，　）∈　八　，　）不在　）　

所形成的角域所对应的角。　

例如：两个角Ｚ＇ＡＯＢ与＿／ＣＯＤ，其顶点都是　

０点，位置关系如图３所示，Ｄ点落在　加８内，　ｃ点落在　∞口之外。由上面的定理１可得到：　

ＺＡＯＢ　Ｕ　ＣＯＤ之后为　ＣＯＢ；　

ＡＯＢＮ　ＣＯＤ之后为　ＡＯＤ；　

∞一　ＣＯＤ之后为ＺＤＯＢ。　

Ｃ　

图３／ＡＯＢ与ＬＣＯＤ的位置关系　

如果多边形一条边除了两个端点之外在中　

间有一个点，则这个点就形成一个角度为１８０。　

的新图形内角，而这个点成为新图形内角的顶　

点。另外，在多边形中，图形内角的角度在（０。，　

３６０。）之间，所以后文中的算法当两个图形内角之　

交为零度，它就形成了一条线段，当两个图形内　

角之并为３６０ｏ，说明该两图形内角的顶点在图形　

的内部（包容性测试角度判别法），算法执行的　

时候应该消除。　

２－３图形内角的布尔运算实现　

此多边形的布尔运算算法主要依据角的布　

尔运算理论。在多边形中，点、边、角存在紧密　

地联系，根据公式（１），可以看出多边形的图形　

内角完全可以有相邻的三个顶点决定，又有公式　

（３）可以判断点在角域里的条件，因此，在求　

图形内角的布尔运算时，主要考察多边形顶点的