一、多边形裁剪概念

对多边形的裁剪不等于把多边形的每一条边进行裁剪。因为多边形通常认为是封闭的，裁剪后的多边形应仍然封闭。（否则为不连贯的折线或者错误的图形）

 对一个多边形的裁剪结果仍是多边形，裁剪后多边形的边界可能包含原来的边以及窗口的边框。

关键：  不仅保留窗口内多边形的边界部分，而且要将窗口边框的有关部分按次序插入到多边形的保留边界中，使之封闭。

多边形的裁剪算法主要要解决两种情况：

（1）一个封闭的多边形被裁剪后通常变得不再封闭，需要确定用窗口边界的适当部分来封闭它。

（2）一个凹多边形被裁剪后可能形成几个小多边形，要正确封闭它们。

二、多边形裁剪算法 -- Sutherland-Hodgman逐边裁剪算法

萨瑟兰德(I．E．SutheSutherland-Hodgmanrland)和霍德曼(Hodgman)在1974年提出的；

算法采用了分割处理、逐边裁剪的方法；

算法思想：将多边形边界作为一个整体，每次用窗口的一条边界对要裁剪的多边形进行裁剪

1）每次用窗口的一条边界(包括延长线)对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧的顶点（可见区域的点），删除外侧的顶点（不可见区域的点），同时，适时地插入新的顶点：即交点和窗口顶点，从而得到一个新的多边形顶点序列。

2）然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又得到一个更新的多边形顶点序列。

3）依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形。

三、 Sutherland-Hodgman逐边裁剪算法规则

1. Sutherland-Hodgman算法中，多边形的新顶点产生规则：

在用窗口一条边界及其延长线裁剪一个多边形时，该边界线把平面分成两个部分：一部分称为边界内侧—可见区域；另一部分称为边界外侧—不可见区域。

2. 多边形新顶点生成规则示例：

四、 Sutherland-Hodgman逐边裁剪算法的实现

裁剪示例：