地图开窗算法设计

实验四 地图开窗算法设计 （09214704）

重点：掌握二维图形点、线段、多边形和字符的裁剪算法。

难点：理解二维裁剪算法思想并且用C语言进行算法的实现。

课时安排：授课4学时（线段裁剪：2学时；多边形裁剪：2学时）；

上机4学时（多边形裁剪）。

一、裁剪的意义

为了描述图形对象，我们必须存储它的全部信息，但有时为了达到分区描述或重点描述某一部分的目的，往往将要描述的部分置于一个窗口内，而将窗口外的部分“剪掉”，这个处理过程叫做裁剪，裁剪在计算机图形处理中具有十分重要的意义。

裁剪实质上是从数据集合中抽取信息的过程，这个过程是通过一定的计算方法来实现。

裁剪就是将指定窗口作为图形边界，将窗口内的图形保留，而窗口外的图形则被舍弃。

二、裁剪的目的

裁剪的基本目的是判断某个图形元素是否落在窗口之内，如落在窗口之内则进一步求出位于窗口内的部分。

三、裁剪处理涉及

1、图元在窗口内外的判别；

2、图形元素与窗口的求交。

3.3 多边形的裁剪 前面讨论了线段的裁剪，多边形的裁剪是以线段裁剪为基础的，但又不同于线段的裁剪。通常有一种错觉，认为只要把多边形的每条边用直线裁剪方法裁剪后，就完成了对多边形的裁剪。

其实不然，在计算机图形学中，多边形定义了一个封闭的二维区域，它把平面分成多边形内区和外区，一个多边形的裁剪结果仍应该是封闭的多边形，而不是一些孤立的线段。

如图中所示，裁剪后的多边形仍应保留原多边形各边的连接顺序并加入一些新顶点（交点、窗口顶点）及删除界外顶点；一个凹多边形裁剪后，可能分裂为几个多边形。

多边形裁剪的常用算法

1．Sutherland-Hodgeman多边形裁剪

2．Weiler－Atherton任意多边形裁剪

3.3.1 Sutherland-Hodgeman多边形裁剪

Sutherland-Hodgman算法也叫逐边裁剪法，该算法是萨瑟兰德(I．E．Sutherland)和霍德曼(Hodgman)在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。

一、Sutherland-Hodgeman多边形裁剪算法思想：

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

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

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

新的多边形顶点序列产生规则：

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

如下图所示,依序考虑多边形的各条边。假设当前处理的多边形的边为SP(箭头表示顺序关系，S为前一点，P为当前点)，边SP与裁剪线的位置关系只有下面四种情况：

1、S在外侧，P在内侧。则交点Q、当前点P保存到新多边形中。

2、S、P均在内侧，则当前点P保存到新多边形中。

3、S在内侧，P在外侧。则交点Q保存到新多边形中。

4、S、P均在外侧。则没有点被保存到新多边形中。

二、Sutherland-Hodgeman多边形裁剪算法实现：

1、已知：多边形顶点数组p[ ][2]，顶点个数n，

裁剪边界xmin(假设对左边界进行裁剪)，

定义新多边形顶点数组q[][2]。

2、赋初值：被裁多边形顶点数组的下标变量i=0；

新多边形顶点数组的下标变量j=-1；

前一个点S的x方向分量s[0]=p[n-1][0]；

S的y方向分量s[1]=p[n-1][1]；

前一个点S的内外标志，用变量flag来标识：

0表示在内侧，1表示在外侧。

if(s在边界内侧) /*例如对左边界：s[0]>=xmin*/

flag=0；

else

flag=1；

3、对多边形的n条边进行处理，对当前点号的考虑为：0～n-1。

for(i=0；i

{

if(当前第i个顶点是否在边界内侧？) /*对左边界：p[i][0]>=xmin */

{

if(flag!=0) /*前一个点在外侧吗？*/ {

flag=0；/*从外到内的情况，将标志置0,作为下一次循环的前一点标志*/

j++；

q[j][0]=求出交点的x方向分量； /*将交点q放入新多边形*/

q[j][1]=求出交点的y方向分量；

}

j++；

q[j][0]= p[i][0]； /*将当前点pi放入新多边形*/

q[j][1]= p[i][1]；

}

else

{

if(flag==0) /*前一个点在内侧吗？*/

{

flag=1；/*从内到外的情况，将标志置1,作为下一次循环的前一点标志*/

j++；

q[j][0]=求出交点的x方向分量； /*将交点q放入新多边形*/

q[j][1]=求出交点的y方向分量；

}

}

s[0]=p[i][0]； /*将当前点作为下次循环的前一点*/

s[1]=p[i][1]；

}

四、点在边界内侧的判断方法：

为了判断pi点是否在边界内侧可用坐标比较法和更通用的向量叉积符号判别法。

1、坐标比较法

将点的某个方向分量与边界进行比较。

例如，判断某点是否在下边界内侧,用条件判别式： if(p[i][1]>=ymin) 即可。

对其它边界也一样。但不能写成通用公式。

2、向量叉积法

为简单计，测试点表示为P点。假设窗口边界方向为顺时针，如图中所示，对于其中任一边界向量，从向量起点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的方向可由下式的符号来确定：

V=(xB-xA)·(y-yA)-(x-xA)·(yB-yA) (3-14)

因此，当V≤0时，P在边界线内侧；

而V>0时，P在边界线外侧。

五、Sutherland-Hodgeman多边形裁剪算法特点：

Sutherland－Hodgeman多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。

上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。

一、Weiler－Atherton任意多边形裁剪算法描述：

在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180o）、甚至是带有内环的（子区），见下图。

裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称：

1、被裁剪多边形为主多边形，记为A；

2、裁剪窗口为裁剪多边形，记为B。

主多边形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。

二、Weiler－Atherton任意多边形裁剪算法思想：

假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。当两个多边形相交时，交点必然成对出现，其中一个是从被裁剪多边形进入裁剪窗口的交点，称为“入点”，另一个是从被裁剪多边形离开裁剪窗口的交点，称为“出点”。

算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；

而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。

按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。

由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完毕后算法结束。

三、Weiler－Atherton任意多边形裁剪算法步骤：

1、顺时针输入被裁剪多边形顶点序列Ⅰ放入数组1中。

2、顺时针输入裁剪窗口顶点序列Ⅱ放入数组2中。

3、求出被裁剪多边形和裁剪窗口相交的所有交点，并给每个交点打上“入”、“出”标记。

然后将交点按顺序插入序列Ⅰ得到新的顶点序列Ⅲ，并放入数组3中；

同样也将交点按顺序插入序列Ⅱ得到新的顶点序列Ⅳ，放入数组4中；