开发动态web网站的几种技术

《开发动态web网站的几种技术》由会员分享，可在线阅读，更多相关《开发动态web网站的几种技术（32页珍藏版）》请在金锄头文库上搜索。

1、1、Cohen-Sutherland算法本算法又称为编码裁剪算法，算法的基本思想是对 每条直线段p1(x1,y1)，p2(x2,y2)分三种情况处理：a、若点p1和p2完全在裁剪窗口内，则该直线段完全可 见， “简取”之。b、若点p1和p2均在窗口外，且满足下列4个条件之一，直线段完全不可见，“简弃”之。c、直线段既不满足“简取”的条件，也不满足“简弃 ” 的条件，需要对直线段按交点进行分段，分段后 重复上述处理。算法具体实现是：每条线段的端点都赋以四位二进 制码D3D2D1D0 ，称为区域码，用来标识出端点相对于 裁剪矩形边界的位置。编码规则如下：若xwxr，则D1=1，否则D1=0；若yw

2、yt，则D3=1，否则D3=0。区域码的各位指出端点对于裁剪窗口的四个相对坐 标位置：左、右、下、上。将区域码各位从右到左编 号，则坐标区域与各位的关系为：位1：左位2：右位3：下位4：上任何位赋值为1，代表端点落在相应的位置上，否 则该位置为0。根据该编码规则，窗口及其延长线所构成的9个区 域的编码如图所示。01000101100100011010011010000010窗口及区域编码D3D2D1D0窗口0000裁剪一条线段时，先求 出端点p1和p2的编码code1 和code2，然后进行处理：（1）若code1|code2=0 ，对直线段应简取之。（2）若code1&code20，对 直线

3、段可简弃之。这是因为若code1和code2经按位与运算后的结果不 为0，说明两个端点同在窗口的上方、下方、左方或 右方。（3）若上述两条件均不成立。则需求出直线段与窗 口边界的交点。在交点处把线段一分为二，其中必有 一段完全在窗口外，可以弃之。再对另一段重复进行 上述处理，直到该线段完全被舍弃或者找到位于窗口 内的一段线段为止。实现时，一般按固定顺序检查直线段端点的编码位 是否为0。这里按左、右、下、上的顺序。与窗口边 界求交的顺序也可以任意选择，这里也按左（x=wxl ）、右（x=wxr）、下（y=wyb）、上（y=wyt）的顺 序进行。对于端点坐标为（x1，y1）和（x2，y2）的直线，

4、 与左、右边界交点的y坐标可以这样计算：其中，x为wxl或wxr，线段的斜率为：与上、下边界交点的x坐标可以这样计算：其中，y为wyb或wyt。下面写出Cohen-Sutherland直线段裁剪算法的步骤：（1）输入直线段的两端点坐标： P1（x1，y1），P2 （x2，y2）,以及窗口的四条边界坐标：wyt、wyb、 wxl和wxr。（2）对P1、P2编码：点P1的编码为code1，点P2的编 码为code2。（3）若code1|code2=0，对直线段应简取之，转（6） ；否则，若code1&code20，对直线段可简弃之，转 （7）；当上述两条均不满足时，进行步骤（4）。（4）确保P1在

5、窗口外部：若P1在窗口内，则交换P1 和P2的坐标值和编码。（5）按左、右、下、上的顺序求出直线段与窗口边 界的交点，并用该交点的坐标值替换P1的坐标值。也就是在交点，假定为S，S处把线段一分为二， 并去掉P1S这一段（考虑到P1是窗口外的一点，因此 可以去掉P1S转（2）。（6）画出当前的直线段P1 P2 。（7）算法结束 。下面根据该算法步骤来裁剪如图所示的直线段P1P2 ：P1P2P3P4直线段P1P2的编码裁剪001010001001000010100101000101100100首先对P1P2进行编 码， P1的编码code1 为0001，P2的编码 code2为0100。由于 co

6、de1|code20，且 code1&code2=0，因 此对直线段P1P2既不 能简取也不能简弃， 故进行求交处理。由code1=0001知P1在窗口左外侧，按左、右、下、 上的顺序求出直线段与窗口左边界的交点为P3， P1P3 必在窗口外，可简弃之。对P2P3重复上述处理（此时用原P3替换P1）： P1（原 P3）的编码为0000，P2编码为0100，因此对直线段P1P2 既不能简取也不能简弃。由于P1（原P3）已在窗口内，交换P1、P2的坐标值和 编码，按左、右、下、上的顺序求出P1P2与窗口下边 界的交点P4 ，丢弃P1（原P2）P4 。剩下的直线段（P3P4）再进行进一步判断， co

7、de1|code2=0，全在窗口中，简取之。Cohen-Sutherland算法用编码的方法实现了对完全 可见和不可见直线段的快速接受和拒绝。比较适合两 种情况：一是大部分线段完全可见；二是大部分线段 完全不可见。2、Liang-Barsky算法在Cohen-Sutherland算法提出后，Cyrus和Beck用 参数化方法提出了针对凸多边形的裁剪算法，它比编 码算法更有效。而梁友栋和Barsky 又针对标准矩形 窗口提出了更快的Liang-Barsky直线段裁剪算法。Liang-Barsky算法的基本出发点是直线的参数方程 。给出任一条直线段P1（x1，y1），P2（x2，y2），其 参数方

8、程为：其中，（x,y）为直线上任意一点。如果直线上一 点（x,y）位于由坐标（x,y）和（x,y）所确定的窗 口内，则有下式成立：即有：将 代入上式可以得到：令：于是有：其中，k = 1，2，3，4。首先分析pk=0的情况，若p1=p2=0,则直线与窗口边 界wxl和wxr平行。其中k对应于该裁剪边界（k=1, ,3,4对应于左、右、下、上边界）。(a)直线段与窗口边界 wxl和wxr平行的情况wytwybwxlwxrABCDEF从右图中可以看出，若 满足 q1umin，则直线段在窗口外，删除该直线。若 umaumin，将uma和umin代回直线的参数方程即求出直 线与窗口的两实交点坐标。注：

9、 当Pk0，表示线段从裁剪边界延长线的 内部延伸到外部。对于每条直线，可以计算出参数umax和umin，它们定 义了在裁剪矩形内的线段部分。 umax的值由线段从外 到内遇到的矩形边界所决定（p0）。 umin取1和uk值之中的最小值。如果 umaxumin，则线段完全落在裁剪窗口之外，删除该直线 ；若umaxumin，将umax和umin代回直线参数方程，即求 出直线与窗口的两实交点坐标。 上述解的几何意义可以这样来看：将直线与窗口边 界的实交点和虚交点分为两组，下限组以pk0为特征：表示在该处，直线从裁剪 边界延长线的内部延伸到外部。在有交情形，下限组 分布于直线段起点一侧，上限组分布于直

10、线段终点一 侧，则下限组的最大值和上限组的最大值就分别对应 于直线与窗口边界的实交点（假定存在）。类似地，若p3=p4=0,则直线与窗口边界wyb和wyt 平行，如右图所示。(b)直线段与窗口边界 wyb和wyt平行的情况wxrwxlwybwytGHIJKL若q3umin，则直线段在窗口外，删除该直线。 若umaxumin，将umax和umin代回直线参数方程，即求 出直线与窗口的两实交点坐标。 对于PK0的情况，则直接求出直线段与窗口边界 的交点：同样， uk是窗口边界及其延长线的交点的对应值 。此时分别计算umax和umin：若umaxumin，则直线段在窗口外，删除该直线。若 umaxu

11、min，将umax和umin代回直线参数方程，即求出直 线与窗口的两实交点坐标。 下面写出Liang-Barsky算法的算法步骤：（1）输入直线段的两端点坐标（x1,y1）、（x2,y2） ，以及窗口的四条边界坐标：wxl、wxr、wyb和wyt。（2）若X=0，则p1=p2=0,此时进一步判断是否满足 q1umin，则直线 段在窗口外，算法转（7）。若umaumin，利用直线的 参数方程：求得直线段与窗口的两实交点坐标。（6）利用直线的扫描转换算法绘制在窗口内的直线段。（7）算法结束。3、多边形的裁剪假定直接用上述介绍的直线段裁剪算法对多边形的 每条边进行裁剪，会得到下面的情况：(a)裁剪前

12、(b)直接采用直线段 裁剪的结果即得到一系列不连续的直线段。而实际上，应该得到的是下图所示的有边界的区域：(c)正确的裁剪结果多边形裁剪算法的输出应该是定义裁剪后的多边形 边界的顶点序列。于是，需要构造能产生一个或多个 封闭区域的多边形裁剪算法。Sutherland-Hodgeman多边形裁剪该算法又称逐边裁剪算法，其基本思想是将多边 形边界作为一个整体，每次用窗口的一条边界对要裁 剪的多边形进行裁剪，体现一种分而治之的思想。窗 口各边界裁剪的多边形存储输入与输出顶点表在窗口 的一条裁剪边界处理完所有顶点后，其输出顶点表将 用窗口的下一条边界继续裁剪。每次裁剪时把落在窗口外部区域的图形去掉，只

13、保 留落在窗口内部区域的图形，并把它作为下一次裁剪 的多边形。依次用窗口的四条边界（按任何顺序均可 ，这里采用左、下、右、上的顺序）对要裁剪的多边 形进行裁剪，则原始多边形即被裁剪完毕。输入：ABCDEFGHABCDEFGH输出：A12DEFGH12(a)用左边界裁剪输出：A134D56FGHADEFGH输入：A12DEFGH12(b)用下边界裁剪3456从上图中可以看到，窗口的一条边及其延长线构成 的裁剪线把平面分为两个区域：包含有窗口区域的一 个域称为可见侧；不包含窗口区域的域为不可见侧。这样，沿着多边形依次处理顶点会遇到四种情况：SPI(a)输出I、P可见侧一是第一点S在不可见侧面而第二

14、 点P在可见侧，则多边形的该边与窗 口边界的交点I与第二点P均被加入 到输出顶点表中。SP(b)输出P可见侧二是S和P都在可见侧 ，则P、S被加入到输出 顶点表中；三是S在可见侧，而P在不可见侧 ，则交点I被加入到输出顶点表中；SPI(c)输出I可见侧SP(d)不输出可见侧四是如果S和P都在不可见侧，输出顶点表中不增加 任何顶点。在窗口的一条裁剪边界处理完所有顶点后，其输出 顶点表将用窗口的下一条边界继续裁剪。A(a)裁剪前BCDEF(b)Sutherland-Hodgeman算法的裁剪结果ABCDEFV1V2V3V4要实现上述算法，就要为窗口各边界裁剪的多边形 存储输入与输出顶点表，如果每一步仅仅裁剪点并且 将裁剪后的顶点传输到下一边界的裁剪程序，就可以 减少中间输出顶点表。这样就可以用并行处理器或单处理器的裁剪算法 的流水线完成。只有当一个点（输入点或交点）被 窗口的4个边界都判定在窗口内或窗口边界上时， 才加入到输出顶点表。因此，该算法特别适合于用 硬件实现。