二维图形的裁剪.ppt

2020 2 16 计算机科学与技术学院 1 二维图形裁剪 二维裁剪概念点的裁剪直线的裁剪多边形的裁剪字符串的裁剪 2020 2 16 计算机科学与技术学院 2 二维裁剪 识别图形在指定区域内和区域外的部分的过程称为裁剪算法 简称裁剪 clipping 二维窗口是投影平面上的一个矩形 一般来说 这个矩形的边和投影平面上的坐标轴平行 图形在窗口内的部分被显示出来 窗口外的部分被裁剪掉了 平面上的图形受该矩形的裁剪称为二维裁剪 2020 2 16 计算机科学与技术学院 3 裁剪的应用从定义的场景中抽取用于观察的部分在三维视图中识别出可见面防止线段或对象的边界混淆用实体造型来创建对象显示多窗口的环境允许选择图形的一部分来进行拷贝 移动或删除等绘图操作裁剪算法类型图形裁剪与窗口 视图变换的先后窗口边界裁剪视区边界裁剪图形生成与裁剪先后先生成后裁剪先裁剪后生成 2020 2 16 计算机科学与技术学院 4 点的裁剪 图形裁剪中的最基本的问题 假设裁剪窗口为一个在标准位置的矩形 即边与坐标轴平行的矩形 由上 y ymin 下 y ymax 左 x xmin 右 x xmax 四条边描述 点 x y 在窗口内的充分必要条件是 裁剪窗口 Xmin Xmax Ymin Ymax 是世界坐标系的窗口边界或视区边界应用举例爆炸场景或海面泡沫的显示问题 对于任何多边形窗口 如何判别 2020 2 16 计算机科学与技术学院 5 直线段裁剪 直线段裁剪算法是复杂图形裁剪的基础 复杂的曲线可以通过折线段来近似 从而裁剪问题也可以化为直线段的裁剪问题 裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分裁剪处理的基础图元关于窗口内外关系的判别图元与窗口的求交假定条件矩形裁剪窗口 xmin xmax X ymin ymax 待裁剪线段 2020 2 16 计算机科学与技术学院 6 直线段裁剪 待裁剪线段和窗口的关系 1 完全落在窗口内 线段完全可见 2 完全落在窗口外 显然不可见 3 与窗口边界相交 线段至少有一端点在窗口之外 但非显然不可见 2020 2 16 计算机科学与技术学院 7 要确定一条直线段上位于窗口内的可见段 只须求出它的两个位于窗口内的可见端点即可 算法的基本思想把所有的直线按照它和窗口的关系分类 不同的直线使用不同的处理方法确定其可见部分 2020 2 16 计算机科学与技术学院 8 为提高效率 算法设计时应考虑 一 快速判断情形 1 2 二 设法减少情形 3 求交次数和每次求交时所需的计算量 直线裁剪算法的主要步骤 首先将不需要裁剪的直线挑出 并删去其中在窗外的直线 其次 对其余直线 逐条与窗框求交点 并将窗外部分删去 2020 2 16 计算机科学与技术学院 9 实交点是直线段与窗口矩形边界的交点 虚交点则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点 2020 2 16 计算机科学与技术学院 10 直线的剪裁算法 直接求交算法矢量裁剪法Cohen Sutherland算法中点分割算法梁友栋 Barsky算法Nicholl Lee Nicholl算法 2020 2 16 计算机科学与技术学院 11 直接求交算法 直线与窗口边都写成参数形式 求参数值 2020 2 16 计算机科学与技术学院 12 矢量裁剪法 算法思想先从线段的一个端点出发进行判断或进行求交运算 所得交点坐标保存在 xs ys 中 然后再从线段的另一个端点出发用前面的判断及其求交运算求得交点坐标 x y 最后只输出两个交点间的线段 用窗口的四条边界的直线将窗口分为9个区 0 1 2 3 4 5 6 7 8 x2 y2 yb yt xl xr x1 y1 2020 2 16 计算机科学与技术学院 13 排斥性测试若线段满足下述四个条件之一时 max x1 x2 xlmin x1 x2 xrmax y1 y2 ybmin y1 y2 yt则线段必定位于窗口之外 无输出线段 包含性测试若线段满足 xl x1 xr yb y1 yt 则线段的始点在0区 也即线段可见段的起点为 xs x1 ys y1 2020 2 16 计算机科学与技术学院 14 求交点 并判断I 若x1 xl 则 线段的起点坐标可能位于3区 4区 5区 而新起点的坐标可能在直线y yb和线段的交点上直线y yt和线段的交点上直线x xl和线段的交点上 0 1 2 3 4 5 6 7 8 x1 y1 x2 y2 yb yt xl xr 2020 2 16 计算机科学与技术学院 15 第一种情况 此时 若xl xs xr则 xsys 为有效新起点 第二种情况 此时 若xl xs xr则 xsys 为有效新起点 第三种情况 此时 若yb ys yt则 xsys 为有效新起点 三种情况都不满足 则此线段不在窗口区内 2020 2 16 计算机科学与技术学院 16 II 若x1 xr线段的起点坐标可能位于6区 7区 8区 而新起点的坐标可能在直线y yb和线段的交点上直线y yt和线段的交点上直线x xr和线段的交点上 0 1 2 3 4 5 6 7 8 x1 y1 yb yt xl xr 2020 2 16 计算机科学与技术学院 17 第一种情况 此时 若xl xs xr则 xsys 为有效新起点 第二种情况 此时 若xl xs xr则 xsys 为有效新起点 第三种情况 此时 若yb ys yt则 xsys 为有效新起点 若此三种情况都不满足 则此线段不在窗口区内 2020 2 16 计算机科学与技术学院 18 III若Xl X Xr线段的起点坐标可能位于1区和2区 而新起点的坐标可能在直线y yb和线段的交点上直线y yt和线段的交点上 0 1 2 3 4 5 6 7 8 x1 y1 yb yt xl xr 2020 2 16 计算机科学与技术学院 19 第一种情况 此时 若xl xs xr则 xsys 为有效新起点 第二种情况 此时 若xl xs xr则 xsys 为有效新起点 若此二种情况都不满足 则此线段不在窗口区内 使用同样的方法 可得到直线在窗口的另一个可见端点 2020 2 16 计算机科学与技术学院 20 Cohen Sutherland算法 编码算法 基本思想 Cohen Sutherland直线剪裁算法以区域编码为基础 将窗口及其周围的八个方向以4bit的二进制数进行编码 对每条直线段p0 x0 y0 p1 x1 y1 分三种情况处理 1 直线段完全可见 简取 之 2 直线段完全不可见 简弃 之 3 直线段既不满足 简取 的条件 也不满足 简弃 的条件 需要对直线段按交点进行分段 分段后重复上述处理 2020 2 16 计算机科学与技术学院 21 算法步骤 第一步判别线段两端点是否都落在窗口内 如果是 则线段完全可见 否则进入第二步 第二步判别线段是否为显然不可见 如果是 则裁剪结束 否则进行第三步 第三步求线段与窗口边延长线的交点 这个交点将线段分为两段 其中一段显然不可见 丢弃 对余下的另一段重新进行第一步 第二步判断 直至结束 裁剪过程是递归的 2020 2 16 计算机科学与技术学院 22 2020 2 16 计算机科学与技术学院 23 Cohen SutherLand算法 编码算法 特点 对显然不可见线段的快速判别编码方法 延长窗口的四条边线 由窗口四条边所在直线把二维平面分成9个区域 每个区域赋予一个四位编码 CtCbCrCl 上下右左 左域 右域 上域 下域 内域 2020 2 16 计算机科学与技术学院 24 第一位1 点处于上边框线的上边 第二位1 点处于下边框线的下边 第三位1 点处于右边框线的右边 第四位1 点处于左边框线的左边 显然 如果某线段的两端点的两个四位代码全为零时那么该线段完全位于窗口内 即全为 0000 可直接保留 如果两端点的标识码的逻辑与 按位乘 运算 结果不为零 那么该线段必位于窗口外 可直接舍弃 否则 这一线段可能与窗口相交 此时 需要对线段进行再分割 即找到与窗口边线的一个交点 根据交点位置 赋予四位二进制编码 然后再进行上述测试 测试结果是必有一段在窗口之外 可被排除 另一段再重复上述处理过程 直到全部线段均被舍弃或被保留为止 2020 2 16 计算机科学与技术学院 25 Cohen SutherLand算法 编码算法 端点编码 定义为它所在区域的编码结论 当线段的两个端点的编码的逻辑 与 非零时 线段为显然不可见的 2020 2 16 计算机科学与技术学院 26 求交测试顺序固定 左上右下 最坏情形 线段求交四次 Cohen SutherLand算法 编码算法 对于那些非完全可见 又非显然不可见的线段 需要求交 如 线段AD 求交前先测试与窗口哪条边所在直线有交 按序判断端点编码中各位的值ClCtCrCb 2020 2 16 计算机科学与技术学院 27 1 特点 容易将不需要裁剪的直线挑出 规则是 如果一条直线的两端在同一区域 则该直线不需要裁剪 否则该直线为可能裁剪直线 对可能裁剪的直线缩小了与之求交的边框范围 规则是 如果直线的一个端点在上 下 左 右 域 则此直线与上边框求交 然后删去上边框以上的部分 该规则对直线的另一端点也适用 一条直线至多只需要与两条边框求交 用编码方法可快速判断线段 完全可见和显然不可见 2 特别适用二种场合 大窗口场合 窗口特别小的场合 如光标拾取图形时 光标看作小的裁剪窗口 2020 2 16 计算机科学与技术学院 28 P1 3 2 1 6 编码 0001 P2 1 2 3 2 编码 1000 2 求右边交点 得P 1 1 11 6 P2 1 1 2 并编码 判别之不可见 求左边交点 得P 1P2 P 1 1 1 2 编码 0000 判别知非完全可见 且P 1在窗口内 因此交换P 1P2得新线段P1P2 P1 1 2 3 2 编码 1000 P2 1 1 2 编码 0000 3 求上边交点 得P 1 1 4 1 P2 1 1 2 并编码 两端点编码全部为0 线段完全可见 程序结束 2020 2 16 计算机科学与技术学院 29 Cohen SutherLand算法 编码算法 如何判定该与窗口的哪条边求交呢 编码中对应位为1的边 2 if ai bi ci di 0 则显示整条直线 取出下一条直线 返回1 否则if a1 a2 or b1 b2 or c1 c2 or d1 b2 1 则取出下一条直线 返回1 否则 例子 依次对每条直线P1P2作如下处理1 对直线两端点P1 P2按各自所在的区域编码 P1 P2的编码分别记为 C1 P1 a1 b1 c1 d1 C2 P2 a2 b2 c2 d2 其中ai bi ci di取值域为 0 1 i 1 2 2020 2 16 计算机科学与技术学院 30 3 if a1 a2 1 则求直线与窗上边 y yw max 之交点 并删去交点以上部分 if b1 b2 1 则求直线与窗下边 y yw min 之交点 并删去交点以下部分 if c1 c2 1 则求直线与窗右边 x xw max 之交点 并删去交点以右部分 if d1 d2 1 则求直线与窗左边 x xw max 之交点 并删去交点以左部分 4 返回1 2020 2 16 计算机科学与技术学院 31 2020 2 16 计算机科学与技术学院 32 中点分割算法 基本思想 从P0点出发找出离P0最近的可见点 和从P1点出发找出离P1最近的可见点 这两个可见点的连线就是原线段的可见部分 定义 线段端点的最近可见点是指任一线段被窗口裁剪后所得两个新端点中离该端点较近的一个点 从P0点出发找出距P0最近的可见点 图中为A点 从P1点出发找出距P1最近的可见点 图中为B 取中点Pm P1 P2 2 2020 2 16 计算机科学与技术学院 33 中点分割法 与前一种Cohen Sutherland算法一样首先对线段端点进行编码 并把线段与窗口的关系分为三种情况 全在 完全不在和线段与窗口有交 对前两种情况 进行一样的处理 对第三类线段的处理当对直线段不能简取也不能简弃时 不断地用对分方法 舍去线段的不可见部分 用中点去逼近线段与窗口边界的交点 简单地用中点分割的方法求出线段与窗口的交点 把线段等分为二段 对两段重复上述测试处理 直至每条线段完全在窗口内或完全在窗口外 2020 2 16 计算机科学与技术学院 34 实现算法 以P0点为例说明 1 排斥性测试测试线段是否完全被排斥在窗口之外 若是 则无线段输出 算法结束 否则执行下一步 2 包含性测试测试P1点是否包含在窗口内 如果是 则P1点即为P0的最远可选点 算法结束 否则 执行下一步 3 将直线段P0P1于中点Pm处分割 则分如下几种情况处理 2020 2 16 计算机科学与技术学院 35 线段MP1完全在窗口之外 那么便以线段P0M为新的线段P0P1 然后返回算法的第一步重新开始测试 如果线段MP1没有被完全排斥在窗口之外 那么便以线段MP1作为新线段P0P1 然后返回算法的第一步 P0 P1 M P0 P1 M P0 P1 M P0 P1 M 2020 2 16 计算机科学与技术学院 36 中点分割算法 求线段与窗口的交点 从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm 若P0Pm不是显然不可见的 并且P0P1在窗口中有可见部分 则距P0最近的可见点一定落在P0Pm上 所以用P0Pm代替P0P1 否则取PmP1代替P0P1 再对新的P0P1求中点Pm 重复上述过程 直到PmP1长度小于给定的控制常数为止 此时Pm收敛于交点 从P1出发找距离P1最近可见点采用上面类似方法 2020 2 16 计算机科学与技术学院 37 中点分割算法框图 2020 2 16 计算机科学与技术学院 38 算法步骤 1 输入直线段的两端点坐标 p0 x0 y0 p1 x1 y1 以及窗口的四条边界坐标 ymin ymax xmin和xmax 2 对p0 p1进行编码 点p0的编码为code1 点p1的编码为code2 3 若code1 code2 0 对直线段应简取之 保留当前直线段的端点坐标 转 5 否则 若code1 code2 0 对直线段可简弃之 转 5 当上述两条均不满足时 进行步骤 4 4 求出直线段的中点M 将p1M p2M入栈 5 当栈不空时 从栈中弹出一条直线段 取为p0p1 转 2 进行处理 否则 继续 6 6 当栈为空时 合并保留的直线段端点 得到窗口内的直线段p0p1 用直线扫描转换算法画出当前的直线段p0p1 算法结束 2020 2 16 计算机科学与技术学院 39 中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点 2020 2 16 计算机科学与技术学院 40 2020 2 16 计算机科学与技术学院 41 重新构造算法步骤 1 若code1 code2 0 对直线段应简取之 结束 否则 若code1 code2 0 对直线段可简弃之 结束 当这两条均不满足时 进行步骤 2 2 找出该直线段离窗口边界最远的点和该直线段的中点 判中点是否在窗口内 若中点不在窗口内 则把中点和离窗口边界最远点构成的线段丢掉 以线段上的另一点和该中点再构成线段求其中点 如中点在窗口内 则又以中点和最远点构成线段 并求其中点 直到中点与窗口边界的坐标值在规定的误差范围内相等 则该中点就是该线段落在窗口内的一个端点坐标 3 如另一点在窗口内 则经 2 即确定了该线段在窗口内的部分 如另一点不在窗口内 则该点和所求出的在窗口上的那一点构成一条线段 重复步骤 2 即可求出落在窗口内的另一点 2020 2 16 计算机科学与技术学院 42 2020 2 16 计算机科学与技术学院 43 defineTRUE1 defineFALSE0intmid trim p1 p2 xmin ymin xmax ymax a floatp1 3 p2 3 xmin ymin xmax ymax a 3 floatA 3 B 3 M 3 set point p1 A set point p2 B while TRUE if Identify line out A B xmin ymin xmax ymax TRUE retuenFALSE if Identify pt in B xmin ymin xmax ymax TRUE set point B a returnTRUE 2020 2 16 计算机科学与技术学院 44 else get midpoint A B M if Identify line out M B xmin ymin xmax ymax TRUE set point M B else set point M A 2020 2 16 计算机科学与技术学院 45 2020 2 16 计算机科学与技术学院 46 对分辩率为2N 2N的显示器 上述二分过程至多进行N次 主要过程只用到加法和除法运算 适合硬件实现 它可以用左右移位来代替乘除法 这样就大大加快了速度 中点分割裁剪算法 2020 2 16 计算机科学与技术学院 47 梁友栋 Barsky算法 算法基本思想 设要裁剪的线段为P0P1 和窗口边界交于A B C D四点 首先从D A和P0三点中找出最靠近P1的点 图中显然为A其次从C B和P1中找出最靠近P0的点 图中显然为B那么AB就是P0P1线段上的可见部分 2020 2 16 计算机科学与技术学院 48 梁友栋 Barsky算法 具体计算时将P0P1写成参数方程其中 0 t 1 2020 2 16 计算机科学与技术学院 49 梁友栋 Barsky算法 窗口边界分类 始边和终边 2020 2 16 计算机科学与技术学院 50 梁友栋 Barsky算法 交点计算 2020 2 16 计算机科学与技术学院 51 梁友栋 Barsky算法 为了确定始边和终边 以及求P0P1与它们的交点 令易知交点的参数为 2020 2 16 计算机科学与技术学院 52 梁友栋 Barsky算法 E F A B 分析另外一个D 2020 2 16 计算机科学与技术学院 53 梁友栋 Barsky算法 当Qi 0时若Di0时 分析另一D 如图中的EF就是这种情况 它使QL 0 DL 0和QR 0 DR 0 这时由于EF和x xL及x xR平行 故不必去求出EF和x xL及x xR的交点 而让EF和y yT及y yB的交点决定直线段上的可见部分 E F A B 2020 2 16 计算机科学与技术学院 54 2020 2 16 计算机科学与技术学院 55 2020 2 16 计算机科学与技术学院 56 Nicholl Lee Nicholl算法 NLN算法在求交计算前进行更多的区域测试来减少求交计算 消除C S算法中多次求交的情况 基本想法 通过在裁剪窗口周围创立多个区域来对一条直线段的多次裁剪 也即对2D平面的更细的划分 2020 2 16 计算机科学与技术学院 57 Nicholl Lee Nicholl算法 假定待裁剪线段P0P1为非完全可见且非显然不可见 步骤 第一步 窗口四边所在的直线将二维平面划分成9个区域 假定落在区域0 4 5 2020 2 16 计算机科学与技术学院 58 Nicholl Lee Nicholl算法 第二步 从P0点向窗口的四个角点发出射线 这四条射线和窗口的四条边所在的直线一起将二维平面划分为更多的小区域 此时P1的位置决定了P0P1和窗口边的相交关系 2020 2 16 计算机科学与技术学院 59 Nicholl Lee Nicholl算法 第三步 确定P1所在的区域 判断P1所在区域位置 可判定P0 P1与窗口哪条边求交 根据窗口四边的坐标值及P0P1和各射线的斜率可确定P1所在的区域 第四步 求交点 确定P0P1的可见部分 特点 效率较高 但仅适合二维矩形窗口 2020 2 16 计算机科学与技术学院 60 非矩形窗口的线段裁剪 思考 凹多边形窗口的线段裁剪圆和曲线窗口的线段裁剪 2020 2 16 计算机科学与技术学院 61 多边形裁剪 几个概念凸多边形如果多边形任意两个内点的连线都在多边形里 则该多边形称为凸多边形 凹多边形一个非凸多边形称为凹多边形多边形正方向顶点为P1 PN 并且边为Pi 1Pi PNP1 的多边形 如果按照这种顺序遍历产生一个逆时针回路 则该多边形被认为是正方向的 2020 2 16 计算机科学与技术学院 62 多边形裁剪 错觉 直线段裁剪的组合 新的问题 1 边界不再封闭 需要用窗口边界的恰当部分来封闭它 如何确定其边界 2020 2 16 计算机科学与技术学院 63 多边形裁剪 2 一个凹多边形可能被裁剪成几个小的多边形 如何确定这些小多边形的边界 2020 2 16 计算机科学与技术学院 64 多边形的剪裁算法 Sutlerland Hodgman算法Weiler Athenton算法 2020 2 16 计算机科学与技术学院 65 Sutherland Hodgman算法 对多边形裁剪的Sutherland Hodgman算法是一种简便的方法 只要对多边形用窗口的四条边依次裁剪四次 便可得到裁剪后的多边形 分割处理策略 将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪 2020 2 16 计算机科学与技术学院 66 基本思想 1 令多边形的顶点按边线逆时针走向排序 各边先与左窗边求交 求交后删去多边形在窗之左的部分 并插入左窗边及其延长线的交点之间的部分 从而形成一个新的多边形 然后 新的多边形按相同的方法与上窗边相裁剪 如此重复 直至与各窗边都裁剪完毕 2 多边形与每一条窗边相交 生成新的多边形顶点序列的过程 是一个对多边形各顶点依次处理的过程 2020 2 16 计算机科学与技术学院 67 2020 2 16 计算机科学与技术学院 68 2020 2 16 计算机科学与技术学院 69 2020 2 16 计算机科学与技术学院 70 Sutherland Hodgman算法 流水线过程 左上右下 左边的结果是上边的开始 亦称逐边裁剪算法 2020 2 16 计算机科学与技术学院 71 算法实施策略 为窗口各边界裁剪的多边形存储输入与输出顶点表 在窗口的一条裁剪边界处理完所有顶点后 其输出顶点表将用窗口的下一条边界继续裁剪 窗口的一条边以及延长线构成的裁剪线把平面分为两个区域 包含有窗口区域的一个域称为可见侧 不包含窗口区域的域为不可见侧 2020 2 16 计算机科学与技术学院 72 沿着多边形依次处理顶点会遇到四种情况 2020 2 16 计算机科学与技术学院 73 2020 2 16 计算机科学与技术学院 74 Sutherland Hodgman算法框图 2020 2 16 计算机科学与技术学院 75 设封闭多边形的顶点为P1 P2 Pn 框图中e是表示窗口的四条边中正在裁剪的一条边 每次裁剪时第一个点存放在F中 以便对最后一条边裁剪时使用 用图 a 中的算法对边P1P2 P2P3 Pn 1Pn作裁剪 用图 b 中的算法对最后一条边PnP1作裁剪 裁剪好一条边便输出一条边 上述算法仅用一条裁剪边对多边形进行裁剪 得到一个顶点序列 作为下一条裁剪边处理过程的输入 2020 2 16 计算机科学与技术学院 76 Sutherland Hodgman算法 裁剪结果的顶点构成 裁剪边内侧的原顶点 多边形的边与裁剪边的交点 顺序连接 几点说明 裁剪算法采用流水线方式 适合硬件实现 可推广到任意凸多边形裁剪窗口 2020 2 16 计算机科学与技术学院 77 Weiler Athenton算法 裁剪窗口为任意多边形 凸 凹 带内环 的情况 主多边形 被裁剪多边形 记为A裁剪多边形 裁剪窗口 记为B 2020 2 16 计算机科学与技术学院 78 主多边形和裁剪多边形把二维平面分成两部分 内裁剪 A B外裁剪 A B Weiler Athenton算法 裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成 并且在交点处边界发生交替 即由A的边界转至B的边界 或由B的边界转至A的边界 2020 2 16 计算机科学与技术学院 79 Weiler Athenton算法 如果主多边形与裁剪多边形有交点 则交点成对出现 它们被分为如下两类 进点 主多边形边界由此进入裁剪多边形内如 I1 I3 I5 I7 I9 I11出点 主多边形边界由此离开裁剪多边形区域 如 I0 I2 I4 I6 I8 I10 2020 2 16 计算机科学与技术学院 80 Weiler Athenton算法 1 建顶点表 2 求交点 3 裁剪 Weiler Athenton裁剪算法 内裁剪 步骤 1 建立主多边形和裁剪多边的顶点表 2 求主多边形和裁剪多边形的交点 并将这些交点按顺序插入两多边形的顶点表中 在两多边表形顶点表中的相同交点间建立双向指针 3 裁剪如果存在没有被跟踪过的交点 执行以下步骤 2020 2 16 计算机科学与技术学院 81 1 建立裁剪结果多边形的顶点表 2 选取任一没有被跟踪过的交点为始点 将其输出到结果多边形顶点表中 3 如果该交点为进点 跟踪主多边形边界 否则跟踪裁剪多边形边界 4 跟踪多边形边界 每遇到多边形顶点 将其输出到结果多边形顶点表中 直至遇到新的交点 5 将该交点输出到结果多边形顶点表中 并通过连接该交点的双向指针改变跟踪方向 如果上一步跟踪的是主多边形边界 现在改为跟踪裁剪多边形边界 如果上一步跟踪裁剪多