一种基于截距的圆形窗口线裁剪算法

任洪海， 郭发军， 王艳娟

（大连交通大学软件学院数字媒体教研室，辽宁 大连 116052）

线裁剪是计算机图形学的一个基本操作，作为圆形窗口线裁剪求交过程较为复杂，快速确定线段是否与窗口相交以及交点计算是这类算法的关键。近年来很多学者提出了圆形窗口的线裁剪算法。如文献[1-2]直接将线段参数方程代入圆形窗口的代数方程，通过求解一元二次方程实现裁剪，效率较低。文献[3]经过矩形单侧排除预处理后，利用圆心到直线段距离以及从圆心向直线段所引的垂直射线来判别直线段与圆形窗口的位置关系，但点-线距离以及旋转矢量法的计算量都很大。文献[4]通过制备规范化交点表避免了二次方程的运算，但需要很大精力建立复杂的规范化交点表。文献[5]利用常规外切正方形一次编码及旋转外切正方形二次编码排除部分圆形窗口之外的线段，在线段位置不确定的情况下，需要进行多重编码，而事实上并未简化求交过程。文献[6]通过坐标变换使线段与圆的位置关系转化为x轴与圆的位置关系，其中坐标变换和其逆变换都很费时。文献[7]通过圆切线斜率与线段斜率的比较确定线段是否与圆形窗口相交，一定程度提高了裁剪效率，不过求圆切线斜率也涉及到开方等复杂计算。

本文提出一种基于线段在两坐标轴上截距的圆形窗口线裁剪算法。经过简单测试，排除两端点都在圆外切正方形某边界之外的线段，并确定两端点都在圆形窗口内或一端点在圆形窗口内而另一端在圆形窗口外这两种情况中线段与圆形窗口的位置关系。对于两端点都在圆形窗口之外的情况，求线段所在直线相交x和y两坐标轴上的截距，并进行如下判断：如果线段所在直线在x或y任意坐标轴上截距的绝对值小于或等于圆半径 r，通过区分两端点在相交轴的同侧还是异侧可快速确定线段与圆形窗口的相交关系；否则，线段或不与圆形窗口相交或与圆形窗口相交于两截距所在半轴约束的象限上。根据该象限上外切正方形的顶点相对于线段所在直线的位置关系排除不与圆形窗口相交线段后，再通过线段与外切正方形两交点任意一个引射线相交外切正方形边所得到的交点与另一交点坐标相比较确定线段是否与圆形窗口相交。该方法可以快速确定线段与圆形窗口的位置关系，明显提高裁剪效率。

1 基本定义

不失一般性，假设裁剪算法中圆形窗口的圆心为坐标原点。如果圆心在其它位置，通过坐标系平移将圆心平移到坐标原点。被裁剪线段的两个端点设为p1(x1,y1)和p2(x2,y2)。

定义 1本文中的“外切正方形”指四边平行于坐标轴，且与圆形窗口相切的正方形。

通过端点pi(xi，yi)（i取1或2）的两坐标值与外切正方形的4个边界相比较确定该点与边界的位置关系：

如果xi＜-r，该点在左边界外侧；否则，该点在左边界内侧或上；

如果xi＞r，该点在右边界外侧；否则，该点在右边界内侧或上；

如果yi＜-r，该点在下边界外侧；否则，该点在下边界内侧或上；

如果yi＞r，该点在上边界外侧；否则，该点在上边界内侧或上。

从而得出线段端点相对于外切正方形及圆形窗口的位置关系为：

如果线段的端点在某一边界的外侧，则该端点一定在外切正方形之外，该端点也在圆形窗口之外。

如果线段的端点在4条边界的内侧或上，则该端点在外切正方形的内侧或上，再进一步判断端点与圆形窗口的位置关系：

设端点pi(xi，yi)（i取1或2）到圆形窗口圆心距离的平方为：

定义 2过圆心向线段p1p2引垂直射线l，称射线l为该线段的主射线。

区分线段两端点p1、p2在其主射线的异侧还是同侧的方法为：

1）当线段p1p2为水平线（即y2＝y1）时：如果x1与x2异号，则两端点 p1、p2分别在线段p1p2主射线l的异侧；否则，两端点p1、p2分别在线段p1p2主射线l的同侧。

2）当线段p1p2非水平线（即y2≠y1）时：如果 min(y1/x1，y2/x2)＜(x1-x2)/(y2-y1)＜max(y1/x1，y2/x2)，则两端点p1、p2分别在线段p1p2主射线l的异侧；否则，两端点p1、p2分别在线段p1p2主射线l的同侧。

2 线段与圆形窗口相交判断

当线段两端点都在外切正方形某边界之外时，线段一定在圆形窗口之外，排除该线段（如图 1线段 l1）。当线段两端点都在圆形窗口之内时，线段一定在圆形窗口之内，保留该线段（如图 1线段 l2）。当线段一端点在圆形窗口之内而另一端点在圆形窗口之外时，线段与圆形窗口相交，实交点到内端点间线段为裁剪结果（如图1线段 l3）。当线段两端点不同时在外切正方形某边界之外且都在圆形窗口之外时，通过线段所在直线相交于两坐标轴上的截距与圆半径的比较分情况确定线段与圆形窗口的位置关系，具体判断如下：

1）线段所在直线相交x或y任意坐标轴上截距的绝对值小于或等于圆半径r的情况。

定理1对于圆心为坐标原点的圆，如果直线相交x或y任意坐标轴上截距的绝对值小于或等于圆半径r，可得该直线一定与圆相交。

证明：过圆心向直线做垂线段，在包含垂线段与x或y坐标轴上截距边的直角三角形内，垂线段（作为直角边）一定小于截距边（作为斜边）。因此，如果截距的绝对值小于或等于 r，圆心到直线的距离一定小于圆半径 r，从而直线一定与圆相交。

线段p1p2所在的直线方程为

根据定理1很容易得出如下结论：当线段两端点都在圆形窗口之外且线段所在直线相交x或y任意坐标轴上截距的绝对值小于或等于圆半径r时，如果线段两端点在截距的绝对值小于r那个相交轴的异侧，则线段一定与圆形窗口相交（如图 1线段 l4）；如果线段两端点在截距的绝对值小于r那个相交轴的同侧，则线段一定不与圆形窗口相交（如图1线段l5）。判断过程如下：

如果-r≤a≤r，且 y1与 y2异号， 则线段与圆形窗口相交；

如果-r≤a≤r，且 y1与 y2同号， 则线段不与圆形窗口相交；

如果-r≤b≤r，且 x1与 x2异号， 则线段与圆形窗口相交；

如果-r≤b≤r，且 x1与 x2同号， 则线段不与圆形窗口相交；

如果线段为水平线段或垂直线段时，只求一个方向截距进行判断即可。

图1 主要类型线段相对于圆形窗口的位置关系

2）线段所在直线相交x和y两坐标轴截距的绝对值都大于圆半径r的情况

当线段所在直线相交x和y两坐标轴截距的绝对值都大于圆半径r时，线段与圆形窗口位置关系有两种情况：线段不与圆形窗口相交或线段与圆形窗口相交于两截距所在半轴约束的象限上。通过测试两方向截距所在半轴对应象限上外切正方形的顶点关于线段所在直线的方向，首先判断线段所在直线是否与外切正方形相交。如果线段所在直线不与外切正方形相交，则线段一定不与圆形窗口相交。假设两截距分别在 x轴的正半轴与y轴的正半轴，则测试外切正方形在第1象限的顶点(r,r)关于直线的方向。

由于已求出直线在两坐标轴上的截距 a与b，直线可应用截距式方程表示

在第1象限上，如果线段所在直线相交x轴与 y轴的截距都大于圆半径 r，则有：可得(r,0)在直线下侧；同时，可得(0,r)在直线下侧。

对于任意所在直线相交于外切正方形在第1象限上1/2上边与1/2右边的线段，将外切正方形边界条件代入直线的截距式方程求直线与外切正方形的两交点为。可以取两个交点任意一个，过该交点作圆形窗口的切线。假设取作圆形窗口的切线与外切正方形在第 1象限上 1/2右边的交点设为

根据I1I3两点距离公式有

比较yR与y'R的大小可得线段所在直线与圆形窗口的位置关系：

如果 yR＜y'R，可得线段所在直线与圆形窗口相交（如图1线段l6）；

如果 yR=y'R，可得线段所在直线与圆形窗口相切；

如果 yR＞y'R，可得线段所在直线与圆形窗口相离（如图1线段l7）；

如果取 I2作圆形窗口的切线与外切正方形相交，则通过比较交点的x方向坐标进行判断线段所在直线与圆形窗口的位置关系。对于与外切正方形相交于其它象限上的线段，同样可进行类似推导，并得出相应结论。

3 裁剪算法描述

4 快速求线段与圆形窗口的交点

当被裁剪线段一端点在圆形窗口内，而另一端点在圆形窗口外，确定线段与圆形窗口有交点后，通过两端点形成直线段参数方程代入圆方程求交点。对于大部分两端点在圆形窗口之外的情况，由于根据被裁剪线段所在直线在两坐标轴的截距判断线段是否与圆形窗口相交，当确定被裁剪线段与圆形窗口有交点时，可以应用线段所在直线与两轴坐标的交点(a,0)和(0,b)形成直线参数方程代入圆方程求交点。具体操作如下：

对于过(a,0)和(0,b)的直线，可用参数形式描述为

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

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

解此一元二次方程，可得

由于被裁剪线段两端点都在圆形窗口之外，如果线段与圆形窗口有交点，则一定有两个交点（相切时有两相同交点），求出u值代入直线的参数方程即可得到两个交点。此一元二次方程解中都是两截距a、b平方与圆半径r平方的组合，很容易构造。

5 算法分析与比较

本文根据被裁剪线段所在直线相交x、y坐标轴上的截距可以确定大部分线段是否与圆形窗口相交。对于其它不能确定相交关系的被裁剪线段，通过点与线的关系及交点坐标比较等简单操作即可快速完成判断。另外通过截距形成被裁剪线段所在直线的参数方程代入圆方程求交点，方程构造与求解形式都比较简单。表1为对于几种主要类型的被裁剪线段（图 1所示），应用本算法进行圆形窗口线裁剪需要的主要操作及运算量。

表1 几种主要类型线段圆形窗口裁剪过程需要的主要操作与运算量

从表1可得出本算法在确定线段与圆形窗口有交点后，才应用1次开方运算求交点，其它判断线段是否与圆形窗口相交的过程只涉及乘除、加减、比较等简单运算。

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

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

由表2可以看出新算法的裁剪效率明显高于现有的4种典型算法。

6 结 论

以二次函数作为约束条件的圆形窗口线裁剪求交过程较为复杂。本文根据线段所在直线相交两坐标轴上的截距与窗口圆半径r相比较，以及线段与所引切线分别相交外切正方形边的交点坐标相比较等方法确定线段与圆形窗口的位置关系。该方法将线段与圆形窗口位置关系的两维问题转化成主要在 x、y两坐标轴上或某外切正方形边上数值比较的一维问题，从而开辟一条解决圆形窗口线裁剪的新途径。在确定线段与圆形窗口位置关系过程中主要涉及的线段在两坐标轴上截距的计算、点线位置关系的判断和所引切线与外切正方形边交点的计算等过程通过简单比较和四则运算即可完成，不需要幂、开方和三角函数等复杂运算，从而能够快速确定线段与圆形窗口是否相交，提高裁剪效率。本文提出的圆形窗口线裁剪算法很容易推广到椭圆窗口的线裁剪，同时对球体等三维窗口的线裁剪也具有很强的参考价值。究与实践[J]. 计算机辅助设计与图形学学报,1992,4(3): 14-20.

[1] 姚涵珍,宋 鹏,张国安. 圆形窗口裁剪算法的研

[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] 任洪海,张飞侠. 一种有效的圆形窗口线裁剪算法[J]. 工程图学学报,2011,32(5): 74-78.

[8] Hearn D,Baker M P. Computer graphics with openGL(third edition) [M]. Publishing House of Electronics Industry,2005: 315-340.