基于适应性相关测试和点斜式查表求交的圆形窗口快速裁剪方法
2012-07-09杨若瑜
路 通， 苏 丰， 杨若瑜
（南京大学计算机软件新技术国家重点实验室，江苏 南京 210093）
裁剪算法是计算机图形学的基础性方法，速度更快的算法一直是研究者的不断追求。在经典的Cohen-Sutherland线段裁剪算法提出之后又出现了许多好的裁剪方法，它们在本质上有两个共同点：一是尽量避免无效的操作，二是尽量用简单快捷的加、减等基本操作代替复杂、耗时的乘、除及开方等操作。例如，Liang-Barsky[1]方法通过正确选择相对于待裁剪线段的窗口矩形始、终边来简化判定；Nicholl–Lee-Nicholl[2]方法通过比较待裁剪线段的斜率和始点到矩形窗口各顶点连线斜率，来确定需求交的窗口边，以便避免无效的求交操作；Devai[3]方法对 Nicholl–Lee-Nicholl方法作了一定的改进；Duvanenko-Robbins-Gyurcsik[4]方法通过优化算法、减少冗余比较与浮点数运算等来提高裁剪效率；Wang-Wu-Cai[5]方法通过将待裁剪线段简单变换，使其始点位于特定区域，从而明确应求交的窗口边来加速处理；Lu-Wu-Peng[6]提出了基于待裁剪线段位置和方向的排除方法；针对圆形窗口也提出了一些裁剪方法[7-10]。但对于圆形窗口如何在排除性测试和线-圆求交等环节避免或减少大量的复杂操作，仍然是有待进一步研究的问题。
圆形窗口对线段的裁剪有众多应用需求，如在智能CAD系统的交互式图形界面中，需要实时移动“圆形放大镜”或“鹰眼”作快速图元检查或检索；在图形识别与理解等复杂图形应用系统中，需要快速计算圆与其它各图元间的精确几何或拓扑约束；以及在实时绘制时需对图元进行消除隐藏线的处理等。在上述系统中，图元数量一般比较大、图元间几何或拓扑关系分析的计算复杂度较高，且实时交互与绘制的要求高，因此设计新的快速圆形窗口裁剪算法显得尤为重要。
一个好的圆形窗口裁剪方法应该尽快、尽多地快速排除完全在圆外的线段；有效地保留完全在圆内的线段；对必须与圆求交的线段应快速求出交点。本文给出圆形窗口对线段的一种快速裁剪算法。该算法由基于适应性切线分隔的圆外线段快速测试方法、基于最小范围的圆内线段测试方法和基于点斜式查表的线段与窗口圆快速求交方法组成。基于适应性切线分隔的圆外线段快速测试方法利用待裁剪线段相对于圆的位置，选择相关切线进行外侧测试，以决定是否排除该线段；基于最小范围的圆内线段测试方法仅对位于窗口圆包围盒之内的线段实施包含性测试；基于点斜式查表的直线与圆的快速求交方法利用“从不同半径圆的坐标轴上离原点按半径比例位置的点出发的相同斜率的两条直线，与各自的圆的交点坐标也成比例”这样一个规律，将二元二次方程组求解改用直线与坐标轴的一次特殊求交及查表来实现。
1 基于切线分隔的圆外线段快速测试规则
1.1 圆外线段的定义及判定
定义1线段上所有点均在圆外的线段称为圆外线段。
因为不可能穷尽测试每一个点，所以不能直接按定义1进行圆外线段的判定。但由于垂足是圆心到线段所在直线的最近点，只要垂足在圆外就能保证线段为圆外线段。当垂足在线段的延长线上时，离垂足近的端点是线段上离圆心最近的点。因此，这两类圆外线段分别用下列2个条件来判定：
条件1 圆心到线段的距离大于圆的半径；
条件2 两端点都在圆外且圆心到线段的垂足在线段延长线上。
由于上述2个条件涉及的二次方程组求解操作过于耗时，其中第1类圆外线段的判定时间为6Tbas+5Tmul+1Tdiv，第 2类的判定时间为 18Tbas+11Tmul+3Tdiv（Tbas、Tmul、Tdiv分别为一次加减、乘法、除法的操作时间）。因此，作为好的裁剪算法必需寻找更快的判定方法。
实际上，圆外线段还可以这样定义：
定义2如果存在一条直线，它可将线段和圆分隔在它的两侧，则该线段为圆外线段。
判定圆是否在某直线一侧的问题实际上也是圆外线段判定问题。而如果某直线是圆的切线，则“圆在该直线的一侧”自然成立。剩下的只需判定待裁剪线段（的两个端点）是否在该切线的外侧。
因此，上述两个判别条件可以合并成1个：
条件如果两端点都在圆的某一切线的外侧，则该线段完全在圆外。
1.2 基于切线外侧测试的圆外线段排除规则
为了便于叙述，本文设线段两端点为P1(x1,y1),P2(x2,y2)，约定坐标原点在裁剪窗口圆的圆心。
1.2.1 基于水平或垂直切线外侧测试的规则
垂直或水平切线的外侧测试是最简单的操作，每边仅需进行2次坐标比较，且可排除的线段在所有待裁剪线段中占有较大比例。有下列圆外线段排除规则：
规则1如果x1>=R∧x2>=R，则可排除该线段，（图 1-a）。
规则2如果x1<=-R∧x2<=-R，则可排除该线段（图1-b）。
规则3如果y1>= R∧y2>= R，则可排除该线段（图1-c）。
规则4如果y1<=-R∧y2<=-R，则可排除该线段（图1-d）。
图1 基于切线分隔的圆外线段排除
1.2.2 基于斜率为±1的切线外侧测试的规则
斜率为±1的切线外侧排除测试也是较简单的操作，且可排除的情况也占有很大比例。设a=(21/2)*R，（此值对一个窗口圆只需计算一次，由所有待裁剪线段共享，故可视为常数），有下列圆外线段排除规则：
规则 5如果(x1-a)≥-y1∧(x2-a)≥-y2，则可排除该线段（图1-e）。
规则 6如果(x1+a)≤-y1∧(x2+a)≤-y2，则可排除该线段（图1-f）。
规则 7如果(x1+a)≤y1∧(x2+a)≤y2，则可排除该线段（图1-g）。
规则 8如果(x1-a)≥y1∧(x2-a)≥y2，则可排除该线段（图1-h）。
1.2.3 基于斜率为±0.5的切线外侧测试的规则
设b=(51/2)R，与“a”一样可视为窗口常数。针对斜率为±0.5的切线，可有如下规则：
规则 9如果(x1-b)≥-2y1∧(x2-b)≥-2y2，则可排除该线段（图1-i）。
规则 10如果(x1+b)≤-2y1∧(x2+b)≤-2y2，则可排除该线段（图1-j）。
规则 11如果 (x1+b)≤2y1∧(x2+b)≤2y2，则可排除该线段（图1-k）。
规则 12如果 (x1-b)≥2y1∧(x2-b)≥2y2，则可排除该线段（图1-l）。
1.2.4 基于斜率为±2的切线外侧测试的规则
常数b与上同，针对斜率为±2的切线，则可有如下规则：
规则 13如果 2x1≥-(y1-b)∧2x2≥-(y2-b)，则可排除该线段（图1-m）。
规则 14如果 2x1≤-(y1+b)∧2x2≤-(y2+b)，则可排除该线段（图1-n）。
规则 15如果 2x1≤(y1-b)∧2x2≤(y2-b)，则可排除该线段（图1-o）。
规则 16如果 2x1≥(y1+b)∧2x2≥(y2+b)，则可排除该线段（图1-p）。
1.2.5 基于与线段斜率平行的切线外侧测试的规则
对线段所在直线与圆不相交的圆外线段，还可用与之平行的两条切线来排除。设线段斜率为t，则与其平行的两条切线与Y轴交点的y坐标分别为±R*(1+t2)1/2；因此，如果线段与Y轴交点不在上述两点连线之内，则可排除。为了避免“无穷大”，分两种情况：
规则 17如果|x2-x1|<|y2-y1|，t=(x2-x1)/(y2-y1)，当 xinter=x1-t*y1满足(xinter2≥R2*(1+t2))时，则可排除该线段（图1-q）；
规则 18如果|x2-x1|≥|y2-y1|，t=(y2-y1)/(x2-x1)，当 yinter=y1-t*x1满足(yinter2≥R2*(1+t2))时，则可排除该线段；
1.2.6 基于线段近圆端点到圆心连线与圆的交点处切线外侧测试的规则
对于两端点都在圆外、且都在圆心到该线段垂线一侧的圆外线段，其所在直线可能与圆相交，也可能不相交。这一类圆外线段可如下判定：设始点为近圆端点，在始点到圆心连线与圆的交点处作切线，再过始点作平行于该切线的直线，如果终点在该直线外侧，必定也在与其平行的切线外侧，则线段在圆外。
始点到圆心连线的斜率为-(x1/y1)，过始点且平行于始点到圆心连线与圆的交点处切线的直线方程为(x-x1)x1+(y-y1)y1=0，终点在其外侧的判别式为 x1x2+y1y2-x12-y12≥0。始点和终点对调的情况类似。
规则 19如果则可排除该线段（图1-r）。
规则 20 如果 x1x2+y1y2≥x22+y22≥R2，则可排除该线段。
2 适应性排除与保留算法
上述规则中的每一条均有自己的覆盖范围，并需数量不等的操作。虽然按一定顺序使用这些规则能将所有圆外线段判定出来，但整体效率可能不是最高。高效的方法必须做到：
1）对有希望判定为圆外的线段，尽量选择针对性的、操作简单的少量规则来测试；
2）对可能是圆内的线段才进行包含性测试；
3）对与圆相交的线段，尽早肯定，避免做无效的排除性测试操作。
本文的适应性圆外线段排除与圆内线段保留算法按以下几点进行。
2.1 第1阶段：适应线段始点位置的垂直/水平切线排除测试
图2给出了使用圆的水平、垂直切线将线段定义范围各分成3个垂直“片”和水平“片”、交叉分成9个“区”的方式。规则1～4中的每条只有在 2个条件都满足情况下才能确定圆外线段，只要第1个条件不满足，就没有必要测试第2个条件。因此，本文在逐步判定始点所在的“片”位置的过程中，选择适应的规则来判定圆外线段，以便避免盲目测试造成的时间浪费。例如，一旦测试确定始点在“x1≥R片”，就选择规则1，如满足则判定线段为圆外线段并结束第1阶段测试；如不满足，也不再对是否满足x1≤-R进行测试，而是接下来对始点的y1坐标测试。如果始点在“y1≥R片”，就选择规则 3，如规则3满足则判定线段为圆外线段并结束第1阶段测试；如不满足，也结束第1阶段测试，因为此时已明确始点在3区而终点只可能在4、5、7或8区。
在上述适应线段始点位置的垂直/水平切线测试方法中，8种可成功判定一条圆外线段的情况中最少花费2次、最多6次、平均4.25次比较操作时间(4.25Tbas)；而9种可确定第1阶段无法排除待测线段的情况中则最少花费4次、最多6次，平均4.56次比较操作时间(4.56Tbas)。
2.2 第1阶段的后处理-分析余下的待测线段终点的区域位置
线段两端点相对于圆的位置是进一步在第2阶段中选择相适应规则的主要依据。对于不能在第一阶段被判定为圆外的线段而言，其始点所在区域已确定，终点的可能范围也已清楚。比如，当始点在1区时，终点只能位于5、6、8、9区之一。因此，稍加处理（平均时间为 2.57Tbas）即可获得线段终点的区域位置。
2.3 第2阶段：适应两端点位置组合的斜切线排
除测试和最小范围的圆内线段保留测试
第2阶段中，由于线段始、终点的区域位置已明确，可根据位置组合先选择规则5 ～8中适合的一条规则测试，必要时再选择规则 9 ～16中适合的一条规则测试。例如，两端点位置分别在1区和6区时，绝对不会满足规则6 ～8中任一条，因而只需使用规则5。按两端点位置组合分别有如下处理：
1）“两端点”为2-8或4-6，线段与圆相交，直接进入求交处理①（端点组合不计方向，如“2-8”包括从2到8和从8到2）；
2）“两端点”都在5区，圆面积占5区的78.53%，即始、终点在圆内的概率各为78.53%，线段是圆内线段的概率为61.67%。本文仅在这个“最小的范围”中进行圆内线段测试，有助于提高整体效率。设则可分下列情况处理：
（1）如果(d1≤R2)&(d2≤R2)，则线段为圆内，加以保留(图3-e)；
（2）如果((d1
（3）其它情况下：
① 如果两端点在不同象限，则线段与圆相交，进入求交处理① (图3-g)；
② 如果两端点在同一象限，则按象限选择使用相关规则：第一象限使用规则5；第2象限使用规则7；第3象限使用规则6；第4象限使用规则8。若满足，是圆外线段(图3-h)；如所用规则中两个条件均不满足，则当两端点在所在象限平分线（如第1象限的x=y）两侧时可确定线段与圆相交，进入求交处理①；在平分线同侧时、以及如两个条件中只有一个满足时，还可能是圆外线段，需进入第3阶段②继续测试；
3）只有1个端点在5区，由于在5区的端点在圆内的概率为78.53%，如果确定在圆内，则线段与圆相交，不必再进行圆外测试。因此，先对在5区的端点进行圆的包含性测试比较有利。设在5区的端点号为i，d= xi2+yi2，则可分别处理如下：
（1）如果d （2）如果d=R2，该端点在圆上，则按其所在象限号(Ⅰ、Ⅱ、Ⅲ、或Ⅳ)与另一端点所在区域的组合选择处理如下： ① “Ⅰ-3”、“Ⅱ-1”、“Ⅲ-7”、“Ⅳ-9”时，线段为圆外线段，可排除； ② “Ⅰ-1”、“Ⅰ-2”、“Ⅰ-6”、“Ⅰ-9”、“Ⅱ-2”、“Ⅱ-3”、“Ⅱ-4”、“Ⅱ-7”、“Ⅲ-1”、“Ⅲ-4”、“Ⅲ-8”、“Ⅲ-9”时，还可能是圆外线段，进入第3阶段3）； ③ 其他组合时，线段与圆相交，进入求交处理① (图3-m)； （3）如果 d >R2，该端点在圆外，则按其所在象限号与另一端点所在区域的组合选择处理如下： ① “Ⅰ-3”、“Ⅱ-1”、“Ⅲ-7”、“Ⅳ-9”时，线段为圆外线段，可排除(图3-j)； ② “Ⅰ-1”、“Ⅰ-2”、“Ⅰ-6”、“Ⅰ-9” 时，使用规则 5；“Ⅱ-2”、“Ⅱ-3”、“Ⅱ-4”、“Ⅱ-7”时，使用规则 7；“Ⅲ-1”、“Ⅲ-4”、“Ⅲ-8”、“Ⅲ-9”时，使用规则 6；“Ⅳ-3”、“Ⅳ-6”、“Ⅳ-7”、“Ⅳ-8”时，使用规则8；若满足，是圆外线段(图3-k)；如所用规则中两个条件均不满足，则当两端点在所在象限平分线（如第1象限的x=y）两侧时可确定线段与圆相交（图3-l），进入求交处理①；在平分线同侧时、以及如两个条件中只有一个满足，则还可能是圆外线段，进入第3阶段③； ③ 其他组合时，线段与圆相交，进入求交处理① (图3-m)； 4）“两端点”为 1-6、2-6、或 2-9，使用规则5；“两端点”为1-8、4-8、或4-9，使用规则6；“两端点”为4-2、4-3、或7-2，使用规则7；“两端点”为7-6、8-6、或8-3，使用规则8；按测试结果分别处理： （1）若两个条件都满足，则线段是圆外线段(图3-a)； （2）若两个条件都不满足，则线段与圆相交，进入求交处理① (图3-b)； （3）若两个条件中只有一个满足，线段还可能是圆外线段而需继续使用规则9 ～16中的一条测试。比如，当使用规则5时两个条件中只有一个满足时，如满足条件的端点在右边时，再使用规则9；当满足条件的端点在左边时，再使用规则13。然后再按测试结果分别处理如下： ① 若两个条件都满足，则线段是圆外线段(图3-c)； ② 若两个条件都不满足，则线段与圆相交，进入求交处理①(图3-d)； ③ 若两个条件中只有一个满足，线段还可能是圆外线段，需进入第3阶段①； 5）“两端点”为 1-9时，先使用规则 5，按测试结果分别处理： （1）若两个条件都满足，则线段是圆外线段； （2）若两个条件中只有一个满足，则按满足条件的端点在右边时再使用规则9，在左边时使用规则13，然后再按测试结果分别处理： ① 若两个条件都满足，则线段是圆外线段； ② 若两个条件都不满足，则线段与圆相交，进入求交处理①； ③ 若两个条件中只有一个满足，线段还可能是圆外线段，需进入第3阶段① （3）若两个条件都不满足，再使用规则6；按测试结果分别处理： ① 若两个条件都满足，则线段是圆外线段； ② 若两个条件都不满足，则线段与圆相交，进入求交处理①； ③ 若两个条件中只有一个满足，则按满足条件的端点在右边时再使用规则14，在左边时使用规则10，然后再按测试结果分别处理： a) 若两个条件都满足，则线段是圆外线段； b) 若两个条件都不满足，则线段与圆相交，进入求交处理①； c) 若两个条件中只有一个满足，线段还可能是圆外线段，进入第3阶段①。 6）“两端点”为3-7时，参照1-9方法类似地处理。 在本阶段处理中，不同的“两端点”组合对应的程序分支花费不同的时间。最少的是2-8和4-6组合，直接进入求交处理，花费时间为0；两端点中都不在 5区时，使用规则 5 ～8之一花费4Tbas，若还需使用相应的规则 9 ～16之一，则在利用已有计算结果的前提下，再花 4Tbas，平均6Tbas。5-5组合测试是否为圆内线段花费时间为4Tbas+4Tmul。按各种组合的线段数平均分布的假设（实际上5-5和5-X组合概率会较小），再加上按端点区域的程序分支时间(2Tbas)，每条线段在本阶段的平均处理时间为8.55Tbas+0.73Tmul。 图3 按两端点的区域位置选择测试规则 进入第3阶段处理的有3种情况：① 可按线段“斜率”选用规则17或18中的一条测试，如满足则为圆外线段；如不满足则进入求交处理；② 比较d1和d2可明确哪个是近圆端点，然后用规则19和20之一测试，满足即确定为圆外线段，不满足时再用规则17或18中的一条测试；③ 在5区的端点是近圆端点，先用规则19、20中对应的一条测试，不满足时再用规则17或18中的一条测试。最终还不能排除时，该线段一定与圆相交，进入求交处理②。 对于情况②，x12+y12或x22+y22已在第2阶段中求得，且均符合“≥R2”。将 d1和 d2比较及使用规则19或20之一共需时间3Tbas+2Tmul。对于情况③，作为近圆端点的在5区的点坐标已求得“x2+y2”，且符合“≥R2”。因此，按“情况①线段数=4*（情况②+情况③）线段数”的假设，第3阶段每条线段平均处理时间为 6.75Tbas+4Tmul+0.8Tdev。 图4中两个半径不同的圆在各自坐标系定义，两条线段的斜率相同，它们分别与两个圆的Y轴相交，且交点各自的y坐标与两圆半径成比例。只要其中一条线段与相关圆的交点坐标已知，就可按半径比例计算出另一线段与其相关圆的交点坐标。基于此例，可给出如下定理： 定理 从不同半径圆的对应坐标轴上离原点按半径成比例位置的点出发的斜率相同的两条直线，与各自的圆相交时的交点坐标也按半径成比例。 如果左边是一个半径固定的规范化圆，事先将其坐标轴上每一点引出各种不同斜率的直线与圆的交点坐标计算好并制备一张两维的线-圆交点表（针对保证直线与圆有交点的坐标轴点和斜率的组合），则对右边任意半径的圆和直线的求交处理，可通过将直线与其坐标轴的交点坐标比例变换到规范化圆的坐标系中，从线-圆交点表中查获直线与规范化圆的交点坐标，并逆比例变换回原来坐标系中来获得直线和圆的交点。这样，线段与圆的求交工作避免了求解二元二次方程组的工作，减少了计算时间。 令规范化圆的半径为 256，针对斜率从 0、1/256、2/256、…、255/256共256种，Y坐标轴上 y =0、1、2、…、362 共 363 个点是斜率小于等于1且与规范化圆相交的直线和Y轴交点坐标最大值），建立一张二维的线-圆交点表2；针对斜率为1，Y坐标轴上y =0、1、2、…、362共363个点，再建立一张一维的线-圆交点表1。两张表的表项内容一致，包含4个数据：这 4个数据分别为规范化圆和相应直线的2个交点的坐标。表1在斜率为1时使用ynor=0、1、2、…、362查询；表2使用ynor=0、1、2、…、362之一和与斜率为0、1/256、2/256、…、255/256对应的tnor=0、1、2、…、255之一来查询。 在字节编址条件下，设4个交点坐标均为2字节整数，则表1通过 Left_Shift3bits(ynor)即可形成访问 8字节表项内容的逻辑地址；而Left_Shift11bits(ynor)+Left_Shift3bits(tnor)则形成了表2的8字节表项的逻辑地址，因而查表速度很快。 将各种对应不同的点-斜率组合的直线与圆的交点事先计算并存入表中相应位置。这2张线-圆交点表即可供任意圆中线-圆求交时使用。 进入求交处理的线段肯定与圆有交点。其中，从“进入求交处理②”进入的线段已经过规则17或18的测试(但失败)。因此，(t,yinter)或(t,xinter)已求出；为了在求交时可直接使用上述数据，以便节省时间，在不改变实质的前提下，将规则17或18修改为： 圆外线段排除规则 17：如果|x2-x1|<|y2-y1|，计算 t=Left_Shift8bits(x2-x1)/(y2-y1)，当 d= Left_Shift8bits(x1)-t*y1满足 d2≥R2*(2562+t2)时，可排除； 圆外线段排除规则18：如果|x2-x1|≥|y2-y1|，计算 t=Left_Shift8bits(y2-y1)/(x2-x1)，当 d=Left_满足时，可排除； 修改后的规则使用时虽然比原来多做2次左移8位的操作，但从而可避免实数除法和乘法，全部用整数运算，其时间反而节省。 如果对从“进入求交处理①”进入的线段补求规则17或18中的(t,d)，则基于点斜式查表的线段与窗口圆的快速求交可由下列步骤接着完成： 1）求 tnor：tnor=|t|；（|t|即 t的绝对值）； 2）求 ynor：ynor=|d|/R；（整数除法）； 3）查表：如果tnor=256，使用ynor查表1；否则，使用 ynor和 tnor查表 2；获 xi1nor、yi1nor、xi2nor、yi2nor； 4）规范化逆变换：xi1=Right_Shift8bits 5）生成原坐标系坐标：由于利用了圆的对称性，正、负斜率及交点在坐标轴负半轴上等各情况都按图5中指定方式变换后，按线段所在直线斜率在[0-1]范围、及与Y轴正半轴有交点的情况查表，因此，所得直线与圆的交点必须按表1所示进行逆变换，将规范化逆变换所得坐标(xi,yi)还原到原坐标系中的坐标(xo,yo)。 图5 线段斜率及其和坐标轴交点位置的各种不同组合时使用“点斜式查表求交”前的变换 （除第1个外，实线为原线段，虚线为查表所用线段） 表1 生成原坐标系坐标的变换方法 有效性检查：如果|x2-x1|≥|y2-y1|，将Po1(xo1,yo1)、Po2(xo2,yo2)、P1、P2从左往右排序；如果|x2-x1|<|y2-y1|，将 Po1(xo1,yo1)、Po2(xo2,yo2)、P1、P2从下往上排序。中间两点之间的线段为裁剪结果。 上述查表求交处理平均需要时间12Tbas+4Tmul+1Tdiv；对从第2阶段“进入求交处理①”进入的线段补求(t,d )的时间可与第 3阶段处理时间抵消，故不计入。 算法效率的高低除了与算法中涉及的操作类型和次数有关外，还与待裁剪线段的随机分布位置有关。表2给出了本文方法对在中心位于坐标原点、边长为 1440的正方形范围内随机生成的100000条线段，用圆心位于坐标原点的5种半径的窗口圆进行裁剪处理的情况分类统计。 表2 100,000条随机线段在几个不同大小的圆形窗口时的处理分类实验数据 由于参考文献[7]用圆形窗口对抛物线裁剪，在对线段裁剪的参考文献中，参考文献[10]的方法比[8-9]的方法均好，因此本文方法仅和文献[10]的方法进行比较。先从算法上对比，再给出实验比较。算法上的对比有助于对实验数据差别的理解。 文献[10]在排除圆外线段方面采用三重编码，即3个阶段；本文与此类似，也分3个阶段。 1）第1阶段测试 在第 1阶段，文献[10]使用了Cohen-Sutherland编码算法，通过将两端点与窗口圆的正则外切正方形的4条边所在直线进行比较，计算待测线段2端点的2组第1类4位区域编码，然后将两组区域码进行“与”操作，若结果非全“零”，线段可排除；而本文在判定始点位置过程中按始点位置选择垂直、水平切线中适应的有关切线进行比较，一旦确认两端点同在某条切线外侧，即可排除线段。 文献[10]必须在对两端点区域编码生成并操作后才得到能否排除的结论，每一位编码的平均生成时间为2.5 Tbas，加上编码初始化及“与”操作，不管能否排除，每一条线段的平均处理时间为 12Tbas；而本文成功判定一条圆外线段时不必记录其位置，将失败判定时记录始点位置及继续判定终点位置时间考虑在内，按表2所出排除率计算，本文第1阶段对每条线段的平均处理时间是(9.24*34%+4.25*66%=)5.95Tbas。 2）第2阶段测试 第1阶段未能排除的线段必须进行第2阶段测试。在第 2阶段，文献[10] 使用旋转 45°的Cohen-Sutherland算法，通过将两端点与窗口圆的45°外切正方形的4条边所在直线进行比较，计算待测线段两端点的第 2类两组 4位区域编码，然后将两组区域码进行“与”操作，若结果非全“零”，线段可排除。不管能否排除，每一条线段的平均处理时间为 18Tbas；而本文方法与其不同点有： （1）根据两端点在水平、垂直切线所划分的区域码组合选择不同的操作；有些组合直接进入求交处理；需与±45°斜切线中比较的仅与其中合适的一条进行比较，然后作出“线段在圆外”、“线段与圆相交”、或“再测试”的结论； （2）“再测试”时根据两端测试结果进一步选用斜率为±2、±0.5切线中的相关的一条再测试，可排除更多的圆外线段（按表2数据，多排除全部线段中的5.78%）； （3）对两端点均在圆的包围盒之内时进行是否为圆内线段的判定； （4）对众多与圆相交的线段（按表 2，多达全部线段中的7.79%）及时判定，跳过第3阶段，直接进入求交处理。本文方法在第2端点的平均处理时间是8.55Tbas+0.73Tmul。 3）第3阶段测试 如果前2个阶段不能肯定线段为圆外线段，则必须进行第3阶段测试。按表2数据，本文方法下进入第 3阶段的线段数为全部线段中的9.24%，而文献[10]为22.85%。 在第3阶段，文献[10]通过计算广义距离编码及某些后续操作后判定线段是否在圆外。每一端点的广义距离编码通过两次乘除、两次加减法获得。对两端点都在圆心到线段的垂线所在直线同一侧的圆外线段共需判定时间为13Tbas+7Tmul；对两端点在圆心到线段的垂线所在直线两侧的圆外线段共需判定时间为18Tbas+8Tmul+1Tdiv；两类平均15.5Tbas+7.5Tmul+0.5Tdiv。 本文在第3阶段对每条线段的平均处理判定时间为6.75Tbas+4Tmul+0.8Tdev。 4）圆内线段的判定 如果线段两个端点都在圆内，则线段为圆内线段。文献[10]和本文都使用端点与圆心距离的平方与半径平方相比来确定端点是否在圆内。但是文献[10]在第3阶段才测试圆内线段，而本文在第2阶段就测试圆内线段，且仅当两端点都在5区时才测试，成功率高。因此，圆内线段被成功判定时，在两种方法下所花费的实际总时间差别很大。 5）线段和窗口圆的求交 文献[10]在第3阶段已计算广义距离等参数的基础上，再经 2次减法运算计算出方程At2+2Bt+C=0的3个系数，求解出参数t后再计算线段和窗口圆的交点坐标，合计花费17Tbas+6Tmul+1Tdiv+1Tsqrt，其中，Tsqtr为一次“开方”时间。 本文利用第 3阶段己计算“交点”和“斜率”的基础上，通过查表法计算两个交点的坐标，共需 15Tbas+4Tmul+1Tdiv。本文方法节省了 2次加减法、2次乘法和1次特别耗时的“开方”运算时间。 6）整体效率 由于2种方法均包括3个排除处理阶段和一个求交处理，每条线段的平均处理时间与各阶段处理的线段数、处理时间有关，即 其中，Ni为每阶段处理的线段数，Ti为每阶段花费的平均处理时间，T整体为每条线段平均处理时间。图6给出了两种方法前两个阶段用来排除圆外线段的切线集合。两种方法在第 1、4两个阶段处理的线段数完全相同，而表2中“规则9 ～16排除的圆外线段数”、“保留的圆内线段数”及 4类“进入求交①的线段数”在文献[11]中必须在第3阶段完成排除，“2-8、4-6组合（进入求交①）的线段数”跳过第2、3两个阶段，另外3项线段跳过第3阶段进入求交处理。每一阶段中本文方法均比文献[10]的方法明显快，特别是第2阶段和求交阶段，因而整体效率本文会明显高。 图6 文献[11]方法(左)和本文方法(右)分隔切线集合 表3给出了相应的2种方法在几个不同大小的圆形窗口下对100,000条随机线段的处理时间及比较，使用的计算机 CPU为 intel Pentium 43.00Ghz，内存1GB。随着窗口圆半径的增大，本文方法的效率比文献[10]越来越高，4.1节的实验分类数据和4.2节的分析给出了其中的原因。 表3 两种方法在几个不同大小的圆形窗口下对100,000条随机线段的处理时间对比实验数据 本文方法应用于建筑智能CAD[11-12]、图形识别与理解[13-14]等系统中。在上述系统中，由于涉及的图元数量多、图元间几何关系分析和图形语义理解算法较为复杂、计算量大，而系统对实时交互响应性能要求较高（如快速图元检索与定位、几何约束查询、通过鹰眼的交互式全图遍历等），采用包括AutoCAD等在内的现有图形软件提供的裁剪算法并不满足上述要求。应用结果表明，采用本文所提出的快速圆形窗口裁剪算法，效率成倍提高。 由于本算法中多层次处理思想的引入，算法实现时的简洁性、与底层图形软硬件接口的衔接需在进一步工作中加以优化。 本文为窗口圆定义了16条固定位置切线、6条随机切线及2条随机切线的平行线作为圆外线段的分隔线。根据端点位置选择适应的分隔切线，可快速确认圆外线段、尽早肯定与圆相交的线段，提高了排除性测试效率；基于最小范围的圆内线段测试提高了包含性测试效率；基于点斜式查表的线段与窗口圆快速求交方法避免了复杂的开方操作；由于尽可能地选择适应的、操作简单的、覆盖率高的测试方法，尽可能避免或减少了复杂耗时的操作和无效的计算，保证了本文算法具有较高的效率。 进一步的研究可包括圆形窗口对多边形的裁剪、椭圆窗口对直线段的裁剪或多边形的裁剪等。 [1] Liang Y D,Barsky B A. A new concept and method for line clipping [J]. ACM Transactions on Graphics,1984,3(1): 1-22. [2] Nicholl T M,Lee D T,Nicholl R A. An effiecient new algorithm for 2-D line clipping: its development and analysis [J]. SIGGRAPH,1987,21(4): 253-292. [3] Duvanenko V J,Robbins W E,Gyurcsik R S. Simple and efficient 2D and 3D span clipping algorithms [J].Computers and Graphics,1993,17(1): 39-54. [4] Devai F. An analysis technique and an algorithm for line clipping [C]//Proc of the IEEE Symposium on Information Visualization,1998: 157-165. [5] Wang H,Wu R,Cai S. A new algorithm for two-dimensional line clipping via geometric transformation [J]. Journal of Computer Science and Technology,1998,13(5): 410-416. [6] Lu G,Wu X,Peng Q. An efficient line clipping algorithm based on adaptive line rejection [J].Computers & Graphics,2002,3(26): 409-415. [7] Wu Q,Huang X,Han Y. A clipping algorithm for parabola segments against circular windows [J].Computers & Graphics,2006,30(4): 540-560. [8] 沈庆云,周来水,周儒荣. 一种圆形窗口裁剪的新方法[J]. 计算机辅助设计与图形学学报,1997,9(6):538-542. [9] 姚涵珍,宋 鹏,张国安. 圆形窗口裁剪算法的研究与实践[J]. 计算机辅助设计与图形学学报,1992,(4): 14-20. [10] 陆国栋,邢军伟,谭建荣. 基于多重编码技术的圆形窗口线裁剪算法[J]. 计算机辅助设计与图形学学报,2002,14(12): 1133-1137. [11] 雷 璐,苏 丰,蔡士杰. 建筑构件参数化建模语言 PCML的设计与应用[J]. 计算机辅助设计与图形学学报,2006,18(5): 687-693. [12] 杨华飞,杨若瑜,路 通,等. 计算机辅助建筑结构算量技术与软件[J]. 计算机辅助设计与图形学学报,2007,19(6): 748-756. [13] Lu T,Tai C L,Su F,et al. A new recognition model for electronic architectural drawings [J].Computer-Aided Design,2005,37(10): 1053-1069. [14] Lu T,Tai C L,Yang H,et al. A novel knowledge-based system for interpreting complex engineering drawings:theory,representation and implementation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(8): 1444-1457.
2.4 第3阶段：适应线段方向及位置的切线排除测试
3 基于点斜式查表的线段与窗口圆的快速求交方法
3.1 直线和圆的点斜式查表求交原理
3.2 线-圆交点表的组织
3.3 基于点斜式查表的线段与窗口圆的快速求交
4 裁剪算法分析和实验
4.1 线段随机分布实验
4.2 算法效率对比分析
4.3 算法效率对比实验
5 结 束 语
