一种有效的圆形窗口线裁剪算法

任洪海， 张飞侠

（1. 大连交通大学软件学院计算机图形学教研室，辽宁 大连 116052；2.辽宁对外经贸学院信息技术系，辽宁 大连 116052）

线裁剪是计算机图形学中的一个基本操作。针对于圆形窗口的线裁剪较为复杂，人们一直努力寻求高效的裁剪算法。如文献[1-2]将线段参数方程代入圆形窗口的代数方程中进行裁剪，裁剪效率较低。文献[3]利用圆心到直线段距离以及从圆心向直线段所引的垂直射线来判别直线段与圆形窗口的位置关系，但点到直线间距离以及旋转矢量法求交点计算量都很大。文献[4]利用圆与其外切正方形的线性关系制备规范化交点表，通过映射法查表实现裁剪，不过规范化表的制作需要花费很大精力。文献[5]利用常规外切正方形一次编码、旋转外切正方形二次编码和广义距离三次编码分别获取不同情况的线段，但在线段位置不确定的情况下，需要进行多重编码，而事实上并未简化求交过程。文献[6]将平移、旋转坐标变换引入裁剪算法中，使线段与圆的位置关系转化为x轴与圆的位置关系，该方法需要费时的几何变换和逆变换。

本文通过讨论线段两端点相对于圆形窗口的位置关系，结合远端点到圆切线斜率与线段斜率的比较以及巧妙的点区域判别快速地判断线段与圆形窗口的相对位置。在确定线段与圆形窗口有交点时才进行求交运算，并应用线段参数化形式代入圆方程求交点，简化求交方程的构造，显著提高了裁剪效率。

1 算法设计

不失一般性，假设裁剪算法中圆形窗口的圆心为坐标原点，半径为 r；被裁剪线段的两个端点为p1(x1, y1)和p2(x2, y2)。

1.1 预处理

根据圆的常规外切正方形，经过简单运算可排除完全位于常规外切正方形同侧的线段，其判断条件为：

1.2 其它类型线段判别方法

1.2.1 线段与圆形窗口位置关系的讨论

对于那些通过预处理方法无法排除的线段，计算线段两端点到圆形窗口圆心距离的平方，并讨论线段两端点相对于圆形窗口的位置关系。

端点pi（i取1或2）到圆形窗口圆心距离的平方为：di2=xi2+ yi2

如果di2＜r2， 可得端点pi在圆形窗口内；

如果di2＝r2， 可得端点pi在圆形窗口上；

如果di2＞r2， 可得端点pi在圆形窗口外。

根据这种相对应的位置关系，区分不同情况判断如下：

（1）如果线段p1p2两端点都在圆形窗口内（也包括：两端点都在窗口上或一个端点在窗口内而另一个端点在窗口上），可得线段在圆形窗口内，所以线段p1p2为裁剪结果。

（2）如果线段 p1p2一个端点在圆形窗口内，而另一个端点在圆形窗口外，可得线段与窗口有交点。应用线段参数形式代入圆方程求交点，窗口内端点到交点之间线段为裁剪结果。

（3）如果线段 p1p2两端点都在圆形窗口外，从距离圆心较远的端点向圆引切线，通过比较两切线斜率与线段斜率，判断线段与圆形窗口的相交情况，具体操作如下：

如果d12≥d22，取p1点向圆引切线，否则取p2点向圆引切线。假设取p1(x1, y1)点向圆引切线，如图1所示。

图1 线段远端点引圆切线关系图

p1o斜率为y1/ x1，设倾斜角为a，则tan(a)=y1/ x1。

p1o与两切线形成的夹角相等，设为 b，则

经验证，无论p1在圆形窗口外的哪个位置，从p1向圆引两切线的倾斜角分别为

c1=a＋b＋kπ 及 c2=a-b＋kπ (k 取 0 或 1 或-1)（证明略）

因而从p1向圆引两切线的斜率分别为tan(c1)和tan(c2)，由于正切函数以π为周期，可以忽略kπ。如果直接应用倾斜角计算斜率必然涉及三角函数和反三角函数，运算较为复杂。可以将tan(c1)和tan(c2)转化为

将已知的三角函数代入并整理得：

如果线段p1p2斜率m满足：

可得p1p2所在直线与圆形窗口相交（等号成立时为相切情况，也可包括在内讨论）。

否则，p1p2所在直线与圆形窗口相离，舍弃线段p1p2。

当p1p2所在直线与圆形窗口相交时，可根据p2所在区域情况判断线段是否与圆形窗口相交，而不必都进行求交运算。由于向圆形窗口引切线的端点是取距离圆心较远的端点，已假设为p1，那么另一个端点p2一定不在Ⅰ区域，只可能在Ⅱ区域或Ⅲ区域，如图1所示。

如果端点p2在Ⅱ区域，线段p1p2与圆形窗口没有交点，则舍弃线段p1p2。

如果端点p2在Ⅲ区域，线段p1p2与圆形窗口有两个交点，两交点间线段为裁剪结果。

（如果线段p1p2所在直线与圆形窗口相切，当端点p2在Ⅲ区域，切点为裁剪结果）

定义1 以圆上两切点为界，Ⅱ区域所对的圆弧边界为Ⅱ区域对应圆弧；Ⅲ区域所对的圆弧边界为Ⅲ区域对应圆弧。

由于Ⅱ区域中所有点到 p1的距离都小于其延长线相交于该区域对应圆弧所形成的交点到p1的距离，而Ⅱ区域对应圆弧上切点到p1的距离最大，所以Ⅱ区域所有点到p1的距离都小于切点到 p1的距离；以此类推，Ⅲ区域所有点到p1的距离都大于切点到p1的距离。因此，本文巧妙地根据p1p2线段距离平方与p1到切点距离平方的比较判别p2在Ⅱ区域还是Ⅲ区域，具体操作如下：

如果 (x2-x1)2+(y2-y1)2＜x12+y12-r2，即 x22+y22+r2-2 x1x2-2y1y2＜0，则p2在Ⅱ区域。

如果(x2-x1)2+(y2-y1)2＞x12+y12-r2，即 x22+y22+r2-2 x1x2-2y1y2＞0，则p2在Ⅲ区域。

设m=x1x2＋y1y2，p2点区域判别过程简化为：如果d22+r2-2m＜0，则p2在Ⅱ区域。如果d22+ r2-2m＞0，则p2在Ⅲ区域。

（4）特殊情况处理：如果一个端点在圆形窗口上，而另一个端点在圆形窗口外。虽然这种情况可以归入情况（2），即直接将线段参数形式代入圆方程求交点。如果在0＜u＜1范围内没有取值，裁剪结果就只有在圆形窗口上的端点；如果在0＜u＜1范围内有值，对应交点到圆形窗口上端点之间线段为裁剪结果。但这种处理方法对于裁剪结果只是圆形窗口上端点的情况也需求交运算，增加了运算量。本文采用另一种处理方法：假设圆形窗口外的端点为p1，从p1引圆的切线，则线段p1p2所在直线必在两切线之间，如情况（3）中讨论：

如果d22+r2-2m≤0，可得端点p2在Ⅱ区域对应圆弧上，线段p1p2与圆形窗口只相交于端点p2，则端点p2为裁剪结果。

如果d22+r2-2m＞0，可得端点p2在Ⅲ区域对应圆弧上，线段p1p2与圆形窗口除p2之外还有一个交点，则端点p2到该交点间线段为裁剪结果。

1.2.2 快速的求交运算

如果线段与圆形窗口有交点，将线段的参数化形式代入圆方程求交点，具体操作如下：

对于端点为p1(x1, y1)和p2(x2, y2)的直线段，可使用参数形式描述为

作为线段与圆形窗口的交点，必满足：x2+y2=r2，将直线参数式代入该方程得

可整理为关于u的一元二次方程

此时一元二次方程的系数都是已求出式子的组合，因而容易构造。解此一元二次方程。

对于情况（2）和情况（4）中有一个非端点的交点情况，解一元二次方程后在0＜u＜1取值范围必能取到一个值，该值对应的点即为线段与圆形窗口的交点。

对于情况（3）中通过斜率比较与点区域判别得到的线段与圆形窗口有两个交点的情况，解一元二次方程后在0＜u＜1取值范围必能取到两个值，这两个值分别对应的点即为线段与圆形窗口的两个交点。（对于线段 p1p2与圆相切情况，只得到对应的一个切点）

2 算法比较

本文与文献[3]在算法设计过程中都利用了线段两端点到圆心的距离作为判断条件，但文献[3]先用矢量叉乘法计算出圆心到线段的距离，在划分出部分线段同时也增加了较大的计算量，另外利用旋转矢量法求交点并未减少求交的计算量。表1列出本文算法与文献[3]算法对于常规外切正方形边界判断无法排出的各种端点类型线段所需主要数学运算量的比较。

表1 本算法与文献[3]算法对于各种端点类型线段裁剪所需运算量的比较

从表1比较可知，对于各种类型线段本算法所需总运算量都要比文献[3]小很多，特别对于线段与圆形窗口有交点的情况。

在同等硬件条件下，应用C++编程实现文献[3]、文献[5]、文献[6]及本文算法，表2 列出四个裁剪算法对于不同半径圆形窗口裁剪400万条随机线段所需的时间比较。

表2 四种裁剪算法裁剪400万条线段所需时间比较（单位：秒）

由表2可以看出新算法的裁剪效率都高于现有的三个典型算法。

3 结 论

圆形窗口的线裁剪算法拥有很强的实用价值，目前具有特色的优秀算法较少。本文在讨论线段两端点相对于圆形窗口位置关系的基础上，首次通过线段中距离圆心较远的端点到圆两切线的斜率与线段斜率的比较，以及另一端点在两切线间有限区域的判别作为判断条件来确定线段与圆形窗口的相交情况。在确定有交点后，利用线段的参数化形式代入圆方程，从而简化求交过程中一元二次方程的构造，明显提高了裁剪效率。另外本文提出的圆形窗口线裁剪很容易推广到椭圆窗口的线裁剪，具有很强的参考价值。

[1]姚涵珍, 宋 鹏, 张国安. 圆形窗口裁剪算法的研究与实践[J]. 计算机辅助设计与图形学学报, 1992,4(3): 14-20.

[2]刘勇奎. 圆形及椭圆形裁剪窗口[J]. 计算机工程与设计, 1994, 15(4): 33-37.

[3]沈庆云, 周来水, 周儒荣. 一种圆形窗口裁剪的新方法[J]. 计算机辅助设计与图形学学报, 1997, 9(6):538-542.

[4]蔡 敏, 袁春风, 宋继强, 等. 一种快速的圆形窗口裁剪算法[J]. 计算机辅助设计与图形学学报, 2001,13(12): 1063-1067.

[5]陆国栋, 邢军伟, 谭建荣. 基于多重编码技术的圆形窗口线裁剪算法[J]. 计算机辅助设计与图形学学报, 2002, 14(12): 1133-1137.

[6]唐 棣, 单会秋. 一种基于坐标变换的圆形窗口线裁剪算法[J]. 计算机应用与软件, 2006, 23(5):116-118.

[7]孙家广, 杨长贵. 计算机图形学(第 3版)[M]. 北京:清华大学出版社, 1998. 199-208.

[8]Donald Hearn, Pauline Baker M. Computer graphics with openGL [M]. Third Edition Publishing House of Electronics Industry, 2005. 315-340.