二维图形裁剪

《二维图形裁剪》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二维图形裁剪1二维图形裁剪1直线段的裁剪2多边形的裁剪3字符的裁剪2窗口内的图形是用户希望在屏幕上输出的，窗口是裁剪图形的标准参照物。裁剪：确定图形中哪些部分落在窗口之内，哪些落在窗口之外,以便只显示落在窗口内/外的那部分图形。这个选择过程称为裁剪。图形裁剪算法，直接影响图形系统的效率。二维图形裁剪－概述裁剪窗口3DisplayWindowWindow3Window2Window1外裁剪在多窗口场合较常用。例如：DisplayWindow：内裁剪，针对Window1－3外裁剪；Window2：内裁

2、剪，针对Window1、3外裁剪；Window1、3：各自内裁剪。二维图形裁剪－内裁剪、外裁剪41直线段的裁剪1.直接求交算法2.Cohen-SutherLand算法(编码法)3.中点分割算法4.Nicholl-Lee-Nicholl算法5.Cyrus-Beck算法(参数法)6.Liang－Barskey算法7.凹多边形窗口的裁剪51直线段的裁剪任何图形都可能包含点、直线、曲线、字符和多边形等图元，但它们都可以分解成点的集合。能否将直线段裁剪问题简化为点的裁剪问题？假设窗口的左下角坐标为(xL,y

3、B),右上角坐标为(xR,yT)，对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式：xL<=x<=xRandyB<=y<=yT否则，P点就在窗口外。(xL,yB)(xR,yT)PPP问题：对于任意多边形窗口，如何判别？－点与多边形的内外关系判别。6直线段的裁剪直线段裁剪是复杂图形裁剪的基础。直线段常见；可构成多边形；复杂的曲线可以通过直线段来逼近。曲线裁剪可否转化为直线段的裁剪？7直线段的裁剪直线段与窗口的关系通常有以下三种情况：整个线段全在窗口内；整个线段全在窗口外；线段部分在窗口

4、外，部分在窗口内。当窗口为凸多边形时，任何一条直线段只会至多有一段在窗口内：当一条直线段的两个端点全在窗口内时，该直线段整个在窗口内；当一条直线段的两个端点，一个在窗口内，一个在窗口外时，该直线段部分在窗口内，部分在窗口外；当一条直线段的两个端点全在窗口外时，该直线段可能整个在窗口外，也可能部分在窗口内，部分在窗口外。8直线段的裁剪直线段裁剪：实质上就是快速判断出线段与裁剪窗口的关系；(1)线段完全可见；(2)显然不可见；(3)其它。然后对于可见部分，求出端点，绘制线段。为提高效率：快速判断情形

5、(1)、(2)；对于情形(3)，如果部分可见，应设法快速求出线段和裁剪窗口的交点。91.直接求交算法如何判断线段是否显然不可见？直线与窗口边如何求交？Y求交点I0、I1，I0I1既为可见部分ExitYP1在窗口内？NP=P0P0=P1P1=PExitN求交点I，P0I既为可见部分NP0P1显然不可见？YP0P1不可见ExitNP0P1与窗口有交？NYP0在窗口内？P1在窗口内？YP0P1完全可见Exit101.直接求交算法直线段与窗口边如何求交？－两线段求交参数式、非参数式设直线过P1(x1,y1

6、)，P2(x2,y2)，m为斜率，则：直线与窗口各边的交点为：L，xL，y=m(xL-x1)+y1，m≠∞R，xR，y=m(xR-x1)+y1，m≠∞T，yT，x=x1+(1/m)(yT-y1)，m≠0B，yB，x=x1+(1/m)(yB-y1)，m≠0总会求出一个交点，即使交点位于窗口外。111.直接求交算法解方程组→求出交点参数tl、te∈[0,1]îíì-+=-+=)()(:),(),(010010111000lltl∈[0,1]yytyyxxtxxyxPyxP的参数方程为îíì=-+=)(

7、minminmaxmineyyxxtxx矩形窗口下边的参数方程为:te∈[0,1]îíì=-+-+=-+)()()(),(),(min010minmaxmin010111000lelyyytyxxtxxxtxyxPyxP和矩形窗口下边的交点满足方程组tl∈[0,1]te∈[0,1]121.直接求交算法盲目求交，计算量大132.Cohen-SutherLand算法这是一个最早最流行的线段裁剪算法。自1968年以来被公认为是一个好的算法，也称编码算法。该算法通过初始测试来减少要计算的交点数目从而加快线

8、段裁剪算法的速度。基本思想：对于每条线段P1P2分为三种情况处理:（1）若P1P2完全在窗口内，则显示该线段P1P2。（2）若P1P2明显在窗口外，则丢弃该线段。（3）若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。递归的裁剪过程142.Cohen-SutherLand算法为快速判断，采用如下编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码：CtCbCrCl（上下右左）；直线的端点都按