裁剪是计算机图形学的基本问题之一, 也是CAD软件系统的一个重要图形编辑功能, 裁剪一般是指把一个封闭区域作为裁剪窗口, 去裁剪其他图形, 把其他图形中不在窗口内的部分裁剪掉, 只保留窗口内的部分. 裁剪功能除了在CAD软件中大量使用外, 在计算机动画、机器人运动学仿真、建筑设计、地理信息系统、平面绘画、影视特技图像处理以及模式识别等领域都有广泛应用.

目前, 裁剪算法的研究主要集中在多边形裁剪方面, 裁剪算法比较丰富, 有适合矩形裁剪窗口的逐边裁剪法、Liang-Barsky算法、中点分割算法, 适合凸多边形裁剪窗口的线裁剪Cyrus-Beck 算法、Sutherland-Hodgman算法、外接矩形判别法和分区判断直接裁剪法以及适合任意多边形裁剪窗口的Weiler-Atherton双边裁剪算法等^[1-13].

圆裁剪也是一个重要的图形裁剪功能, 具有广泛的应用, 圆裁剪有两种类型, 一是圆做裁剪窗口对各种图形进行裁剪, 例如圆窗口对直线段的裁剪^[14-18], 二是多边形或者其他图形作为裁剪窗口对圆进行裁剪, 裁剪后只保留窗口内的圆弧部分. 在第二种圆裁剪类型中, 矩形窗口的圆裁剪在视窗显示时应用较多, 裁剪算法有逐边裁剪法、区域编码法及投影法等^[19-22]. 除了矩形窗口的圆裁剪外, 在实际应用中, 也存在任意多边形做裁剪窗口的圆裁剪情况, 因此, 研究任意多边形窗口的圆裁剪也具有重要的实用价值. 关于多边形做裁剪窗口的圆裁剪, 文献[23]提出了一种方法: 首先, 计算多边形每条边与圆的交点, 再对交点在圆周方向排序, 然后再进一步判断相邻交点间的圆弧是否在窗口内, 该方法为多边形窗口的圆裁剪提供了一条有效的途径, 但是, 文献中的算法需要开平方计算交点和反三角计算检测圆弧的可见性, 效率低且耗资源; 文献[24]将圆裁剪分成相交性检测求交点、点在多边形内外判断、交点排序以及可见性检测等5个步骤, 在圆与多边形相交性检测时利用投影和射线法相结合, 降低了运算的耗费, 对交点排序和圆弧可见性检测方法也做了相应改进, 算法的效率相比文献[23]有所提高. 文献[25]提出了和文献[24]类似的方法, 利用X-扫描线法分析圆与多边形的位置关系, 再利用多边形顶点与圆的相对位置对交点排序. 文献中提出的方法, 除了细节不同外, 算法的整体思路基本上是相同的: 均是先求出多边形与圆的交点, 再对交点在圆矢量方向上排序, 然后, 判断相邻两个交点之间的圆弧段是否在多边形裁剪窗口内(即可见性检测), 从而实现对圆的裁剪. 在上述思路中, 除了计算交点外, 交点排序和相邻交点之间圆弧的可见性检测也是非常重要的环节, 文献采用的交点排序方法有三三排序法^[24]、比较顶点和圆心距离的排序法^[25]等, 但是, 这些排序方法只适用于多边形裁剪窗口只有外环的情况, 当多边形裁剪窗口除了外环外还含有一个或多个内环多边形时, 文献中的交点排序方法就会出错, 则后续的圆弧可见性检测方法也会失效, 因此, 文献中的方法不适合有内环的任意多边形做裁剪窗口的圆裁剪情况.

笔者在进行相关课题研究时, 对任意多边形裁剪窗口的圆裁剪问题也进行了探讨. 通过分析发现, 当多边形裁剪窗口和圆相交时, 利用交点相对裁剪窗口的进出点特性, 即可判断圆弧段的可见性, 不需要再对圆弧的可见性单独进行检测, 而通过比较圆与多边形边所在直线相交的参数值大小就能够直接确定交点的进出点特性信息, 也不再需要其他额外的计算判断.

为此, 本文提出了一种基于交点参数值分析的任意多边形裁剪窗口的圆裁剪算法, 与文献中的方法相比, 本算法只需对交点参数值进行比较, 即可判断出裁剪窗口内的圆弧部分, 判断步骤简洁明了, 效率要明显高于文献中的方法, 适用于包括含内环多边形在内的任意多边形做裁剪窗口对圆进行裁剪的情况.

1 基于进出点特性的多边形窗口对圆裁剪

在任意多边形裁剪窗口对多边形的裁剪算法中, 基于交点进出点特性的Weiler- Atherton双边裁剪算法是一种非常有效的解决方案, 该方法通过将两个多边形设置为有向多边形, 当两个多边形有交点时, 沿着多边形的方向, 通过判断交点是进入裁剪窗口的进点还是离开裁剪窗口的出点, 并保留进点和出点之间的多边形, 实现裁剪. 该方法利用交点的进出点特性获得裁剪窗口内的部分, 对多边形裁剪窗口的圆裁剪具有借鉴意义.

图1所示为一个多边形裁剪窗口对圆裁剪, 其中, 多边形为 $ {P_0}{P_1}{P_2}{P_3}{P_4}{P_5}{P_6}{P_7}{P_8} $ , 顺时针走向, $ O $ 是被裁剪圆, 逆时针走向. 圆 $ O $ 与多边形相交的交点为: $ {I_0} $ 、 $ {I_1} $ 、 $ {I_2} $ 、 $ {I_3} $ 、 $ {I_4} $ 和 $ {I_5} $ . 根据交点的进出点分析方法, 沿着圆的走向, 进入多边形裁剪窗口内的交点称为进点, 离开多边形裁剪窗口内的交点称为出点, 由于圆本身是封闭的, 裁剪窗口的内部区域也是连通的, 所以, 进点和出点成对出现, 数量相同. 沿着圆的走向, 从进点到出点之间的圆弧位于多边形裁剪窗口内部, 在裁剪时应予以保留, 从出点到进点之间的圆弧在多边形裁剪窗口的外部, 应裁剪掉. 因此, 在求出多边形裁剪窗口和圆的交点后, 首先, 沿着圆的走向对交点进行排序, 然后, 对排序后的交点, 进行进点 $\Rightarrow $ 出点的组合, 这样, 就可以获得多边形裁剪窗口内部的圆弧. 例如, 图1中, 将多边形裁剪窗口和圆的交点沿着圆的逆时针走向排序, 顺序为: $ {I_0} $ (进点) $ \Rightarrow $ $ {I_5} $ (出点) $ \Rightarrow $ $ {I_4} $ (进点) $ \Rightarrow $ $ {I_3} $ (出点) $ \Rightarrow $ $ {I_2} $ (进点) $ \Rightarrow $ $ {I_1} $ (出点), 则进点 $ \Rightarrow $ 出点的组合为: $ {I_0} \Rightarrow {I_5} $ 、 $ {I_4} \Rightarrow {I_3} $ 和 $ {I_2} \Rightarrow {I_1} $ , 对应这些进点到出点之间的圆弧为裁剪后需保留的部分.

图1中的多边形裁剪窗口是只有一个外环的一般多边形的情况. 下面对形状更为复杂的含内环的任意多边形裁剪窗口的圆裁剪情况进行分析.

图2为一个含内环的多边形对圆进行裁剪, 多边形的外环顶点依次为 $ {P_0}{P_1}{P_2}{P_3}{P_4}{P_5}{P_6} $ , 外环按顺时针走向, 内环顶点依次为 $ {Q_0}{Q_1}{Q_2}{Q_3}{Q_4} $ , 内环按逆时针走向, $ O $ 是被裁剪圆, 逆时针走向. 圆 $ O $ 分别与多边形裁剪窗口的内外环相交, 圆与外环的交点以及交点的进出点特性为: $ {I_0} $ (进点)、 $ {I_3} $ (出点)、 $ {I_2} $ (进点)和 $ {I_1} $ (出点), 圆与内环的交点以及交点的进出点特性为: $ {I_4} $ (出点)和 $ {I_5} $ (进点). 沿着圆的逆时针走向, 对所有交点进行排序, 顺序为: $ {I_0} $ (进点) $ \Rightarrow $ $ {I_4} $ (出点) $ \Rightarrow $ $ {I_5} $ (进点) $ \Rightarrow $ $ {I_3} $ (出点) $ \Rightarrow $ $ {I_2} $ (进点) $ \Rightarrow $ $ {I_1} $ (出点). 则排序后的交点进行进点 $ \Rightarrow $ 出点组合为: $ {I_0} $ $ \Rightarrow $ $ {I_4} $ 、 $ {I_5} $ $ \Rightarrow $ $ {I_3} $ 和 $ {I_2} $ $ \Rightarrow $ $ {I_1} $ , 对应这些进点到出点之间的圆弧也为裁剪后需保留的部分.

因此, 利用交点的进出点特性也可以实现对含内环多边形在内的任意多边形裁剪窗口的圆裁剪.

本裁剪算法的步骤归纳如下:

第1步. 依次判断多边形外环和内环的每条边与圆是否相交, 如相交, 则计算交点;

第2步. 判断交点是进点还是出点, 并在交点信息中记录其进出点特性;

第3步. 沿圆的走向将交点进行排序;

第4步. 根据交点的进出点特性, 将排序后的交点进行进点 $ \Rightarrow $ 出点组合, 保留进点 $ \Rightarrow $ 出点之间对应的圆弧.

2 交点进出点特性和直线参数的关系

在上述的裁剪算法中, 判断交点的进出点特性是整个算法的关键. 对于多边形裁剪窗口对多边形的裁剪, 可以通过被裁剪边的两个顶点和裁剪边的相对位置关系来判断交点是进点还是出点, 但是对于圆裁剪, 由于圆本身没有顶点, 所以, 不能再借鉴多边形的进出点判断法来分析圆与多边形交点的进出点特性, 因此, 还需要寻找新的方法来判断交点的进出点信息.

设线段 $ {P_0}{P_1} $ 是多边形裁剪窗口的一条边, 两个端点分别为 $ {P_0}\left( {{x_0}, {y_0}} \right) $ 和 $ {P_1}\left( {{x_1}, {y_1}} \right) $ , 边的方向是 $ {P_0} $ 指向 $ {P_{\text{1}}} $ , 则该边所在直线的参数方程表示为:

$ \left\{ {\begin{array}{*{20}{c}} {x = (1 - t){x_0} + t{x_1}} \\ {y = (1 - t){y_0} + t{y_1}} \end{array}} \right. $

(1)

如图3所示, 参数将边所在直线划分为3个区域: $ ( - \infty , 0) $ 、 $ [0, 1] $ 和 $ (1, + \infty ) $ , 其中, 当参数值 $ t \in [0, 1] $ 时, 对应直线上的点在 $ {P_0} $ 和 $ {P_1} $ 之间的线段上, 即在多边形的边上, 而且参数值从 $ {P_0} $ 到 $ {P_1} $ 逐渐增大; 当 $ t \notin [0, 1] $ 时, 对应直线上点不在 $ {P_0} $ 和 $ {P_1} $ 之间的线段上, 而是在该线段两侧的延长线上; 当 $ t < 0 $ 时, 点在 $ {P_1} $ 指向 $ {P_0} $ 的线段延长线上, $ t $ 值越来越小, 当 $ t > 1 $ 时, 点在 $ {P_0} $ 指向 $ {P_1} $ 的线段延长线上, $ t $ 值越来越大, 也即直线上的点在沿着 $ {P_0} $ 指向 $ {P_1} $ 的方向上, 对应的参数值 $ t $ 越来越大, 反之, 参数值 $ t $ 越来越小.

设多边形为有向多边形, 其中, 外环为顺时针走向, 内环为逆时针走向, 则多边形内部所在区域具有这样的特点: 不管是外环边还是内环边, 沿着边的走向前进, 即沿着 $ {P_0} $ 点指向 $ {P_1} $ 点的方向前进, 这时, 边的右侧均为多边形的内侧区域. 即使多边形的各边具有不同的倾斜方向, 该特点仍然存在, 如图4所示.

图5所示是多边形的一个边所在直线与圆相交的情况, 圆的走向是逆时针, 边直线的方向是 $ {P_0} $ 点指向 $ {P_1} $ 点, 则沿着直线走向的右侧是多边形的内侧区域. 若圆与直线 $ {P_0}{P_1} $ 相交, 交点记为 $ {I_0} $ 和 $ {I_1} $ , 则从图中可以看到, 圆在交点 $ {I_0} $ 处进入多边形内侧区域, 即 $ {I_0} $ 为进点, 在交点 $ {I_1} $ 处离开多边形内侧区域, 即 $ {I_1} $ 为出点, 设交点 $ {I_0} $ 和 $ {I_1} $ 在直线的参数方程式(1)中对应的参数值分别为 $ {t_0} $ 和 $ {t_1} $ , 这时, 参数值 $ {t_0} $ 和 $ {t_1} $ 的大小关系是:

$ {t_0} < {t_1} $

(2)

式(2)也是图4中有向边所在直线第一种倾斜情况下, 和圆相交时交点的进出点特性和交点在直线上参数值大小的对应关系.

图6是图4中有向边所在直线的另外3种倾斜方向下和逆时针走向圆相交的情况, 直线的方向是 $ {P_0} $ 点指向 $ {P_1} $ 点, $ {I_0} $ 和 $ {I_1} $ 是两个交点, 其中, $ {I_0} $ 为进点, $ {I_1} $ 为出点, 从图6也可以得出和图5相同的结论: 沿着边所在直线的走向, 如果右侧是多边形裁剪窗口的内侧区域, 圆沿逆时针走向, 圆和直线相交的两个交点分别是进点和出点, 则进点在直线上的参数值小于出点在直线上的参数值, 即进点和出点在直线上的参数值具有和式(2)相同的大小关系.

因此, 圆和多边形裁剪窗口相交时交点的进出点特性, 通过判断交点在对应边所在直线的参数值大小即可确定下来, 这样, 就利用第1节提出的基于交点进出点特性的多边形窗口的圆裁剪算法, 即可实现对圆的裁剪.

3 圆与边所在直线的交点计算及处理

上述的圆与多边形边相交是指圆与多边形边所在直线相交, 这时, 交点可能在多边形的边上, 也可能在边的延长线上. 只有落在多边形的实际边上而不是在其延长线上的交点才用于裁剪, 这个交点称为实交点, 在边的延长线的交点称为虚交点. 当边与圆没有实交点时, 圆和该边不存在裁剪, 不必计算. 只有存在实交点时, 才计算交点的参数值, 并比较大小, 判断该实交点是进点还是出点.

判断直线与圆是否存在交点的方法如下:

设圆的半径是 $ R $ , 圆心为 $ {P_c}({x_c}, {y_c}) $ , 逆时针方向, 圆方程为:

$ {(x - {x_c})^2} + {(y - {y_c})^2} = {R^2} $

(3)

将式(1)中的直线参数化表示代入式(3)中, 建立参数 $ t $ 的一元二次方程. 该方程的解为:

$ t = \frac{{B \pm \sqrt {{B^2} - 4AC} }}{{2A}} $

(4)

其中,

$ A = {({x_1} - {x_0})^2} + {({y_1} - {y_0})^2} $

$ B = 2[({x_1} - {x_0})({x_c} - {x_0})+ ({y_1} - {y_0})({y_c} - {y_0})] $

$ C = {({x_c} - {x_0})^2} + {({y_c} - {y_0})^2} - {R^2} $

令 $ \Delta = {B^2} - 4AC $ , 则 $ t = \dfrac{{B \pm \sqrt \Delta }}{{{\text{2}}A}} $ .

当 $ \Delta < 0 $ 时, 方程无解, 即直线和圆没有交点.

当 $ \Delta = 0 $ 时, 方程只有一个解, 即直线和圆相切, 此时也不必考虑裁剪.

当 $ \Delta > 0 $ 时, 直线与圆有两个交点, 这时需进一步判断是否存在实交点, 当有实交点时, 计算方程的两个解 $ {t_1} $ 和 $ {t_2} $ :

$ {t_1} = \frac{{B - \sqrt \Delta }}{{{\text{2}}A}} \text{, } {t_2} = \frac{{B + \sqrt \Delta }}{{{\text{2}}A}} $

(5)

由于 $ {t_1} < {t_2} $ , 所以, $ {t_1} $ 对应的交点为圆在直线上的进点, $ {t_2} $ 对应的交点为圆在直线上的出点.

当 $0 \leqslant {t_1},\; {t_2} \leqslant 1$ 时, 则 $ {t_1} $ 和 $ {t_2} $ 对应的两个交点均为实交点, 将 $ {t_1} $ 和 $ {t_2} $ 代入式(1), 即得交点值, 将两个交点插入交点序列中, 并标识每个交点的进出点特性.

当 $ {t_1} $ 和 $ {t_2} $ 中仅有一个值在 $ [0, 1] $ 区间时, 则在 $ [0, 1] $ 区间的 $ t $ 值对应的交点为实交点, 将该交点插入交点序列中, 并标识其进出点特性.

4 圆周方向交点排序

所有的实交点沿着圆周方向排序是实现裁剪的重要一步. 文献中的交点排序方法是比较每个点在圆的逆时针方向对应的圆弧角大小, 需要进行反三角运算, 比较耗性能. 由于所有的交点都在圆上, 所以, 本文采用比较交点与 $ (R, 0) $ 或者 $ ( - R, 0) $ 距离的方法进行排序, 如图7所示.

当交点的坐标值 $ y \geqslant 0 $ (即交点在圆上0°到180°之间)时, 按交点到 $ (R, 0) $ 的距离大小排序:

$ {D^2} = {(x - R)^2} + {y^2} $

(6-1)

当交点坐标值 $ y < 0 $ (即交点在圆上180°到360°之间)时, 按交点到圆上 $ ( - R, 0) $ 的距离大小排序:

$ {D^2} = {(x + R)^2} + {y^2} $

(6-2)

然后, 将两组交点序列合在一起, 获得所有交点的排序.

5 算法实例及与文献算法的分析比较

为了验证本文提出的基于交点参数的多边形裁剪窗口的圆裁剪方法, 笔者在Visual C++平台下进行了图形编程, 在生成直线、圆、圆弧以及各种类型多边形的基础上, 实现了本文第1节提出的基于交点进出点特性的多边形窗口的圆裁剪算法, 在算法中, 利用第3节的方法计算多边形边与圆的交点, 交点的进出点特性则根据第2节提出的交点所在边直线的参数判断, 并按第4节的方法在圆周方向对交点进行排序.

图8和图9是利用本算法实现的裁剪效果实列, 其中, 图8是仅有外环多边形裁剪窗口对圆的裁剪, 其中, 图8(a)是裁剪前的多边形裁剪窗口和被裁剪的圆, 图8(b)是裁剪后效果. 图9是带内环的多边形裁剪窗口对圆的裁剪, 其中, 图9(a)是裁剪前的多边形裁剪窗口和被裁剪的圆, 图9(b)是裁剪后效果. 图8和图9中的多边形均通过随机交互方式构造生成, 无任何特殊设定, 裁剪结果证实本文提出的算法是切实可行的.

本实验中采用的直线、多边形、圆以及圆弧这些图形的生成方法均为笔者自己开发的算法实现, 没有借助Visual C++平台或者其他如OpenGL图形库现有的绘图函数生成, 为了说明本文算法的效率和性能, 下面列出本文方法和文献方法在步骤上的区别比较.

表1是本文算法与文献算法的比较. 其中, 在判断和计算裁剪边界直线和圆的交点时, 本文算法的时间复杂度是 ${\rm O}(n)$ , 其中 $ n $ 为多边形的边的数量, 空间复杂度为 ${\rm O}(k)$ , 其中 $ k $ 为实交点的数量, 对交点排序时的复杂度为 ${\rm O}(k)$ , 空间复杂度为 ${\rm O}(1)$ , 也即本文和文献在共有的算法步骤中的时间复杂度和空间复杂度是相同的. 但是, 除了共有的步骤外, 文献算法还需要其他步骤才能实现, 而本文的算法, 仅根据交点在多边形边所在直线的参数值大小, 判断出交点的进出点特性, 即可进行裁剪, 不需要太多步骤, 因此效率更高. 另外, 文献也没有考虑多边形裁剪窗口带内环的情况, 本文算法不仅适用于仅有外环的一般多边形裁剪窗口, 也适用于带内环的任意多边形裁剪窗口的圆裁剪, 因此, 算法更具有通用性.

6 结论

本文提出了一种基于交点参数信息分析的任意多边形裁剪窗口的圆裁剪算法, 在计算多边形边与圆交点的同时, 通过交点在边所在直线的参数信息, 即可识别出交点的进出点特性, 从而实现对圆的裁剪. 与文献中的方法相比较, 本算法步骤较少, 编程实例结果也验证了本文算法的可行性. 本文的算法不仅对仅有外环的一般多边形裁剪窗口的圆裁剪适用, 也适用于带内环的任意多边形裁剪窗口的圆裁剪.