计算机图形学二维图形的裁剪

所示，对于其中任一边界向量，从向量起点A向终点B看过去： 如果被测试点P在该边界线右边(即内侧)，AB×AP的方向与X-Y平面
垂直并指向屏幕里面，即右手坐标系中Z轴的负方向。 反过来，如果P在该边界线的左边(即外侧)，这时AB×AP的方向与X-
Y平面垂直并指向屏幕外面，即右手坐标系中Z轴的正方向。 设：点P(x，y)、点A(xA，yA)、点B(xB，yB)， 向量AB={(xB-xA)，(yB-yA)}， 向量AP={(x-xA)，(y-yA)}， 那么AB×AP的方向可由下式的符号来确定：
依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边 形顶点序列即为所求的裁剪好了的多边形。如下图所示。
7.3.1 Sutherland-Hodgeman多边形裁剪
新的多边形顶点序列产生规则： 在用窗口一条边界及其延长线裁剪一个多边形时，该边界线把平面分
成两个部分：一部分称为边界内侧；另一部分称为边界外侧。 如下图所示,依序考虑多边形的各条边。假设当前处理的多边形的边为
V=(xB-xA)·(y-yA)-(x-xA)·(yB-yA)
(3-14)
因此，当V≤0时，P在边界线内侧； 而V>0时，P在边界线外侧。
练习
Sutherland-Hodgeman多边形裁剪中，常用向量叉积法来测试当前点P是 否在边界内侧。已知窗口边界A(30,100)、B(40,180)，某点P(50, 300),请 问点P在边界内侧吗？
7.3 多边形的裁剪
多边形裁剪的常用算法 1．Sutherland-Hodgeman多边形裁剪 2．Weiler－Atherton任意多边形裁剪
7.3.1 Sutherland-Hodgeman多边形裁剪
Sutherland-Hodgman算法也叫逐边裁剪法，该算法是萨瑟兰德 (I．E．Sutherland)和霍德曼(Hodgman)在1974年提出的。这种算法采用了 分割处理、逐边裁剪的方法。 一、Sutherland-Hodgeman多边形裁剪算法思想：
主多边形A和裁剪多边形B的边界将整个二维平面分成了四 个区域：
1、A∩B（交：属于A且属于B）； 2、A－B（差：属于A不属于B）； 3、B－A（差：属于B不属于A）； 4、A∪B(并：属于A或属于B，取反；即：不属于A且 不属于B)。 内裁剪即通常意义上的裁剪，取图元位于窗口之内的 部分，结果为A∩B。 外裁剪取图元位于窗口之外的部分，结果为A－B。 观察右图不难发现裁剪结果区域的边界由被裁剪多边形的 部分边界和裁剪窗口的部分边界两部分构成，并且在交点 处边界发生交替，即由被裁剪多边形的边界转至裁剪窗口 的边界，或者反之。由于多边形构成一个封闭的区域，所 以，如果被裁剪多边形和裁剪窗口有交点，则交点成对出 现。这些交点分成两类： 一类称“入”点，即被裁剪多边形由此点进入裁剪窗口， 如图中a、c、e； 一类称“出”点，即被裁剪多边形由此点离开裁剪窗口， 如图中b、d、f。
每次用窗口的一条边界(包括延长线)对要裁剪的多边形进行裁剪，裁剪 时，顺序地测试多边形各顶点，保留边界内侧的顶点，删除外侧的顶点， 同时，适时地插入新的顶点：即交点和窗口顶点，从而得到一个新的多边 形顶点序列。
然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又 得到一个更新的多边形顶点序列。
7.3.1 Sutherland-Hodgeman多边形裁剪 二、Sutherland-Hodgeman多边形裁剪算法实现：
7.3.1 Sutherland-Hodgeman多边形裁剪
三、Sutherland-Hodgeman多边形裁剪算法演示： 四、点在边界内侧的判断方法：
为了判断pi点是否在边界内侧可用坐标比较法和更通用的向量叉积符号 判别法。
计算 V = (xB－xA）·(y－yA)－(x－xA)）·(yB－yA) =(40－30)·(300－100)－(50－30)）·(180－100) =400
因为V > 0时，所以P在边界外侧。
作业 Sutherland-Hodgeman多边形裁剪中，常用向量叉积法来测试当前点P是 否在边界内侧。已知窗口边界A(50,80)、B(75,130)，某点P(60, 150),请问 点P在边界内侧吗？
7.3.2 Weiler－Atherton任意多边形裁剪 Sutherland－Hodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但 一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。WeilerAtherton多边形裁剪算法正是满足这种要求的算法。 一、Weiler－Atherton任意多边形裁剪算法描述：
1、坐标比较法 将点的某个方向分量与边界进行比较。 例如，判断某点是否在下边界内侧,用条件判别式： if(p[i][1]>=ymin) 即 可。 对其它边界也一样。但不能写成通用公式。
7.3.1 Sutherland-Hodgeman多边形裁剪
2、向量叉积法 为简单计，测试点表示为P点。假设窗口边界方向为顺时针，如图中
在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的 （内角大于180o）、甚至是带有内环的（子区），见下图。
裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称： 1、被裁剪多边形为主多边形，记为A； 2、裁剪窗口为裁剪多边形，记为B。
7.3.2 Weiler－Atherton任意多边形裁剪
7.3.1 Sutherland-Hodgeman多边形形裁剪算法特点： Sutherland－Hodgeman多边形裁剪算法具有一般性，被裁剪多边形可
以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是任意凸多边 形。
上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的 每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次 裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。
SP(箭头表示顺序关系，S为前一点，P为当前点)，边SP与裁剪线的位置关 系只有下面四种情况：
1、S在外侧，P在内侧。则交点Q、当前点P保存到新多边形中。 2、S、P均在内侧，则当前点P保存到新多边形中。 3、S在内侧，P在外侧。则交点Q保存到新多边形中。 4、S、P均在外侧。则没有点被保存到新多边形中。