一个有效的多边形裁剪算法
摘要：多边形多裁剪与线剪裁相比具有更广泛的实用意义，因此它是目前裁剪
研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形，既可以是凹多边形，也可以是有内孔的多边形.该算法不仅可以求多边形的“交”(多边形裁剪)，而且可以求多边形的“并”和“差”.它是以所提出的一系列新方法和新技术为基础而形成的.首先，该算法使用单线性链表数据结构，与其他使用双链表或树结构的算法相比，具有占用空间少及处理速度快的特点；其次，到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理，减少了算法对多边形链表的遍历次数，而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后，判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法，进一步加快了算法的运行速度.与其他同类算法进行了比较，结果表明，新算法具有最简单的结构和最快的执行速度.
正文:
1.基本概念与定义.
为了便于下面对算法的讲解，本节首先介绍有关多边形裁剪的一些基本概念及术语.
(1) 多边形的边的方向与内外区域的关系.
如果多边形的边的方向是顺时针的(即多边形的顶点是以顺时针的顺序输入的)，则在沿着多边形的边走时，右侧区域为多边形的内部；相反，如果多边形的边的方向是逆时针的，则在沿着多边形的边走时，左侧区域为多边形的内部.对于具有孔洞的多边形，只要把内孔边界和外边界以相反的方向表示，由上面的规则判断多边形的内部仍然适用.
(2) 进点和出点的定义.
设I是多边形S和C的一个交点，如果S沿着S的边界的方向在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
5
I
1
I
3
是对于C的进点,I
4
I
2
I
6
是对于C的出点.如果S的方向为
顺时针方向S
5→S
4
→S
3
→S
2
→S
1
，则对于C来说,I
2
I
4
I
6
是进点,I
1
I
5
I
3
是出点
(3) 进点和出点的判定.
假设多边形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个
交点是进点还是出点，其他交点的进出性则
可依次确定.
对于一个多边形裁剪另一个多边形的过
程，就是求两个多边形的相交区域(我们称其
为结果多边形或输出多边形).结果多边形是
由实体多边形位于裁剪多边形内的边界和裁
剪多边形位于实体多边形内的边界组成的.
2.新算法的数据结构
多边形裁剪算法需要一个适当的数据结
构来存储多边形及交点，并能够在其上进行
正确的操作.在Weiler的算法中，输入多边形
组成一个树形结构.Greiner-Hormann算法采
用双向链表的结构，每个多边形由一个双向链表来表示.每到一个交点，就将其分别插入到实体多边形和裁剪多边形的两个双向链表中.Greiner-Hormann算法使用了线性链表，与Weiler算法的树形结构相比降低了数据结构的复杂性.本文的算法采用单链表来表示所有的多边形(输入和输出)，与Greiner-Hormann算法的双向链表结构相比，不仅由于少用了一个指针域而节省了存储空间，而且还进一步降低了数据结构的复杂性.我们知道，在插入一个交点时，双向链表所需修改的指针数是单链表的2倍，因此，对单链表的操作不仅简单，而且也省时.
新算法的每个多边形由一个单链表来表示，单链表的每一个结点按序(多边形顶点输入的顺序)存储着多边形的一个顶点.最后一个结点的指针指向第1个结点(循环单链表).每个链表由一个头指针指向其第1个结点，实体多边形链表的第1个结点由头指针HeadS指示；裁剪多边形链表的第一个结点由头指针HeadC指示.结点的结构定义如下(其中coordinates表示坐标类型，用于存储顶点或交点的坐标值;pointer表示指针类型):
Vertex={x, y: coordinates;
inters, used: Boolean;
next: pointer;
}
交点的数据结构如下:
Intersection={x, y: coordinates;
inters, used: Boolean;
next1, next2: pointer;
}
其中的指针域用于将交点分别插入到两个多边形的单链表中，第1指针域next1用于插入实体多边形链表；第2个指针域next2用于插入裁剪多边形链表.这样的数据结构定义使算法在求出一个交点时只需建立1个Intersection(交点)类型的结点，并分别插入到两个多边形的单链表中，而不像Greiner-Hormann算法那样，要建立两个交点类型的结点，然后将每一个插入到一个多边形的链表中，而插入到两个链表中的这两个交点类型的结点之间也要用指针域neighbor彼此相连.
数据结构与算法论文应该注意的是，实体多边形链表中的交点的进出性是对裁剪多边形而言的，而裁剪多边形链表中的交点的进出性则是对实体多边形而言的.
在这两个数据结构的定义中，布尔类型域inters用于区分该结点是否Intersection(交点)类型的结点;used域用于有多个输出多边形时.所有交点的used域的初值都为0，当一个交点被输出时，其used域被置为1.
裁剪结果可能得到多个分立的输出多边形，因此需要设立一个指针链表Out，其每个结点有一个指针域polygon指向一个输出多边形链表的第一个结点.该指针链表的结点结构如下:
Out={polygon: pointer;
next: pointer;
}
图2给出了对图1的多边形进行裁剪时,Greiner-Hormann算法和新算法所使用的数据结构.可见，新算法的数据结构要比Greiner-Hormann算法简单得多.
3.新算法
新算法分为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的进点
如果C
e 的正向与S
e
的正向的夹角在180o~360o之间(即C
e
从上向下穿过S
e
(如图3(b)
所示)，则由图显然可见，该交点对于多边形S是进点，而对于多边形C则是出点.这就是我们要证明的结论.
对于两个相交多边形的边的取向均为逆时针方向的情况，可用相同的方法证明该引理. □
根据该引理，对其中一个多边形求出一个进点或出点以后，在两个多边形方向相同的情况下，其对另一个多边形的进出性也就确定了.这样，如果两个多边形的方向相同，则在求出交点时只需判断和标记它对其中一个多边形是进点还是出点.它对另一个多边形的进出性则相反.而由第1节的讨论可知，由于沿着一个多边形的边界，在其上的进点和出点是交替出现的.所以只需标记第1个交点是进点还是出点，其他交点的进出性则可依次确定.最终我们得出一个结论：如果两个多边形的方向相同，则要标记所有交点对于两个多边形的进出性，只需标记任何一个多边形链表中的第1个交点的进出性即可(在后面的算法描述中，我们用变量Sin来标记实体多边形链表中的第1个交点对于裁剪多边形是否为进点).因此，新算法的
第1步就要是判断两个多边形是否同向.如果不同向，则将裁剪多边形链表反向，使两个多边形的方向相同.
判断两个多边形是否同向，是通过判断一个交点(如第1个交点)对于两个多边
形的进出性来完成的.如果该点对于实体多边形的进出性与对于裁剪多边形的进出性不同，则可知两个多边形取向相同；否则，两个多边形的取向相反.
新算法将交点的计算与进出性判断合成一步进行.当一个多边形的一个边对另一个多边形进行直线裁剪操作之后，如果有交点，即可根据交点在这个边上的排序的奇偶性来确定交点对另一个多边形的进出性.这样在计算交点的同时也确定了该交点的进出性.详细的描述见第4节.
下面是算法的第1部分的形式描述，其中指针变量PS和PC分别指向实体多边形链表和裁剪多边形链表中正在被处理的当前结点.另外，我们把由结点PS↑和其下一个结点PS↑.next↑定义的边简称为由PS指向的边.
PS=HeadS;
Repeat
以PS指向的边与裁剪多边形进行直线裁剪操作(即求交点的操作，见第4节);
if (上述直线裁剪操作有交点) then
{如图2所示，将每个交点(可能有多个)按其在该边上的顺序插入到实体多边形链表和裁剪多边形链表的对应相交边的两个结点之间;
由Sin标记插入到实体多边形链表中的第1个交点对于裁剪多边形的进出性,Sin=1表示进;
令PF指向第1个交点结点，以备算法的第3阶段使用;
将PC指向该交点在裁剪多边形上的对应边;
以PC指向的边与实体多边形进行直线裁剪操作;
求出上述第1个交点对于实体多边形的进出性;
if上述第1个交点对于实体多边形和裁剪多边形的进出性相同 then 逆转裁剪多边形的链表;
令PS指向实体多边形的下一个边;
转到算法的第2阶段;
}
令PS指向实体多边形的下一个边;
until PS=HeadS;
两个多边形无交点，算法结束;
在第2阶段，算法从第1阶段求出交点的那个实体多边形边的下一个边开始，用每一个实体多边形边与裁剪多边形求交点，并如图2所示，给每个交点建立一个包含该交点坐标的新的交点结点，然后将其插入到实体多边形链表和裁剪多边形链表的对应相交边的两个结点之间.例如，一个交点是由结点PS↑和其下一个结点PS↑.next↑所定义的实体多边形的边与由结点PC↑和其下一个结点PC↑.next↑所定义的裁剪多边形的边相交形成的，那么该交点结点就应该被插入到实体多边形链表的结点PS↑和其下一个结点PS↑.next↑之间，同时被插入到裁剪多边形链表的结点PC↑和其下一个结点PC↑.next↑之间.当一个边上有多个交点时，则以该边的方向为序将这些交点插入其中.例如，如果该边的方向是从左向右的斜线，则可按交点的x坐标的大小顺序插入这些交点.
在这个阶段，算法不需要标记交点的进出性，因为如前所述，算法只需在第1阶段用变量Sin来标记实体多边形链表中的第1个交点对于裁剪多边形的进出性，其余交点对于两个多边形的进出性便由如前所述的规律可知.下面是算法的第2部分的形式描述.
Repeat