📄 2.6.2 多边形的剪裁.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.ekany.com/wdg98/cg/contents/chapter2/les262.htm -->
<HTML><HEAD><TITLE>2</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY><B>
<H3 align=justify><A name=262><FONT face=楷体_GB2312 size=4>2.6.2
多边形的剪裁</FONT></A></B></H3>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>
多边形的剪裁比直线剪裁复杂。如果套用直线剪裁算法对多边形的边作剪裁的话，剪裁后的多边形之边就会成为一组彼此不连贯的折线，从而给填色带来困难（图2.6.3(b)）。多边形剪裁算法的关键在于：通过剪裁，不仅要保持窗口内多边形的边界部分，而且要将窗框的有关部分按一定次序插入多边形之保留边界之间，从而使剪裁后的多边形之边仍旧保持封闭状态，填色算法得以正确实现（图2.6.3(c)）。</FONT></FONT></P>
<P align=center><IMG height=193 src="2.6.2 多边形的剪裁.files/2_6_3.gif" width=421
border=0></P>
<P align=center><FONT face=楷体_GB2312><FONT size=4>图</FONT>2.6.3 <FONT
size=4>多边形剪裁</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>下面介绍的多边形剪裁算法是Sutherland和Hodgman提出的<SUP>[9]</SUP>，它的基本思想是：</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>1）令多边形的顶点按边线逆时针走向排序：p<SUB>1</SUB>, p<SUB>2</SUB>, …,
p<SUB>n</SUB>。如图2.6.4(a)。各边先与上窗边求交。求交后删去多边形在窗之上的部分，并插入上窗边及其延长线的交点之间的部分（图2.6.4(b)中的（3，4）），从而形成一个新的多边形。然后，新的多边形按相同方法与右窗边相剪裁。如此重复，直至与各窗边都相剪裁完毕。图2.6.4(c)、(d)、(e)示出上述操作后所生成的新多边形的情况。</FONT></FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4><IMG height=417
src="2.6.2 多边形的剪裁.files/2_6_4.gif" width=471 border=0></FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4>图2.6.4 多边形剪裁的步骤</FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>2）多边形与每一条窗边相交，生成新的多边形顶点序列的过程，是一个对多边形各顶点依次处理的过程。设当前处理的顶点为p，先前顶点为s，多边形各顶点的处理规则如下：</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>如果s,
p均在窗边之内侧，那么，将p保存。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>如果s在窗边内侧，p在外侧，那么，求出sp边与窗边的交点I，保存I，舍去p。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>如果s,
p均在窗边之外侧，那么，舍去p。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>如果s在窗边之外侧，p在内侧，那么，求出sp边与窗边的交点I，依次保存I和p。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>上述四种情况在图2.6.5(a)、(b)、(c)、(d)中分别示出。基于这四种情况，可以归纳对当前点p的处理方法为：1、p在窗边内侧，则保存p；否则不保存。2、p和s在窗边非同侧，则求交点I，并将I保存，并插入p之前，或s之后。</FONT></FONT></P>
<P align=center><IMG height=290 src="2.6.2 多边形的剪裁.files/2_6_5.gif" width=460
border=0></P>
<P align=center><FONT face=楷体_GB2312><FONT size=4>图</FONT>2.6.5 <FONT
size=4>多边形的新顶点序列的生成规则</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>程序2.6.6执行上述算法思想。它的主程序clip_polygon含有输入参数：</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>x,
y是两个长n的数组，存放多边形顶点坐标；X<SUB>w-max</SUB>，X<SUB>w-min</SUB>，Y<SUB>w-max</SUB>，Y<SUB>w-min</SUB>是窗口的边界。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>输出参数：一个剪裁后的多边形，顶点仍放在x,
y数组之中，长度为修改了的n。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>clip-polygon</FONT>调用二个子程序：</FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>1）clip_single_edge(edge,
type, n_in, y_in, n_out, x_out,
y_out)；功能为将多边形与一条窗边edge相剪裁。其中输入参数为：</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>edge：窗边的值，可以是X<SUB>w-max</SUB>，Y<SUB>w-max</SUB>，X<SUB>w-min</SUB>，Y<SUB>w-min</SUB>四种值之一种；</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>type：窗边的类型，可以是right, left,
top, bottom四种值之一种；</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>x_in, y_in,
n_in：输入多边形顶点坐标及个数。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>输出参数为：x_out, y_out,
n_out，是输出多边形的新顶点序列坐标及个数。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>2）test_intersection(edge,
type, x<SUB>1</SUB>, y<SUB>1</SUB>, x<SUB>2</SUB>, x_out, y_out, yes,
is_in)；功能与参数含义为：</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>（1）判断当前点（x<SUB>2</SUB>,
y<SUB>2</SUB>）是否在所剪裁的窗边edge之内侧，如是，is_in为True；否则，is_in为False。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>（2）判断（x<SUB>2</SUB>,
y<SUB>2</SUB>）与先前点（x<SUB>1</SUB>,
y<SUB>1</SUB>）是否分在edge之异侧，如是，yes为True；否则，yes为False。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>（3）如果yes=True，求出边（x<SUB>1</SUB>y<SUB>2</SUB>）（x<SUB>2</SUB>y<SUB>2</SUB>）与edge之交点坐标，存入x_out,
y_out。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>该程序的输出参数为is_in, yes，和x_out,
y_out。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>clip_polygon (Xwmax, Xwmin, Ywmax,
Ywmin, n, x, y)</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>int Xwmax, Xwmin, Ywmax, Ywmin, n,
*x, *y;</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>{</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>int * x1, *y1, n1;</FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>/* </FONT>定义<FONT
size=4>right=1, bottom=2, left=3, top=4. */</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>clip_single_edge(Xwmax, right, n,
x, y, &n1, &x1, &y1);</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>clip_single_edge(Ywmin, bottom, n1,
x1, y1, &n, &x, &y);</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>clip_single_edge(Xwmin, left, n, x,
y, &n1, &x1, &y1);</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>clip_single_edge(Ywmax, top, n1,
x1, y1, &n, &x, &y);</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>}</FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT size=4>程序2.6.6
多边形剪裁主程序</FONT></FONT></P>
<BLOCKQUOTE>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>clip_single_edge(edge, type, nin, xin, yin, nout, xout,
yout)</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int edge, type, nin, *xin, *yin, *nout, *xout, *yout;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>{</FONT></P>
<BLOCKQUOTE>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int i, k, yes, is_in;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int x, y, x_intersect, y_intersect;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>{</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> x=xin[nin]; y=yin[nin];</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> k=0;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> for(i=0; i<nin; i++){</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
test_intersect(edge, type, x, y, xin[i], yin[i],</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
&x_intersect, &y-intersect, &yes, &is_in);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>/* yes</FONT>表示两点是否在<FONT face=Arial>edge</FONT>之异侧；<FONT
face=Arial>is_in</FONT>表示<FONT face=Arial>xin[i], yin[i]</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> </FONT>是否在<FONT face=Arial>edge</FONT>之内侧<FONT
face=Arial>. */</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> if (yes) {</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
xout[k]=x_intersect;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
yout[k]=y_intersect;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
k++;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
}</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> if(is_in) {</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
xout[k]=xin[i];</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
yout[k]=yin[i];</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
k++;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -