7、二维裁剪li.ppt

《7、二维裁剪li.ppt》由会员分享，可在线阅读，更多相关《7、二维裁剪li.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7讲 二维裁剪l l显示屏幕范围有限，在显示一张大图时，只能显示图形的一个矩形部分。l l用来指定图形显示内容的矩形区域称为裁剪窗口。l l在窗口内的图形被显示，窗口之外的图形被裁剪掉。l l二维裁剪分为直线裁剪，多边形裁剪。直线裁剪l l常见的直线裁剪方法有：l lCohen-Sutherland算法l l中点分割法l l梁友栋-Barsky算法Cohen-Sutherland算法(1)l l平面分成平面分成9 9个区域，各区域用个区域，各区域用4 4位二进制码位二进制码C CT TC CB BC CR RC CL L表示表示00001000010001100010101010010001

2、0101yTyBxLxRl l00000000区域为显示窗口，只有在该区域的直线段才显示。区域为显示窗口，只有在该区域的直线段才显示。编码方法：编码方法：y=y=y=y yB B （窗口上边）窗口上边）C CB B=0=0 否则否则C CB B=1=1 x=x=x=x xL L（窗口右边）窗口右边）C CL L=0=0 否则否则C CL L=1=1Cohen-Sutherland算法(2)l l根据线段端点所在区域，为端点赋予区域码。根据线段端点所在区域，为端点赋予区域码。1.1.端点两码全为端点两码全为00000000，可见，显示，可见，显示2.2.端点两码相端点两码相“与与”，结果不为，结

3、果不为00000000，不可见，不显示，不可见，不显示3.3.端点两码不全为端点两码不全为0 0，相，相“与与”，结果为，结果为00000000，不确定。可，不确定。可能部分可见，继续判断能部分可见，继续判断000010000100011000101010100100010101yTyBxLxRCohen-Sutherland算法(3)l l用编码中，用编码中，1 1所对应的边与直线求交点，将线段分成两段。所对应的边与直线求交点，将线段分成两段。l l为两个新线段端点编码，窗口这边线段的交点，该位编码为两个新线段端点编码，窗口这边线段的交点，该位编码为为0 0，非窗口这边线段的交点，该位编码为

4、，非窗口这边线段的交点，该位编码为1 1l l用上述步骤用上述步骤1 1，2 2，3 3对两个新线段进行判断，直到线段所对两个新线段进行判断，直到线段所有部分都明确可见或不可见为止。有部分都明确可见或不可见为止。000010000100011000101010100100010101yTyBxLxR窗口的两个对角坐标分别为（10，80）、（90，20），试用“Cohen-Sutherland”直线裁剪算法分别对线段(20，30)(40，30)，(5，75)(80，60)，(100，10)(110，15)进行裁剪（要求将裁剪步骤写清楚）。（15分）要点：每一条线段各5分，其中，线段两端点编码正确

5、1分，严格按照裁剪算法步骤进行裁剪4分。中点分割法(1)-近似求解l l用两个端点的坐标与窗口参数用两个端点的坐标与窗口参数x xL L 、x xR R 、y yT T 、y yB B的关的关系判断线段是否完全不可见系判断线段是否完全不可见,(,(类似前节首先编码类似前节首先编码)。p0p1ABl l从从p p0 0出发寻找最近可见点出发寻找最近可见点p pl l若若p p0 0可见，不用找了可见，不用找了p=pp=p0 01.1.若若p p0 0不可见，取中点不可见，取中点p pmm=(p=(p0 0+p+p1 1)/2)/2pmAp1pmp0p0p1中点分割法(2)2.2.p pmm，p

6、p1 1是否太接近？是，是否太接近？是，p=pp=pmm，结束；不是，向下走结束；不是，向下走3.3.p pmmp p0 0是否不可见？是是否不可见？是,p,p0 0=p=pmm ，回到回到1 1；不是；不是,p,p1 1=p=pmm ，回到回到1 1这样线段以一次去一半的速度，很快找到距离这样线段以一次去一半的速度，很快找到距离p p0 0最近的最近的可见点可见点l l从从p p1 1出发寻找最近可见点方法一样出发寻找最近可见点方法一样l l和前一种方法相比，这里只要判断线段是否不可见，也和前一种方法相比，这里只要判断线段是否不可见，也不需要区域编码。不需要区域编码。l l线段满足下列四个条

7、件之一，完全不可见线段满足下列四个条件之一，完全不可见线段两个端点都满足线段两个端点都满足x x x x xR R ;线段两个端点都满足线段两个端点都满足y y y yT T;线段两个端点都满足线段两个端点都满足y y 1t 00 t x0,xL为始边，xR为终边；x1y0,yB为始边，yT为终边；y1=t1，直线不可见。否则计算t0，t1对应的直线点(x0,y0),(x1,y1)，并显示。l l当线段为水平或垂直线时，即y1=y0或x1=x0，先判断y1yTOR y1xROR x1xL(该线段是否不可见)，如果不能确定，就计算交点参数。此时，只要计算一条始边、一条终边。例题：在例题：在“梁友

8、栋梁友栋-BarskyBarsky”直线裁剪算法中用参数直线裁剪算法中用参数方程表示直线。用参数方程表示直线二维平面上的方程表示直线。用参数方程表示直线二维平面上的直线直线(x0,y0)(x1,y1)(x0,y0)(x1,y1)，并解释参数，并解释参数t0,t=0,0tt,t0,t=0,0t1t=1,t1时，直线上的点的变化范围。时，直线上的点的变化范围。(15(15分分)解：设直线段的起点为解：设直线段的起点为(x0,y0)(x0,y0)，终点为，终点为(x1,y1)(x1,y1)（+2+2），），则直线则直线(x0,y0)(x1,y1)(x0,y0)(x1,y1)的参数方程的参数方程x=x

9、0+(x1-x0)tx=x0+(x1-x0)ty=y0+(y1-y0)t y=y0+(y1-y0)t （+5+5）当当t t由由 时，时，t t所对应的直线上的点，所对应的直线上的点，由线段由线段(x0,y0)(x1,y1)(x0,y0)(x1,y1)起点端无穷远处依次经起点端无穷远处依次经过起点、终点向终点端无穷远处运动，其中过起点、终点向终点端无穷远处运动，其中当当t0t0时，点的变化范围在起点端无穷远处与起点时，点的变化范围在起点端无穷远处与起点(x0,y0)(x0,y0)之间；（之间；（+1+1）当当t=0t=0时，时，(x,yx,y)=(x0,y0),)=(x0,y0),对应直线段起

10、点对应直线段起点(x0,y0)(x0,y0)；（；（+2+2）当当0t10t1t1时，点的变化范围在终点时，点的变化范围在终点(x1,y1)(x1,y1)与终点端无与终点端无穷远处之间穷远处之间.（+1+1）要点：必须事先明确起点和终点，不同的规定导致要点：必须事先明确起点和终点，不同的规定导致不同的结果。不同的结果。例题：在例题：在“梁友栋梁友栋-BarskyBarsky”直线裁剪算法中将窗口直线裁剪算法中将窗口四条边分为四条边分为“始边始边”和和“终边终边”两类。如何确定两类。如何确定“始边始边”和和“终边终边”？(15(15分分)解：设窗口的四条边分别用xmin,ymin,xmax,ym

11、ax表示，(+2)直线段的起点为(x0,y0)，终点为(x1,y1)(+2)令x=x1x0,y=y1y0，(+1)当当xx00时，时，x=x=xminxmin为始边，为始边，x=x=xmaxxmax为终边为终边当当xx000时，时，y=y=yminymin为始边，为始边，y=y=ymaxymax为终边为终边当当yy00时，时，y=y=ymaxymax为始边，为始边，y=y=yminymin为终边为终边(+3)(+3)当当x0 x0且且y0y0时，分别有两条始边和终边；当时，分别有两条始边和终边；当xx=0(+2)=0(+2)或或yy=0(+2)=0(+2)时，只有一条始边、一条终边。时，只有一

12、条始边、一条终边。要点：要点：1 1、对各种参数要做说明，未做说明要做相应的、对各种参数要做说明，未做说明要做相应的扣分；扣分；2 2、用确定的参数确定判断原则；、用确定的参数确定判断原则；3 3、对特殊、对特殊情况情况xx=0=0或或yy=0=0要做说明，未做说明或说明错误要要做说明，未做说明或说明错误要做相应的扣分。做相应的扣分。多边形裁剪l l多边形裁剪不同于直线裁剪，多边形表示一个用多边形的边围成的一个区域，裁剪结果仍然是一个区域。部分区域的边界可能由窗口边界代替。l l常见的多边形裁剪有：1.1.窗口（矩形）对任意多边形的裁剪2.2.一个任意多边形对另一个任意多边形的裁剪Suther

13、land-Hodgman算法l l该算法该算法用于矩形窗口对任意多边形的裁剪用于矩形窗口对任意多边形的裁剪l l设矩形窗口参数为设矩形窗口参数为x xL L，x xR R ，y yB B，y yT T ，任意多边形任意多边形顶点表示为顶点表示为P P0 0P P1 1P P2 2P Pn n。l l每个窗口参数都各自将平面划分为内侧空间、外每个窗口参数都各自将平面划分为内侧空间、外侧空间两部分。侧空间两部分。x=xL内侧空间内侧空间外侧空间外侧空间y=yTy=yBx=xR外侧空间外侧空间内侧空间内侧空间内内侧侧空空间间外外侧侧空空间间外外侧侧空空间间内内侧侧空空间间Sutherland-Hod

14、gman算法l l该算法该算法用窗口四条边依次裁剪多边形用窗口四条边依次裁剪多边形。l l裁剪输入参数是一系列顶点，裁剪结果也是一系裁剪输入参数是一系列顶点，裁剪结果也是一系列顶点。列顶点。l l四条边依次处理完后，所得到的一系列顶点就是四条边依次处理完后，所得到的一系列顶点就是裁剪多边形顶点。裁剪多边形顶点。l l某一条边的裁剪过程如下：某一条边的裁剪过程如下：1.1.将多边形所有顶点依次输入到输入数组将多边形所有顶点依次输入到输入数组P,P,相邻相邻的两个顶点是多边形的一条边。注意：起点的两个顶点是多边形的一条边。注意：起点P P0 0也也作为最后一个顶点输入到数组，以构成最后一条作为最后

15、一个顶点输入到数组，以构成最后一条边边P Pn nP P0 0。Sutherland-Hodgman算法2.2.准备一个输出数组准备一个输出数组Q Q，用来接收输出的顶点。用来接收输出的顶点。3.3.依次从依次从P P 中取出一条边，前一个点放入前点变中取出一条边，前一个点放入前点变量量S S，后一个点放入后点变量后一个点放入后点变量P P。4.4.按照下列原则将相应的点依次存入按照下列原则将相应的点依次存入Q:Q:内内内内，输出后点；，输出后点；内外内外，输出交点；，输出交点；外外外外，不输，不输出；出；外内外内，输出交点和后点。，输出交点和后点。5.5.返回返回3 3，直到所有的边处理完毕

16、。，直到所有的边处理完毕。内侧外侧内侧外侧内侧外侧内侧外侧SPiSPSPSPi输出后点输出后点输出交点输出交点不输出不输出输出交点和后点输出交点和后点Weiler-Atherton算法l l该算法用于多边形裁剪多边形l l被裁剪多边形称为主多边形，裁剪窗口称为裁剪多边形l l多边形裁剪多边形在地理信息系统中应用广泛。如统计某行政区某种作物面积行政区划 某种作物某种作物Weiler-Atherton算法l l主多边形为A，裁剪多边形为B。约定多边形外部边界的顶点顺序取逆时针方向，内部边界的顶点顺序取顺时针方向。保持多边形区域位于有向边左侧。P0P0P1P2P3P4P2P1P3Weiler-Ath

17、erton算法l l主多边形A为：P0P1P2P0;裁剪多边形B为:Q0Q1Q2Q0。l l建立主多边形和裁剪多边形顶点表，分别依次排列主多边形和裁剪多边形顶点。P P0 0P P1 1P P2 2P P3 3P P0 0QQ0 0QQ1 1QQ2 2QQ3 3QQ0 0P P0 0P P1 1P P2 2P P3 3QQ0 0QQ1 1QQ2 2QQ3 3Weiler-Atherton算法l l求出主多边形和裁剪求出主多边形和裁剪多边形的交点，并将多边形的交点，并将交点按照顺序插入到交点按照顺序插入到两个多边形顶点表中。两个多边形顶点表中。P P0 0P P1 1P P2 2P P3 3QQ

18、0 0QQ1 1QQ2 2QQ3 3I0I1I2I3I4I5I6I7Q0P1P2P3P0P0Q1Q2Q3Q0I0I1I2I3I4I5I6I0I1I2I3I4I5I6I7I7Weiler-Atherton算法l l在两个表的相同交点之间建立双向指针Q0P1P2P3P0P0Q1Q2Q3Q0I0I1I2I3I4I5I6I0I1I2I3I4I5I6I7I7Weiler-Atherton算法l l利用这两个表进行裁剪：1.1.建立空的裁剪结果多边形的顶点表2.2.选取任意一个没有被跟踪的交点为起点，将其输出到结果多边形顶点表中Weiler-Atherton算法3.3.如果该交点为如果该交点为进进点点，跟

19、踪主多边，跟踪主多边形边界顶点表；形边界顶点表；出点出点，跟踪裁剪，跟踪裁剪多边形边界顶点多边形边界顶点表表Q0P1P2P3P0P0Q1Q2Q3Q0I0I1I2I3I4I5I6I0I1I2I3I4I5I6I7I7进点：进点：主多边形边界主多边形边界由此进入裁剪多由此进入裁剪多边形区域边形区域出点：出点：主多边形边界主多边形边界由此离开裁剪多由此离开裁剪多边形区域边形区域Weiler-Atherton算法4.4.跟踪多边形边界，每遇到多边形顶点，将其输跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直到遇到新的交点出到结果多边形顶点表中，直到遇到新的交点5.5.将该交点输出到结果多边形顶点表中，并通过将该交点输出到结果多边形顶点表中，并通过双向指针，转到另一个多边形边界顶点表双向指针，转到另一个多边形边界顶点表6.6.重复如此，直到回到起点。重复如此，直到回到起点。7.7.查找没有被跟踪过的交点，再进行新的跟踪，查找没有被跟踪过的交点，再进行新的跟踪，直到所有的交点都被跟踪过。裁剪结束。直到所有的交点都被跟踪过。裁剪结束。