1 引言

在日常生活中, 随着计算机动画、人机交互以及虚拟现实等技术的不断融入, 人们对计算机图形学技术提出了更高要求. 计算机图形学研究的内容十分广泛, 如基本图形生成、裁剪、三维几何造型、真实感图形的显示、交互技术等等. 裁剪作为计算机图形学的基础操作, 也是图像处理、模式识别等问题的基础.

在实际应用中, 裁剪窗口可能是各种形状, 比较常用的裁剪窗口为矩形或者多边形. 目前, 对裁剪算法的研究工作主要包括: 矩形窗口的线裁剪^[1,2]、圆裁剪^[3]和多边形裁剪^[4], 多边形窗口的线裁剪^[5,6]、圆的裁剪^[7,8]和多边形裁剪^[9]等等. 这些研究为后续的算法研究奠定的一定的基础. 但是, 由于多边形窗口的凹凸性和无规则性, 与矩形窗口内图形裁剪相比, 多边形窗口内图形裁剪更为复杂. 在实际应用中经常会遇到关于任意多边形窗口的圆裁剪问题, 如两个或多个实体间的碰撞、检测等等. 因此, 研究多边形窗口内圆的裁剪问题具有重要的意义.

为了提升已有的矢量圆裁剪算法效率和减少算法对内存占用率等问题, 一种具有线性复杂度的任意多边形窗口的矢量圆裁剪算法被提出^[7], 该算法结合投影和射线法的线性几何思想, 借助向量叉积和向量共线基本定理, 降低了裁剪过程的运算量, 提高了裁剪效率, 具有较高的鲁棒性和通用性.

文献[8]中提出了一种任意多边形窗口的圆裁剪算法, 该算法按照逆时针方向依次求出圆与多边形各条边之间的交点并排序, 然后借助“中点检测法”判定相邻两点是线还是弧的连接, 最终完成圆的裁剪. 该算法在效率和稳定性上都取得了比较理想的结果. 但该算法只考虑了圆和多边形窗口相交及圆在多边形窗口内的情况, 并未考虑圆与多边形窗口相离以及多边性窗口在圆内的情况. 针对该问题, 如果更加全面的讨论多边形窗口和圆的位置关系的情况下完成圆的裁剪是十分有必要的.

本文提出了一种更加有效全面的多边形窗口的圆裁剪算法. 在考虑任意多边形窗口与圆的不同位置关系的情况下, 能够全面的分析多边形窗口各顶点、各边与圆之间的关系, 并对其进行了不同的裁剪. 最后仿真例子验证该方法的有效性和全面性.

2 直线段和圆的位置关系

基于任意多边形窗口, 圆的裁剪关键要解决以下两个问题:

(1) 圆与多边形窗口每条直线段是否有相交; 如果相交, 如何求交点;

(2) 圆和多边形的位置关系如何确定.

已知被裁剪圆的方程为:

${(x - {x_0})^2} + {(y - {y_0})^2} = {r^2}$

(1)

其中, 圆心坐标O为(x₀, y₀), 半径为r.

给定直线段P₁P₂, 端点坐标分别为P₁(x₁, y₁), P₂(x₂, y₂), 则按照逆时针方向总可得到其参数方程表示. 不失一般性, 假设有向直线段P₁P₂, 为逆时针方向, 则其参数方程表示为:

$\left\{ {\begin{array}{*{20}{c}}{x = {x_1} + ({x_2} - {x_1})t}\\{y = {y_1} + ({y_2} - {y_1})t}\end{array}} \right.\quad \quad t \in [0,1]$

(2)

按逆时针方向, 考虑直线段和圆的位置关系, 有5种可能的情况(如图1).

确定直线段和圆的位置关系:

将(2)代入(1), 化简整理可得:

$a{t^2} + bt + c = 0$

(3)

其中,

$a = {({x_2} - {x_1})^2} + {({y_2} - {y_1})^2}$

$b = 2[({x_2} - {x_1})({x_1} - {x_0}) + ({y_2} - {y_1})({y_1} - {y_0})]$

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

令 $ \Delta = {b^2} - 4ac$ ,

若 $\Delta < 0$ , 说明方程(3)没有解;

若 $\Delta = 0$ , 说明方程(3)有且仅有一个解: ${t_1} = {t_2} = - \displaystyle\frac{b}{{2a}}$ ;

若 $\Delta > 0$ , 说明方程(3)有两个解, 分别为: ${t_1} = \displaystyle\frac{{ - b + \sqrt \Delta }}{{2a}}$ , ${t_2} = \displaystyle\frac{{ - b - \sqrt \Delta }}{{2a}}$ .

综上, 如果 $\Delta \geqslant 0$ , 说明方程(3)有解, 则需要判断 ${t_i}(i = 1,2)$ 的取值范围来进一步确定直线段和圆的交点个数. 如果 ${t_i} \in [0,1]$ , 则其对应的点(代入方程(3)可得对应的点的坐标)即为直线段和圆的交点, 否则不是直线段和圆的交点.

3 基于多边形窗口的圆的裁剪

给定任意多边形窗口 ${P_1}{P_2} \cdots {P_m}$ , ${P_i}({x_i},{y_i})(i = 1,2, \cdots\!,$ m)为多边形窗口的顶点.

考虑任意多边形窗口和被裁剪圆的位置关系, 有四种可能的情况(如图2):

3.1 $x{\rm{ - }}$ 扫描线算法判断多边形窗口和圆的位置关系

借助 $x{\rm{ - }}$ 扫描线算法填充多边形的基本思想, 这里研究如何利用 $x{\rm{ - }}$ 扫描线算法判断多边形窗口与圆的位置关系, 其基本思想为:

从多边形各个顶点 ${P_i}({x_i},{y_i})(i = 1,2, \cdots ,m)$ 出发, 依次做平行于 $x$ 轴的扫描线（方向向右）, 并计算每条扫描线与圆的交点个数情况 ${n_i},\;{n_i} \in \{ 0,1,2\} $ .

考虑以下情况:

如果 $\forall \;{n_i} = 0$ 或 $\forall \;{n_i} = 2$ , 则说明圆在多边形窗口外, 如图2(a);

如果 ${n_i}$ 的取值即有0也有2, 则说明圆在多边形窗口内, 如图2(b);

如果 $\forall \;{n_i} = 1$ , 则说明多边形窗口在圆内, 如图2(c);

如果 ${n_i}$ 的取值中0, 1, 2都有, 则说明圆在多边形窗口内, 如图2(d).

备注: 借助于 $x - $ 扫描线算法, 不仅能够确定多边形窗口和圆的位置关系, 而且能够准确的区分图2所示的不同情况, 对多边形窗口和圆的位置关系给出更加准确的判定. $x - $ 扫描线算法避免了由计算确定位置关系的大量计算, 而且解决了由计算不能区分图2中(a), (b), (c)中多边形和圆位置关系判定的问题.

3.2 基于多边形窗口的圆的裁剪.

根据3.1节基于 $x - $ 扫描线算法对多边形窗口和圆的位置关系的判断, 接下来讨论确定圆关于多边形窗口的裁剪的问题. 针对以上四种不同情况进行不同的讨论:

(1) $\forall \;{n_i} = 0$ 或 $\forall \;{n_i} = 2$

在这种情况, 被裁剪圆要么落在多边形窗口外(如图2(a)), 则整个圆被裁剪;

(2) ${n_i}$ 的取值即有0也有2

在这种情况, 被裁剪圆落在多边形窗口内(如图2(b)), 则绘制整个圆;

(3) $ \forall \;{n_i} = 1$

在这种情况下, 多边形窗口在被裁剪圆内(如图2(c)), 则绘制整个多边形;

(4) ${n_i}$ 的取值中0, 1, 2都有

在这种情况下, 则说明多边形窗口与圆相交(如图2(d)).

下面针对情况(4), 讨论圆弧是否被裁剪:

为了方便, 首先引入输入顶点数组 ${{P}}$ (多边形顶点)和输出顶点数组 ${{Q}}$ (圆与多边形窗口交点), 输入顶点数组 ${{P}}$ 中以逆时针方向列出, 即首先定义多边形窗口顶点的首点, 然后以逆时针方向将多边形顶点依次存入数组 ${{P}}$ .

按照2.1节给出的直线段和圆的交点的求法, 依次沿逆时针方向分别求多边形窗口各个边与圆的交点, 并将其按照顺序存入数组 ${{Q}}$ 中, 其排序具体方法为:

取出多边形窗口的顶点数组 ${{P}}$ 中的首边 ${P_1}{P_2}$ , 按照逆时针方向依次求出多边形窗口各个边 ${P_i}{P_{i + 1}}$ 与圆的交点参数序列, 记为: ${t_1}$ , ${t_2},\cdots,$ ${t_k}$ ( $1 \leqslant k \leqslant 2m$ ), 并将其对应的点 ${Q_1}$ , ${Q_2},\cdots,$ ${Q_k}$ 依次存入数组 ${{Q}}$ 中, 记 ${Q_{k + 1}} = {Q_1}$ .

同时, 判断多边形窗口的顶点 ${P_i}$ 是否在圆内, 如果在圆内, 将其按照逆时针方向存入数组 ${{Q}}$ 中. 如果 ${P_{i - 1}}{P_i}$ 与圆有交点 ${Q_j}$ , 且 ${P_i}$ 点在圆内, 则将点 ${P_i}$ 存入数组 ${{Q}}$ 中, 并将其存放在 ${Q_j}$ 后面, 记为 ${Q_{j + 1}}$ .

下面判断两个相邻交点之间是圆弧连接还是线段连接:

① 如果 ${Q_i}$ , ${Q_{i + 1}}$ 为多边形窗口中同一条直线段与圆的交点, 则弧 ${Q_i}{Q_j}$ 被裁剪, 绘制直线段 ${Q_i}{Q_j}$ ;

② 如果 ${Q_i}$ , ${Q_{i + 1}}$ 为多边形窗口中不同直线段与圆的交点, 则弧 ${Q_i}{Q_{i + 1}}$ 被绘制;

③ 如果 ${Q_i}$ , ${Q_{i + 1}}$ 中, 一个点为多边形窗口中一条边与圆的交点, 另一点为圆内的多边形顶点, 则绘制直线段 ${Q_i}{Q_{i + {\rm{1}}}}$ .

4 算法实现与实例仿真 4.1 多边形窗口和圆的位置关系

按照上述原理, 给出本文方法的基本框架, 如图3所示.

4.2 实例仿真

根据本文提出的任意多边形窗口的圆裁剪算法的有效性和全面性, 讨论了图2给出的四种多边形窗口和圆的位置关系的情况下圆的裁剪.

图4验证了当多边形窗口和圆分离时, 根据本文提出算法, 得到的裁剪结果为: 圆被裁减掉.

图5验证了当圆在多边形窗口内时, 根据本文提出算法, 得到的裁剪结果为: 绘制整个圆.

图6验证了当多边形窗口在圆内时, 根据本文提出算法, 得到的裁剪结果为: 绘制整个多边形.

图7验证了当多边形窗口及圆相交时, 根据本文提出算法, 得到的裁剪结果为: 绘制圆在多边形窗口内部分及新生成的圆弧.

对于任意多边形窗口和圆的位置关系, 图4-7中的结果验证了本文提出方法的全面性和有效性.

相比于文献[8]的算法, 本文提出的算法对于圆在多边形窗口外的情况进行了完善, 增加了多边形窗口和圆相离及多边形窗口在圆内的两种不同情况, 其裁剪结果验证了本文提出方法的全面性.

对于相邻两点之间是圆弧连接还是直线段连接上, 文献[8]中提出的“中点检测法”需要计算两点中点与当前圆弧段之间的位置关系, 从而确定其连接方式; 本文在决定两点之间到底是圆弧还是直线段连接的判断只需判断相邻两点及前后点之间的位置关系断定, 节省了一定的计算量. 相比, 本文提出方法不仅能够全面有效地完成任意多边形窗口内圆的裁剪问题, 而且能够节省一定的工作量.

5 结论

本文讨论了任意多边形窗口内圆的一种更加全面、有效地裁剪算法. 其主要思想为: 首先, 通过 $x - $ 扫描线的思想, 确定由圆心出发的射线与多边形窗口的交点个数, 如果交点个数为奇数, 说明圆在多边形窗口内, 则绘制整个圆; 如果交点个数为偶数, 说明圆在多边形窗口外, 则整个圆被裁剪掉. 其次, 对于圆和多边形窗口相交的情况, 按照逆时针方向, 判断多边形顶点是否在圆内, 在圆内存入数组Q, 否则不存入; 然后求出多边形窗口每条直线段与圆的交点, 并存入数组Q. 最后, 通过判断两点间的关系, 决定两点之间画线还是画弧, 完成圆的裁剪. 实验结果表明, 该方法不仅能够全面、有效地完成任意多边形窗口内圆的裁剪, 而且大大降低了裁剪过程中的计算量.