第4章 裁剪.pptVIP

多边形顶点的排列顺序是外环：顺时针 ；内环：逆时针（使多边形区域位于有向边的右侧 ） 主多边形和裁剪多边形把二维平面分成两部分。 裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界 B A Weiler-Atherton多边形裁剪算法 内裁剪：A∩B 外裁剪：A-B 无论对主多边形还是裁剪多边形的顶点，外部边界的顶点按顺时针排列，内部边界的顶点按逆时针排列。 S1 I1 I8 I2 S2 S3 S4 S5 S6 I3 I4 I5 I6 I7 C1 C4 C2 C3 P189图9-23 出点：沿主多边形边离开裁剪多边形内部的交点。 进点：沿主多边形边进入裁剪多边形内部的交点。 主多边形和裁剪多边形的交点分为进点和出点两类。 哪些是进点？哪些是出点？ Weiler-Atherton多边形裁剪算法 内表存放裁剪结果(内侧多边形)。外表存放主多边形被窗口裁掉的部分(外侧多边形). (4)裁剪:内侧多边形的生成(内表)和外侧多边形（外表）的生成过程不同。 (3)建立两类交点表:进点表和出点表； (2)求出主多边形和裁剪多边形的交点,并将交点分别加入SP和CP中； (1)建立主多边形的顶点表SP和裁剪多边形的顶点表CP； 内侧多边形的生成(内表) S1 I1 I2 S2 I3 S3 I4 S4 S5 I5 I6 S6 I7 I8 S1 C1 I8 I1 C2 I2 I3 C3 I4 I5 C4 I6 I7 C1 开始 完成 a)从进点表中取出一个交点,若交点表为空,则处理结束; b) 跟踪SP表,直到发现下一个交点,复制这一段SP表并记入内表中; c) 转到CP表的该交点位置,跟踪CP表,直到发现下一交点,复制这段CP表并记入内表中,再转回SP表; d)重复上述过程,直到回到起始交点处. S1 I1 I8 I2 S2 S3 S4 S5 S6 I3 I4 I5 I6 I7 C1 C4 C2 C3 SP表 CP表 内侧多边形为：I1I2I3S3I4I5I6I7I8I1 S1 I1 I8 I2 S2 S3 S4 S5 S6 I3 I4 I5 I6 I7 外侧多边形的生成(外表) S1 I1 I2 S2 I3 S3 I4 S4 S5 I5 I6 S6 I7 I8 S1 C1 I8 I1 C2 I2 I3 C3 I4 I5 C4 I6 I7 C1 开始 完成 a) 从出点表中取出一个交点,若交点表为空,则处理结束; b)跟踪SP表,直到发现下一个交点,复制这一段SP表并记入外表中; c)转到CP表的该交点位置,反向跟踪CP表,直到发现下一交点,复制这段CP表并记入外表中,再转回SP表; d)重复上述过程,直到回到起始交点处. C1 C2 C3 C4 外侧多边形：I2S2I3I2，I4S4S5I5I4，I6S6I7I6 I8S1I1I8 SP表 CP表 字符可分为 矢量字符和点阵字符。 4.3 字符裁剪 字符串的裁剪按三种精确度进行:串精度裁剪、字符精度裁剪、笔画精度裁剪。 点阵字符：由点阵表示。 矢量字符：由单个的线段或笔画表示； 第4章 4.1 直线段裁剪算法 4.2 多边形裁剪的算法 4.3 字符裁剪 主要教学内容 确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形,这个选择过程称为裁剪。 该显示区被称为裁剪窗口。 4.1 直线段裁剪算法 假设矩形窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，则点P(x,y)在窗口内的条件是： (xL,yB ) (xR,yT ) P 点的位置是裁剪中最基本的问题 否则，P点就在窗口外。 满足： xL = x = xR 和 yB = y = yT 直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。 快速判断情形(1)(2)， 对于情形(3)，设法减 少求交次数和每次求 交时所需的计算量。 a b c 裁剪线段与窗口的关系： (1