多边形裁剪算法

多边形裁剪
刘运达【油源恒业北京 2003】
摘要：多边形裁剪与线剪裁相比具有更广泛的实用意义,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,也可以是凹多边形。

该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,占用的空间小特点。

其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法。

结果表明,新算法具有最简单的结构。

关键词: 计算机图形学;凹多边形;多边形剪裁;交点计算;单链表结构
1．引言
在图形系统中,二维裁剪是最为基础、最为常用的操作之一.其典型的应用是在图形的消隐处理等处理求交操作之中.对裁剪算法的研究主要集中在裁剪直线和裁剪多边形两方面.在实用中,多边形裁剪与线剪裁相比具有更高的使用率,因此它是目前裁剪研究的主要课题.多边形裁剪用于裁剪掉被裁剪多边形(又称为实体多边形)位于窗口(又称为裁剪多边形)之外的部分.多边形愈复杂,其裁剪算法就愈难以实现.现有的解决方案或者局限于某一类多边形,或者结构复杂、时间消耗大.
本文提出了一个新的多边形裁剪多边形的有效算法.其中的裁剪多边形和被裁剪多边形都可以是一般多边形,也可以是凹多边形.该算法只使用单线性链表数据结构,所以具有数据结构简单、占用空间少的特点,而且无须事先规定以什么方向输入图形的顶点.另外,该算法使用了一个新的具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.算法最终通过简单的遍历线性链表,可以得到每一个输出多边形.
2．基本概念与定义
为了便于下面对算法的讲解,本节首先介绍有关多边形裁剪的一些基本概念及术语.
(1) 多边形的边的方向与内外区域的关系.
如果多边形的边的方向是顺时针的(即多边形的顶点是以顺时针的顺序输入的),则在沿着多边形的边走时,右侧区域为多边形的内部;相反,如果多边形的边的方向是逆时针的,则在沿着多边形的边走时,左侧区域为多边形的内部.
(2) 进点和出点的定义.
设I是多边形S和C的一个交点,如果S沿着C的边界的方向在I点从C的外部进入C的内部,则称I为对于C的一个进点.反之,如果S在I点从C的内部出到C的外部,则称I为对于C的一个出点.
例如,对于如图1所示的多边形C和S及其交点I,若S的方向为逆时针方向S
1→S
2
→S
3
→S
4
→S
5
,
则I
5I
1
I
3
是对于C的进点,I
4
I
2
I
6
是对于C的出点.如果S的方向为顺时针方向S
5
→S
4
→S
3
→S
2
→S
1
,则
对于C来说,I
2I
4
I
6
是进点,I
1
I
5
I
3
是出点.
(3) 进点和出点的判定.
图1 进点和出点的定义
假设多边形S的一条边S
i S
i+1
与另一多边形C有交点.当点S
i
是C的外点时,则沿着S的走向,边
S i S
i+1
与C的第一个交点I必是C的进点;而当S
i
是C的内点时,I必是C的出点.由于沿着S的边界对于
C的进点和出点是交替出现的(两多边形的边重合或者两多边形在顶点处相交的情况除外.这类特殊情况的处理将在第5节进行讨论),所以,只需判断第1个交点是进点还是出点,其他交点的进出性则可依次确定.
对于一个多边形裁剪另一个多边形的过程,就是求两个多边形的相交区域(我们称其为结果多边形或输出多边形).结果多边形是由实体多边形位于裁剪多边形内的边界和裁剪多边形位于实体多边形内的边界组成的.
3．算法的数据结构
多边形裁剪算法需要一个适当的数据结构来存储多边形及交点,并能够在其上进行正确的操作.算法的每个多边形由一个单链表来表示,单链表的每一个结点按序(多边形顶点输入的顺序)存储着多边形的一个顶点.最后一个结点的指针指向第1个结点(循环单链表).每个链表由一个头指针指向其第1个结点,实体多边形链表的第1个结点由头指针HeadS指示;裁剪多边形链表的第一个结点由头指针HeadC指示.结点的结构定义如下:
struct Vertex
{
double x,y;
BOOL inters,used;
pointer next;//pointer 表示指针类型
};
struct Intersection
{
double x,y;
BOOL inters,used;
pointer next1,next2; //pointer 表示指针类型
};
其中的指针域用于将交点分别插入到两个多边形的单链表中,第1指针域next1用于插入实体多边形链表;第2个指针域next2用于插入裁剪多边形链表.这样的数据结构定义使算法在求出一个交点时只需建立1个Intersection(交点)类型的结点,并分别插入到两个多边形的单链表中即可。

注意: 实体多边形链表中的交点的进出性是对裁剪多边形而言的,而裁剪多边形链表中的交点的进出性则是对实体多边形而言的.
在这两个数据结构的定义中,布尔类型域inters用于区分该结点是否Intersection(交点)类型的结点;used域用于有多个输出多边形时.所有交点的used域的初值都为0,当一个交点被输出时,其used域被置为1. 裁剪结果可能得到多个分立的输出多边形,因此需要设立一个指针链表Out,其每个结点有一个指针域polygon指向一个输出多边形链表的第一个结点.该指针链表的结点结构如下:
struct Out
{
pointer polygon; //pointer 表示指针类型
pointer next; //pointer 表示指针类型
};
4．算法描述
新算法分为3个阶段.第1个阶段,判断及计算第1个交点,并由其进出性判断两个多边形是否同向.如果不同向,则将裁剪多边形链表反向,然后将该交点插入到两个多边形的链表中.第2阶段,依次以实体多边形的每一个边对裁剪多边形进行直线裁剪操作,判断及计算其余交点,并以正确的顺序插入到两个多边形的链表中.第3阶段,遍历整个链表,输出最终结果.
我们以下面的引理开始算法第1阶段的描述.
引理1. 如果两个相交多边形的边的取向相同(均为顺时针或逆时针方向),则对一个多边形是进点的交点对另一个多边形必是出点.
证明:设分别属于两个相交多边形S和C的两个相交边为S
e 和C
e
,我们首先考虑两个相交多边
形的边的取从下向上穿过S(图3a的情况)),则由图3显然可见,C经过交点从多边形S内走向S外,即该交点是对于多边形S的出点;而另一方面,边S向均为顺时针方向的情况.在这种情况下,多边形边的右侧为多边形内侧(在图3中由阴影表示).考虑两边之间的夹角,由于此夹角是由两边的相对位置决定的,所以我们可以将一个边的方向固定而讨论另一个边方向变化的各种情况.在图
3中,设S
e 边的方向是从左向右固定不变的,如果C
e
的正向与S
e
的正向的夹角在0o~180o之间(即C
eeee
则是经过该交点从多边形C外走向C内,即该交点是对于多边形C的进点.
(a) S e和Ce的正向的夹角在0o和180o之间(b) Se和Ce的正向的夹角在180o和360o之间
图3 当两个多边形的相交边S e和C e的取向均为顺时针方向时,对一个多边形是进点的交点对另一个多边形必是出点(阴影表示多边形内侧)
如果C e的正向与S e的正向的夹角在180o~360o之间(即C e从上向下穿过S e(如图3(b)所示),则由图显然可见,该交点对于多边形S是进点,而对于多边形C则是出点.这就是我们要证明的结论.
对于两个相交多边形的边的取向均为逆时针方向的情况,可用相同的方法证明该引理.
根据该引理,对其中一个多边形求出一个进点或出点以后,在两个多边形方向相同的情况下,其对另一个多边形的进出性也就确定了.这样,如果两个多边形的方向相同,则在求出交点时只需判断和标记它对其中一个多边形是进点还是出点.它对另一个多边形的进出性则相反.而由第1节的讨论可知,由于沿着一个多边形的边界,在其上的进点和出点是交替出现的.所以只需标记第1个交点是进点还是出点,其他交点的进出性则可依次确定.最终我们得出一个结论:如果两个多边形的方向相同,则要标记所有交点对于两个多边形的进出性,只需标记任何一个多边形链表中的第1个交点的进出性即可(在后面的算法描述中,我们用变量Sin来标记实体多边形链表中的第1个交点对于裁剪多边形是否为进点).因此,新算法的第1步就要是判断两个多边形是否同向.如果不同向,则将裁剪多边形链表反向,使两个多边形的方向相同.
判断两个多边形是否同向,是通过判断一个交点(如第1个交点)对于两个多边形的进出性来完成的.如果该点对于实体多边形的进出性与对于裁剪多边形的进出性不同,则可知两个多边形取向相同;否则,两个多边形的取向相反. 新算法将交点的计算与进出性判断合成一步进行.当
一个多边形的一个边对另一个多边形进行直线裁剪操作之后,如果有交点,即可根据交点在这个边上的排序的奇偶性来确定交点对另一个多边形的进出性.这样在计算交点的同时也确定了该
交点的进出性.详细的描述见第5节
下面是算法的第1部分的形式描述,其中指针变量PS和PC分别指向实体多边形链表和裁剪多边形链表中正在被处理的当前结点.另外,我们把由结点PS↑和其下一个结点PS↑.next↑定义
的边简称为由PS指向的边.
PS=HeadS;
DO
以PS指向的边与裁剪多边形进行直线裁剪操作(即求交点的操作,见第4节);
if (上述直线裁剪操作有交点)
{
将每个交点(可能有多个)按其在该边上的顺序插入到实体多边形链表和裁剪多边形链表的对应相交边的两个结点之间;
由Sin标记插入到实体多边形链表中的第1个交点对于裁剪多边形的进出性,Sin=1表示出;
令PF指向第1个交点结点,以备算法的第3阶段使用;
将PC指向该交点在裁剪多边形上的对应边;
以PC指向的边与实体多边形进行直线裁剪操作;
求出上述第1个交点对于实体多边形的进出性;
if(上述第1个交点对于实体多边形和裁剪多边形的进出性相同) 逆转裁剪多边形的链表;
令PS指向实体多边形的下一个边;
转到算法的第2阶段;
}
令PS指向实体多边形的下一个边;
WHILE PS!=HeadS;
If（实体多边形的每个点是否都在裁剪多边形里）
{
直接输出实体多边形链表。

}
else
{
输出裁剪多边形链表}
两个多边形无交点,
算法结束;
在第2阶段,算法从第1阶段求出交点的那个实体多边形边的下一个边开始,用每一个实体多边形边与裁剪多边形求交点,并如图2所示,给每个交点建立一个包含该交点坐标的新的交点结点,然后将其插入到实体多边形链表和裁剪多边形链表的对应相交边的两个结点之间.例如,一个交点是由结点PS↑和其下一个结点PS↑.next↑所定义的实体多边形的边与由结点PC↑和其下一个结点PC↑.next↑所定义的裁剪多边形的边相交形成的,那么该交点结点就应该被插入到实体多边形链表的结点PS↑和其下一个结点PS↑.next↑之间,同时被插入到裁剪多边形链表的结点PC↑和其下一个结点PC↑.next↑之间.当一个边上有多个交点时,则以该边的方向为序将这些交点插入其中.例如,如果该边的方向是从左向右的斜线,则可按交点的x坐标的大小顺序插入这些交点.
在这个阶段,算法不需要标记交点的进出性,因为如前所述,算法只需在第1阶段用变量Sin 来标记实体多边形链表中的第1个交点对于裁剪多边形的进出性,其余交点对于两个多边形的进出性便由如前所述的规律可知.下面是算法的第2部分的形式描述.
DO
以PS指向的边与裁剪多边形进行直线裁剪操作;
if (上述直线裁剪操作有交点)
{
将每个交点按其在该边上的顺序插入到实体多边形链表和裁剪多边形链表的对应相交边的两个结点之间;
}
令PS指向实体多边形的下一个边;
WHILE PS!=HeadS;
转到算法的第3阶段;
在算法的第3阶段,通过遍历已插入交点结点的实体多边形和裁剪多边形链表来跟踪结果多边形的边界,最后产生输出多边形链表.
跟踪一个结果多边形的边界是以实体多边形链表中的一个进点(对于裁剪多边形)开始的.从该进点到实体多边形链表中的下一个交点(记为N1)之间的实体多边形的边界全部是结果多边形的边界.N1既是对于裁剪多边形的出点也是对于实体多边形的进点,因此从N1点开始到裁剪多边形链表中的下一个交点之间的裁剪多边形的边界全部是结果多边形的边界(如图1所示).输出这些边界.重复此过程,一直到回到实体多边形链表中的开始进点为止,便跟踪输出了一个结果多边形.在上述过程中,实体多边形链表中的进点(对于裁剪多边形)的used域被标记为1,以表明从它开始的边界已经被输出过.“used域”用于有多个结果多边形的情况.
算法第3阶段的遍历是以实体多边形链表的顺序进行的.从实体多边形链表中的第1个进点开始,如果该进点(当前进点)的used域为0(表明它未被输出过),则将其置为1,并执行上一段所述的跟踪过程输出一个结果多边形;如果该进点的used域为1,则走到实体多边形链表的下一个进点,即该进点的下一个交点的下一个交点(如前所述,在多边形链表中交点的进出性是相隔分布的).以下一个进点为当前进点,重复此过程,一直到回到实体多边形链表中的第1个进点为止.所有的进点都被访问过,所有的结果多边形也都被输出.至此,算法结束.下面是算法第3阶段的形式描述.
if Sin=0 令PF指向实体多边形链表中的下一个交点结点,以确保PF指向第1个进点;
PP=PF;
DO
if PP所指的交点结点的used域为0
{PO=PP;
建立一个新的输出多边形链表,并将指向该链表的头指针加入到指针链表Out的最后(在polygon域当中);
repeat
将PO 所指的交点结点(一定是出点)的used 域置为1;
将从PO 所指的交点结点开始(用next1指针域)到下一个交点结点(记为N1)之前的实体多边
形链表中的结点加入到输出多边形链表的最后,并使PO 指向N1;
将从PO 所指的交点结点开始(用next2指针域)到下一个交点结点(记为N2)之前的裁剪多边
形链表中的结点加入到输出多边形链表的最后,并使PO 指向N2;
WHILE PO!=PP
}
else 使PP 指向实体多边形链表中的下一个出点结点(即下一个交点结点的下一个交点结点);
until PP=PF;
算法结束,输出多边形链表由指针链表Out 的polygon 域指出.
5.焦点的计算和判断
由上述分析可知,多边形裁剪的交点判断和计算是以多边形窗口的线裁剪为基础的,因为在多边形裁剪中求交点时是用实体多边形的每一条边与裁剪多边形求交点,即为线裁剪.
本文采用一个更有效的、适用于一般多边形的判断和计算交点的方法,我们称其为错切变换法.下面加以描述. 设多边形窗口C 有n 条边,C 的顶点vi 的坐标为(xi ,yi ),i =1,2,…,n ;被裁剪线段为L ,其端点A 和B 的坐标分别为(xa ,ya )和(xb ,yb ),如图6所示.
图6 多边形窗口与被裁剪线段
下面以x b ≥x a 情况为例,记∆x =x b −x a ,∆y =y b −y a ,并假定∆x ≠0,∆y ≠0,否则L 将与一条坐标轴平
行,而这种情况无须错切变换,使执行过程更为简单.
在设计裁剪算法时,最主要的考虑是尽可能减少不必要的交点计算.本方法给出了很简单的判断条件,可以不计算落在窗口边的延长线上的非有效交点.对于落在被裁剪直线的延长线上的非有效交点,则只有当它被计算出之后才能确定其是否有效(即在直线的两端点之间).
首先对C 和L 施加相同的错切变换,用沿Y 轴方向的错切变换将L 变换成与X 轴平行(水平)的方向.变换的分量形式是x ′=x; y ′=x.d+y,其中x ′和y ′表示错切变换后的坐标值(下面均以这种形式表示变换后的点或坐标).显然,错切变换对这些点的x 坐标没有影响,如图7和图8所示.设直线L 与Y 轴的交点为I (0, yc ),这里yc =xa .d +ya .容易验证,经错切变换后,直线AB 变为直线y =yc .
图7 错切变换图8 图6经错切变换后的裁剪多边形与被裁剪线段(变为水平线)
错切变换是一种仿射变换,它不能保留图形的度量性质,会引起图形形状的改变,但是直线之间的相对关系(相交关系)是不变的.由于对C和L进行错切变换后,L变成了水平直线,所以很容易判断和计算交点.又由于变换前后的相交关系及其交点的x坐标都没有变化,因此在(错切变换后)求出交点以后只需对其y坐标进行反错切变换即可.从上面的错切变换公式可见,错切变换及其反变换的计算量是很小的. 经过错切变换,容易看出,C的一条边与直线AB相交的条件是该边两顶点变换后的点vi−1′(xi−1′,yi−1′)和vi′(xi′,yi′)位于直线y=yc两侧,或至少一个变换后的顶点落在该直线上.我们先讨论前一种情况.这时,线段vi−1′vi′与直线y=yc的交点的x坐标可计算如下:
上述过程可以形式化地描述如下:
(1) 计算∆x,∆y,d,y
c ,y
a
′和y
b
′;
(2) 对每个v
i ,计算y
i
′=x
i
⋅d+y
i
,(i=1,2,…,n);
(3) 令y
0′=y
n
′; j=1;
(4) 对每个i(1≤i≤n),依次作:
if (y
i−1′>y
c
)AND (y
i
′<y
c
) OR (<y
c
)AND (y
i
′>y
c
) then
{用式(1)计算交点的x坐标Ix
j
; j=j+1}
如上一节所述,新算法在第1次计算交点的同时也确定了该交点的进出性.具体的方法是,根据交点在被裁剪直线上的奇偶性来确定交点的进出性,奇序数交点是进点,偶序数交点是出点.由于被裁剪直线在错切变换后变成了水平直线,所以根据交点的x坐标的大小就可以决定交点在被裁剪直线上的顺序.如果求出一个交点的x坐标之后,经过判断发现该交点位于被裁剪直线的延长线上而不在直线的两端点A′和B′之间,则该交点不被插入到多边形链表中,但是去掉该交点可能对被裁剪直线上其他交点顺序的奇偶性产生影响.我们的办法是,如果被裁剪直线的方向是从A′到B′,则对A′侧延长线上的交点不保留,但只累计个数,以保持有效交点顺序的正确性,对B′侧延长线上的交点不保留也不累计;如果被裁剪直线的方向是从B′到A′,则只累计B′侧延长线上的交点个数。

6．结论
本文提出了一个有效的多边形裁剪的算法,它适用于凹多边形。

该算法不仅可以求多边形的“交”(多边形裁剪),而且也可以求多边形的“并”和“差”.另外,还适用于有多个分立的结果多边形的情况,具有一般性.整个算法采用单链表作为输入输出的数据结构,且无须限制输入
多边形的方向.本文还提出了一些新的技术和方法作为该算法的基础.算法无论在占用存储空间方面,还是在计算量和运行速度方面都是很好的.
参考文献：
刘勇奎, 高云, 黄有群写的“一个有效的多边形裁剪算法”文章
刘勇奎,颜叶,石教英.一个有效的多边形窗口的线裁剪算法.计算机学报,1999,22(11):1209~1214.。