本实现主要参考了发表于2003年《软件学报》的《一个有效的多边形裁剪算法》(刘勇奎,高云,黄有群)这篇论文，所使用的理论与算法大都基于本文，对论文中部分阐述进行了详细解释，并提取了论文中一些重要的理论加以汇总。另外对于论文描述无法处理的一些情况也进行了试探性的分析。

多边形裁剪用于裁剪掉被裁剪多边形(又称为实体多边形，后文用S表示)位于窗口(又称为裁剪多边形，后文用C表示)之外的部分。裁剪的结果多边形是由实体多边形位于裁剪多边形内的边界和裁剪多边形位于实体多边形内的边界组成的。见下图

图1

后文将以这个图来描述裁剪过程，这个图形比原论文给出的图形更具代表性，最主要就在于C1这一点，论文中的图形，切割多边形没有在实体多边形中的点。所以，第一次看的人往往容易误以为切割多边形与交点组成的列表没有作用。

如图中所示，切割多边形与实体多边形分别为C1C2C3C4和S1S2S3S4S5(由于两个多边形需要同向，需要逆置切割多边形为C1C4C3C2，这个逆置也是有条件的，需要第一个交点保持不变，具体可以见代码实现)，我们要得到的结果是C1-I6->I3-I4->I5(-C1)和S4->I1-I2(->S4)这两个结果多边形（其中用"-"表示切割多边形在实体多边形中的边，用"->"表示实体多边形在切割多边形中的边）

算法的实现分为三个阶段：

阶段1：计算第一个交点，并由第一个交点两多边形相互的进出性判断两个多边形是否同向，如果不同向，将切割多边形反向来使两个多边形方向一致。

阶段2：依次使用实体多边形每条边去切割裁剪多边形并将交点以正确的顺序分别插入到两个多边形的链表中。

阶段3：遍历交点列表，获得最终的结果。

后文将按照这3步来介绍相关的实现要点和代码中主要方法。最后在文章末尾还提到一些特殊情况的处理。

阶段1

阶段1要判断2个多边形是否同向（同向的重要性在后文有描述），其中很重要的一点就是求切割的交点，当然求交点在第二阶段也是很重要的，这里介绍了求交点第二阶段就不再介绍了。

（注：判断多边形是顺时针还是逆时针的方法有很多，本文的C#代码将采用原论文中的方法）

原论文中描述的方法基于一个定理：

定理1：如果两个相交多边形的边的取向相同(均为顺时针或逆时针方向)，则对一个多边形是进点的交点对另一个多边形必是出点。

如果两个多边形的方向相同，对其中一个多边形求出一个进点或出点以后，另一个多边形的进出性也就确定了。这样，求出交点时只需标记其中一个多边形对另一个多边形的进出性即可。从另一个多边形角度看的进出性相反。

判断两个多边形是否同向，需要判断交点的进出性。同一个交点对于两个多边形的进出性不同，则两个多边形是同向；否则，两个多边形方向相反。

交点进出性的判定（排除切线与多边形在顶点处相交或与多边形一条边重合的情况。）

当一条直线切割多边形时，与多边形相交的第一个点是必是进点，第二个点必是出点，如此进点与出点循环出现。

当一个多边形的边切割另一个多边形时，多边形上所有交点的进出性也是交替出现。

通过上面的分析可知，整个实现过程中一个十分关键的操作就是求线段（阶段1中是求直线与多边形交点）与多边形的交点（即用线切割多边形）。并在这个过程中判断交点对于被切割多边形的进出性。

求交点

这里介绍一下原论文中给出的名为错切变化法的求交点方法。这种方法基于两直线进行错切变换后交点的x值不变来实现，通过把切线变为斜率为0的直线来使求交点的过程简化。假设切割线段为(x1,y1)、(x2,y2)，被切割多边形由v1, v2 … vn构成。求交点过程可以描述如下：

1. 求斜率d，d是切线的斜率，将(x1,y1)、(x2,y2)按照这个斜率进行变化后可以得到一条水平直线，我们设这条水平直线为y=yc，则有如下方程组：

带入可得，有

说明，原论文说这里需要x1<x2（看代码实现可知x1=x2 x1>x2都是特殊处理的）。x1≠x2和y1≠y2也是需要满足的，当x1=x2时表示切线是垂直线，应在垂直方向进行切割，先求交点的坐标y。如果y1=y2则不用错切过程，直接用切线切割即可。保证x1<x2是为了保证交点插入实体多边形的顺序正确。

下图是一个例子，黑色的线是错切前的线，绿色的线是错切后的线，实线是切线，虚线是多边形上一条被切割的线：

图2

2. 将多边形上每个点vi(xi, yi)的y坐标按公式进行错切变化得到yi‘：

3. 对错切后多边形的每条边（(xi,yi‘),(xi+1,yi+1‘)）与切线求交点的x坐标Ixj：

如，对于前面图中的例子，带入xi, xi+1可得Ix=6.8。

接着，通过反错切就可以得到Iy，公式：

所以

经计算，Iy=4.6。最终坐标系图像：

图3