——基于编码技术的直线和多边形的裁剪
课本中的算法5.3-1描述了【求取一条线段与一个图形的公共部分的算法】，该算法通过求取直线段与多边形的所有交点，然后对交点进行排序，来确定交点的奇偶性，然后再根据交点的奇偶性，方便地求出直线段与多边形的公共部分。当然，其中包含了交点特征值，以及对于重交点的处理。
该算法思路清晰，判断准确，是一个好的算法。但是，该算法在实际实行上却有不少的问题。首先，该算法要求多边形的方向是正向，既逆时针，只有这样才能够正确处理特征值的问题，然而，我们要做的工作是实现一个可交互式的图形裁剪试验程序，不可能要求用户只按照逆时针的顺序来输入多边形。其次，该算法的第一个步骤求交点，使用的是参数法，这个方法求出的点可能在直线段上，其延长线上，多边形的边上，边的延长线上。其中在多边形的边的延长线上交点是完全没有必要求取的。而对于一个普通的多边形来说，这样的点恰恰很多。所以，对于这个部分，该算法的效率也还有很大的提升空间。
改进这两个问题就要做到：
l 对多边形的方向没有要求；
l 大幅提高求交点的效率，避免不必要的运算；
参考了相关领域的研究成果，我决定实现陆国栋等[1]提出的算法。该算法使用了和Cohen-Sutherland算法相同的思路，都是通过编码，巧妙的排除无关的线段。大大减少了求交点的运算次数，也因此，很大程度上提高了效率。
下面，我对该算法进行简要的一个描述。
该算法第一个亮点在于，其编码对象为多边形的顶点，即，不是对裁剪对象进行编码，而是对裁剪窗口进行编码，这点与Cohen-Sutherland不同，但是却是异曲同工之妙。
我们知道，平面上的直线都可以表示成 的形式。利用这个方程，我们将平面上的点集分成三个子集：
(1) 对这个集合，我们称为负集，记为G-；
(2) 对这个集合，我们称为零集，记为G0；
(3) 对这个集合，我们称为正集，记为G+；
显然，对于直线 ，如果线段AB和直线有一个交点（非A或B），当且仅当AB分别落在正集和负集。算法利用这个原理，对于多边形的每个顶点进行分类，也即编码。实现了完全避免求取那些落在多边形边的延长线上的交点。
这个想法是不错，但是要对顶点进行分类，免不了要把多边形的顶点带入到直线方程中去计算，而且还是复杂的乘法运算，这样下来，也节省不了多少。
本算法的第二个亮点就是，利用“简单直线”放大零集，简化运算，快速编码。
为了进一步提高效率，该算法采用放大零集的做法。在平面上，坐标轴和|k|=1的四根直线，把平面分成了8个区域，将其中那个直线段所在的区域作为拟似的零集，可以对零集以外的点进行快速判断。如下图：
A
B
G 0’
G-
G+
直线段AB所在的直线的k满足 ，对于使得yi<xi成立的点(xi,yi)来说，肯定可以使yi<kxi+b成立，即在y=x直线右侧的点，肯定输入直线AB的负集；而对于使xi<0成立的(xi,yi)来说，则一定可以使yi>kxi+b成立，即点肯定属于正集。而其判断都仅需一次比较就可以完成，非常的高效。
最后只有那些在y轴和y=x中间区域的多边形顶点，才需要带入到直线的方程中去判断，这些点到底真正落在那个集合。
编码时候，可以令正集的点编码为f=1，负集的为f=-1，零集的为f=0。在求交点的时候，如果多边形的边的两个端点的fi*fi+1<0，则肯定有交点，开始求交点，如果fi*fi+1>0，则肯定没有交点，不用求，如果fi*fi+1=0，则说明是情况比较特殊，有至少一个顶点在直线上，这时候应该专门处理，但是实际情况中，进入这个分支的时候很少。
不失一般性，在具体实现的时候，不会正好是坐标轴和y=x，y=-x四条直线分割平面，我们会重新选择一个特定的“原点”，以确保最大程度的区分多边形的顶点，减少计算。在实际处理的时候，选用的是多边形的外接矩形的边界上的点。
详细的描述，可以参考文献[1]。
算法流程图如下：
struct poly_vertex
{
int x;
int y;
int f; //code
};
struct CodecPoly
{
CTypedPtrList<CPtrList,poly_vertex*> poly;
};
上述为算法实现时主要采用的数据结构，poly_vertex是多边形的顶点的一个结构，其中f用来表示其相对于直线的编码值，CodecPoly是一个编码了的多边形，poly是一个poly_vertex指针组成的类型安全的链表。
算法的实现要对多边形窗口进行两次遍历，第一次对每个顶点进行编码，第二次，求出所有的交点。交点求取结束后，对交点进行排序，根据第一个有效的交点（即不在线段的延长线上）的序数的奇偶性，可以确定此点的出入性，交点的出入性是交替出现的，所以对后序的点不用作判断，遍历交点的链表，每遇到一个入点，就以此点为始点，其后紧接着的出点为终点创建一条线段，加入当前的线段集合。如果线段起点在多边形内，则以起点为第一个入点，如果最后一个交点是入点，则以被裁剪线段的终点为出点。最后删去原被裁剪线段，则完成了裁剪。
这里值得补充的是对上文中提到的fi*fi+1=0时候的处理，也即对奇异情况的处理。对于此种情况，可以增加一个顶点Vi-1来帮助判断。如果fi-1*fi+1=1，说明Vi在直线上，而Vi-1和Vi+1位于直线的同侧，此时的Vi不能改变直线的出入性，所以直接舍去；如果fi-1*fi+1=-1，说明Vi-1和Vi+1位于直线的异侧，改变了直线的出入性，Vi直接加入交点链表；如果fi-1*fi+1=0，情况比较复杂，如果fi =0，说明，ViVi+1这条边与直线重合，则如果这条边时多边形的凸边，则应该保留Vi进入交点链表，如果是凹边，则应该舍去；如果fi≠0，说明Vi-1或者Vi+1在直线上，这两种情况可以不处理，为什么呢？因为Vi-1在上一个循环中是Vi，而Vi+1在下一个循环中处于Vi的地位，不用重复处理。
该算法适应性良好，多余非常复杂的情况也有良好的适应性。如图：
而且裁减的速度很快，对于直线非常多的情况也完全没有问题。如图：
对于许多不同方向上的直线的同时裁剪的效果图。可见该算法对于各种方向的直线都有很好的适应性，正确性。
多边行的矩形裁剪，课本上介绍了Sutherland-Hodgman的算法，我觉得对于矩形裁剪来说，这应该算得上最简单的算法了。但是，这个算法的性能并不差。这又验证了，简单的就是优美的，高效的那么一个道理。
Suterland-Hodgman算法用矩形窗口的边界做刀，分别对多边形进行裁剪，每裁剪一次，进行一次封口操作，这样，一共四次，就可以完成对于多边形的裁剪。
其裁剪过程如图所示：
有感于直线的多边形线裁剪算法，我在Sutherland-Hodgman算法中加入了编码的成分。以提高对交点有无的判断，进而减少求交次数。
具体编码方案，采用了Cohen-Sutherland的编码方案，这个编码方案在直线的矩形窗口裁剪中本来是有缺陷的，即它不能快速排除跨越三个区域的直线。然而，这个编码方案用在这里却是正正好好，恰到好处，因为这种裁剪方案，每次使用一条边裁剪，仅需对分布在两个区域的线段作判定，使这种编码方案显示了充分的威力。
在具体实现的时候，我是这么做的：
首先，基于矩形窗口对多边形进行编码；
然后，依次裁剪，裁剪的时候，根据编码，可以快速排除，如果一条边位于窗口的一个边界的同侧，则不予处理。对于，分布在边界两侧的边，求出其交点，并且加入到多边形中。
对于封口操作，我这里也想出了一个新的办法，可以在裁剪的同时，就完成封口操作。不用额外地使用一个函数。
下面，我提一下我的设计思路：
我在这里用编码值标记顶点的有效性。刚才不是提到了使用Cohen-Sutherland算法中的编码方案吗，根据这个编码，我可以对一些明显不在裁剪范围内的点进行舍去。这个判断的条件其实是相当简单的，取出该顶点关于某条边的编码的位，如果为0，有效，为1则无效。
比如上面图中，白色和黄色三角形的顶点，对于上边界可以直接舍去，蓝色和黄色三角形标记的顶点对于右边界可以舍去。有了无效的判断方法，在进行边裁剪的时候，就可以轻易完成封口操作，在裁剪中，首先准备一个结果链表，用来存储一条边裁剪过后的结果多边形。
然后从多边形首节点开始遍历，取出多边形首节点和次节点编码中针对这条边的码值，比如对于上图中，针对上边界，只要把每个顶点的编码值与8作位与，就可以取得了。这个取出的码值如果为零，说明这个顶点在结果链表中，如果两个连续顶点，一个码值为零，另一个不为零，所名跟当前切割边必有交点，求出交点，求出交点的编码，然后把交点加入到多边形链表中，指针后移一个，继续遍历多边形。真正巧妙的在于，由于刚才把无效的顶点直接舍去了，求出的结果多边形正好是已经正确封口的多边形，不需要额外的封口操作了。
下面给出算法的流程图：
对所有顶点编码
是否全在内部
进行四次线裁剪
取出当前节点及其下一个节点
取出两个顶点关于当前边的编码
当前节点码值为零
加入结果链表
当前节点与下一个节点码值不等
开始
求交点，求交点的编码（其实是全零），将交点加入到结果链表，指针后移一个。
结束
N
Y
4次
Y
N
N
Y
struct vertex{
int x,y;
int code1;
bool valid;
……
vertex(const vertex& v)
{
x = v.x;
y = v.y;
code1 = v.code1;
code2 = v.code2;
valid = v.valid;
};
vertex(int x, int y)
:code1(0),code2(0),valid(false)
{
this->x = x;
this->y = y;
};
vertex& operator=(const vertex& v)
{
if (this == &v) return *this;
x = v.x;
y = v.y;
code1 = v.code1;
code2 = v.code2;
valid = v.valid;
};
bool operator<(const vertex& v)
{
if (x < v.x) return true;
if (x == v.x && y < v.y) return true;
return false;
};
};
//多边形数据结构
struct polygon{
list<vertex> V;
};
顶点使用了自己定义的一个结构，code1用来存放编码的值，多边形使用了和STL结合的办法，用了一个标准的list，主要是看中它操作方便的特性。
当然，正如大家所知道的。Sutherland-Hodgman算法有着很大的局限性，即其只能对凸多边形进行正确的裁剪，而对于凹多边形，在有些情况下会出现无法消去的退化边界，在课本里成为蜿蜒的现象。另一个局限就是不能分块输出。
对于书上一个经典的例子，就变成下面这种局面：
其实，还有其它的情况，比如下面的样子：
这也是退化边，而且，这种类型的退化边根据裁剪顺序的不同，而有所不同。如上图，裁剪顺序为，左，上，右，下。如果换成左，右，上，下，又会有所不同了。
虽然，Sutherland-Hodgman算法有很大的局限性，但是做为仅仅需要进行凸多边形裁剪的场景的应用，该算法，还是有相当的优势的。
不过，如果非要实现去除退化边界，结果分块输出的效果，应该怎么做呢？那就只有使用二维布尔运算的办法了。下面，我也会介绍。
任意多边形的裁剪，更加具有一般性，与矩形裁剪不同，对被裁剪的多边形形，和裁剪使用的窗口都没有明确的规定，可以是凹多边形，甚至是带有内环的多边形。
对于这样的多边形，常常采用的就是二维布尔运算的方法。这种方法，主要优点是通过定义相互的出点和入点，然后可以方便地进行各种布尔运算。对于多边形的裁剪来说，也是其中的一个方面。
在任意多边形的裁剪算法中，我就是使用二维布尔运算的原理。
这个原理在书上有叙述，我就不再赘述了，简单说就是先求交点，然后确定交点是入点还是出点。接下去按照书上的描述，进行处理，就可以实现裁剪了。
我这里主要是提几个关键性的问题。
书上提到的二维布尔求交是基于几个假设的，首先多边形是有方向的，书上假设的是多边形都是逆时针方向的。在这种假设下，多边形的入点和出点才有意义。这也就意味着，如果想按照算法来解决问题，第一步就是要使两个多边形处于正方向。
对于这一点，交互式地输入多边形，肯定是不能满足条件的，因为你不能规定用户按照哪个方向来输入多边形。
我是这么解决的，我发现，对于两个多边形来说，如果两个多边形的方向是一致的，那么对于一方来说的入点对于另外一方来说就是出点，而且对于同一个多边形来说，沿着这个多边形的方向，入点和出点是交替分布的。这其实降低了要求，不要求两个多边形的方向一定是正方向，而是只要求，两个多边形的方向相同。
那么如何判定两个输入多边形的方向是否相同呢？
这个就是我这个算法里面比较有新意的地方。我们知道，如果一个多边形是有方向的，其实是说，多边形的边是顺次相连的有向线段。对于一个顶点来说，是一条有向线段的起点，是另一条有向线段的终点。对于这两条线段，我们可以求取它的叉积。这个叉积其实业是一个向量，我发现在于同一个多边形中，凸顶点的叉积都是相同方向的，而凹定点的叉积也是相同方向的，而且是凸顶点的反方向，如果将一个多边形的方向逆转，就会发现这两种方向都发生反转。有了这种特性，我就可以很方便的判定两个多边形的方向是否一致了，只要在两个多边形中各找到一个凸顶点，然后计算叉积，如果符号相同，就说明两个多边形的方向一致，否则，只要任意逆转其中一个多边形就可以了。
下面，我再用一个图示来说明：
+1
+1
+1
+1
-1
-1
-1
-1
-1
+1
对于上面这张图来说，两个多边形的方向如图所示，对于每个顶点，求<进入这个顶点的向量，离开这个顶点的向量>这个有序对的叉积，如果值大于0，则标注+1，小于0则标注-1，我们看到，方向不同的两个多边形的正负情况刚好相反。所以在实际中，我们可以利用这个特性，来判断两个多边形的方向。
首先求出两个多边形的最左（右，上，下）边的点，这个点一定是凸顶点，对这个点求叉积，如果两个多边形的符号相同，就是同向，进入下一个阶段，如果两个多边形的符号不同，就是反向，这时候，只要逆转其中之一就可以了。
下面，我还是给出整个算法的流程图：
取得多边形
取得实体多边形的最左点，求得叉积，负值给sign1
取得裁剪多边形的最左点，求得叉积，负值给sign2
sign1 * sign2 > 0
逆转裁剪多边形
求裁剪多边形与实体多边形的第一个交点，通过包容性测试判断其出入性，用P指针标记此点
求出两个多边形的所有的交点，然后插入到两个多边形的链表中。
P指向的交点是实体多边形相对于裁剪多边形的入点
沿着实体多边形移动到下一个交点，F指向P
新建一个结果多边形链表的节点
把F加入结果链表第一个多边形。进入到实体多边形，标记该点已处理
遇到交点
将点加入
将点加入，进入裁剪多边形
遇到交点
将点加入
是否是P点
移动F到下一个没有标记过的入点
结束
返回结果链表
N
N
N
N
N
struct vertex {
int x,y;
bool inters, used;
struct vertex *next, *next1, *next2;
};
struct out{
vertex *polygon;
struct out *next;
};
如上，就是这个算法中使用的数据结构，vertex是一个节点数据结构，我们可以看到，这里面有三个指针域，next是多边形单链表用的。next1表示如果是交点，被插入了实体多边形，使用这个指针，同时这个节点也会被插入到裁剪多边形，使用next2指针。所以实际中最多会用到两个。
实体多边形和裁剪多边形都是用单链表的结构存储，vertex也可以表到交点，用inters这个bool型来说明是否是交点，used这个bool在输出的时候用来标记节点是否已经处理。
out是使一个输出链表，它是一个顶点链表的链表，也即是一个多边形的链表，用来存储分块输出的多边形。
对于数据结构的实际使用，我也用图示来说明：
对于如下的两个多边形：
输入后，并且求出所有的交点后是如下图的样子：
这个数据结构的采用，是参考了刘勇奎等[2]的提法，也主要是因为这个结构比较简单，清晰，而且占用了较少的资源。
使用了二维布尔求交后，可以对任意的多边形求取裁剪，稍作修改，也可以求并，补等运算。完全解决了矩形裁剪时候的蜿蜒，其实只要用多边形来表达矩形，就可以实现正确的矩形裁剪，但是为了比较，我还是保留了矩形裁剪。
其最后效果如图：
通过本次图形学的课程设计，我实践图形学中二维图形处理的很重要的一块，裁剪。裁剪的算法是三维图形处理中消隐的基本算法，也是大型图形处理中很重要的一块，对于算法的正确性，效率都有很高的要求。
在这次课程设计中，能够选择这个题目我很高兴。学到了很多的知识。
也曾为了一些技术问题头疼过，但当我真的想出了一个可行的解决方案时，那种欣喜，是无法用语言表达的。
不管怎么说，我觉得做这个课程设计，我是用了十分的努力的，我也从中获得了极大的满足。这个图形学课程和课程设计，都带给了我很多知识，我在此感 谢何 老师，您是一位很好的老师，教学认真，讲究方法，授人以渔而非授人以鱼，您是一位不可多得的好老师！
感谢辛苦评阅此次课程设计的所有人员， 包括 老师和助教。没有你们，我们也不能顺利完成课程的学习。
感谢蔡舒同学，你和我选择一样的题目，并且毫不吝啬地和我分享你的经验，和我一起讨论技术问题，使我获得了许多的启发，你的努力认真也使我受到了激励！
[1] 陆国栋，邢世海，彭群生 基于顶点编码的多边形线裁剪高效算法 计算机学报 2002.9
[2] 刘勇奎，高 云，黄有群 一个有效的多边形裁剪算法 软件学报 2003
本实验报告的原文及C++代码实现的源文件，请按这里下载！仅供参考！
