矩形裁剪多边形算法

多边形是由若干线段围成的封闭图形，使用长方形裁剪多边形得到的结果应该仍然是一个多边形，一个封闭的图形

之前我们学习了Liang-Barsky直线裁剪算法，但是如果仅重复的利用直线段的裁剪方法进行裁剪，很可能无法得到期望的图形结果，无法得到一个封闭的多边形

采用逐边裁剪算法:
依次使用窗口的四条边框直线对多边形进行分布裁剪，先用一条边框直线对整个多边形进行裁剪，得到一个或者若干个新的多边形，再用第二条边框直线对新产生的多边形进行裁剪…依次类推知道四条边框直线都裁剪完，整个多边形的裁剪过程结束

步骤：

• 把待裁剪多边形的各个顶点按照一定的方向有次序的组成有序的顶点序列（p1,p2,pn），相继连接相邻两个顶点（p1p2,p2p3,p3p4,pnp1)即为组成多边形的n条边。该顶点序列就是待处理的输入量
• 对输入的顶点序列进行处理，结果是产生一组新的顶点序列，然后输出该组新的顶点序列，该新的顶点序列表示了由M条边组成的新的多边形
• 把输入的顶点序列作为新的输入量，再次输入进行处理，这样处理三次

如何处理：

• 对于给定的顶点序列，依次检验顶点序列中每个顶点pi (i=1,2,n) ，处于裁剪边框可见侧的顶点被放入新的顶点序列中，处于裁剪边框不可见侧的顶点被删除
• 还要检测pi和他的前一个顶点pi-1点是否处于裁剪边框的同侧（认为p1的前一个顶点是pn），如果不再同一侧的话，要求出裁剪边框与直线段pipi-1的交点并把该交点作为新的顶点列入到新顶点序列中输出
• 我们设多边形的任意一条边起点为s，终点为e。给定的矩形有可见侧和不可见侧
  
• 则线段SE和裁剪线有四种位置关系： 端点SE都在不可见侧，则没有输出；SE都在可见侧，输出端点E；端点S在可见侧，端点E在不可见侧，则输出线段SE与裁剪线的交点C；端点S在不可见侧，端点E在可见侧，则输出线段SE与裁剪线的交点C和端点E