一種有效的圓形窗口線裁剪算法

任洪海， 張飛俠

（1. 大連交通大學(xué)軟件學(xué)院計(jì)算機(jī)圖形學(xué)教研室，遼寧 大連 116052；2.遼寧對外經(jīng)貿(mào)學(xué)院信息技術(shù)系，遼寧 大連 116052）

線裁剪是計(jì)算機(jī)圖形學(xué)中的一個基本操作。針對于圓形窗口的線裁剪較為復(fù)雜，人們一直努力尋求高效的裁剪算法。如文獻(xiàn)[1-2]將線段參數(shù)方程代入圓形窗口的代數(shù)方程中進(jìn)行裁剪，裁剪效率較低。文獻(xiàn)[3]利用圓心到直線段距離以及從圓心向直線段所引的垂直射線來判別直線段與圓形窗口的位置關(guān)系，但點(diǎn)到直線間距離以及旋轉(zhuǎn)矢量法求交點(diǎn)計(jì)算量都很大。文獻(xiàn)[4]利用圓與其外切正方形的線性關(guān)系制備規(guī)范化交點(diǎn)表，通過映射法查表實(shí)現(xiàn)裁剪，不過規(guī)范化表的制作需要花費(fèi)很大精力。文獻(xiàn)[5]利用常規(guī)外切正方形一次編碼、旋轉(zhuǎn)外切正方形二次編碼和廣義距離三次編碼分別獲取不同情況的線段，但在線段位置不確定的情況下，需要進(jìn)行多重編碼，而事實(shí)上并未簡化求交過程。文獻(xiàn)[6]將平移、旋轉(zhuǎn)坐標(biāo)變換引入裁剪算法中，使線段與圓的位置關(guān)系轉(zhuǎn)化為x軸與圓的位置關(guān)系，該方法需要費(fèi)時的幾何變換和逆變換。

本文通過討論線段兩端點(diǎn)相對于圓形窗口的位置關(guān)系，結(jié)合遠(yuǎn)端點(diǎn)到圓切線斜率與線段斜率的比較以及巧妙的點(diǎn)區(qū)域判別快速地判斷線段與圓形窗口的相對位置。在確定線段與圓形窗口有交點(diǎn)時才進(jìn)行求交運(yùn)算，并應(yīng)用線段參數(shù)化形式代入圓方程求交點(diǎn)，簡化求交方程的構(gòu)造，顯著提高了裁剪效率。

1 算法設(shè)計(jì)

不失一般性，假設(shè)裁剪算法中圓形窗口的圓心為坐標(biāo)原點(diǎn)，半徑為 r；被裁剪線段的兩個端點(diǎn)為p1(x1, y1)和p2(x2, y2)。

1.1 預(yù)處理

根據(jù)圓的常規(guī)外切正方形，經(jīng)過簡單運(yùn)算可排除完全位于常規(guī)外切正方形同側(cè)的線段，其判斷條件為：

1.2 其它類型線段判別方法

1.2.1 線段與圓形窗口位置關(guān)系的討論

對于那些通過預(yù)處理方法無法排除的線段，計(jì)算線段兩端點(diǎn)到圓形窗口圓心距離的平方，并討論線段兩端點(diǎn)相對于圓形窗口的位置關(guān)系。

端點(diǎn)pi（i取1或2）到圓形窗口圓心距離的平方為：di2=xi2+ yi2

如果di2＜r2， 可得端點(diǎn)pi在圓形窗口內(nèi)；

如果di2＝r2， 可得端點(diǎn)pi在圓形窗口上；

如果di2＞r2， 可得端點(diǎn)pi在圓形窗口外。

根據(jù)這種相對應(yīng)的位置關(guān)系，區(qū)分不同情況判斷如下：

（1）如果線段p1p2兩端點(diǎn)都在圓形窗口內(nèi)（也包括：兩端點(diǎn)都在窗口上或一個端點(diǎn)在窗口內(nèi)而另一個端點(diǎn)在窗口上），可得線段在圓形窗口內(nèi)，所以線段p1p2為裁剪結(jié)果。

（2）如果線段 p1p2一個端點(diǎn)在圓形窗口內(nèi)，而另一個端點(diǎn)在圓形窗口外，可得線段與窗口有交點(diǎn)。應(yīng)用線段參數(shù)形式代入圓方程求交點(diǎn)，窗口內(nèi)端點(diǎn)到交點(diǎn)之間線段為裁剪結(jié)果。

（3）如果線段 p1p2兩端點(diǎn)都在圓形窗口外，從距離圓心較遠(yuǎn)的端點(diǎn)向圓引切線，通過比較兩切線斜率與線段斜率，判斷線段與圓形窗口的相交情況，具體操作如下：

如果d12≥d22，取p1點(diǎn)向圓引切線，否則取p2點(diǎn)向圓引切線。假設(shè)取p1(x1, y1)點(diǎn)向圓引切線，如圖1所示。

圖1 線段遠(yuǎn)端點(diǎn)引圓切線關(guān)系圖

p1o斜率為y1/ x1，設(shè)傾斜角為a，則tan(a)=y1/ x1。

p1o與兩切線形成的夾角相等，設(shè)為 b，則

經(jīng)驗(yàn)證，無論p1在圓形窗口外的哪個位置，從p1向圓引兩切線的傾斜角分別為

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

因而從p1向圓引兩切線的斜率分別為tan(c1)和tan(c2)，由于正切函數(shù)以π為周期，可以忽略kπ。如果直接應(yīng)用傾斜角計(jì)算斜率必然涉及三角函數(shù)和反三角函數(shù)，運(yùn)算較為復(fù)雜?？梢詫an(c1)和tan(c2)轉(zhuǎn)化為

將已知的三角函數(shù)代入并整理得：

如果線段p1p2斜率m滿足：

可得p1p2所在直線與圓形窗口相交（等號成立時為相切情況，也可包括在內(nèi)討論）。

否則，p1p2所在直線與圓形窗口相離，舍棄線段p1p2。

當(dāng)p1p2所在直線與圓形窗口相交時，可根據(jù)p2所在區(qū)域情況判斷線段是否與圓形窗口相交，而不必都進(jìn)行求交運(yùn)算。由于向圓形窗口引切線的端點(diǎn)是取距離圓心較遠(yuǎn)的端點(diǎn)，已假設(shè)為p1，那么另一個端點(diǎn)p2一定不在Ⅰ區(qū)域，只可能在Ⅱ區(qū)域或Ⅲ區(qū)域，如圖1所示。

如果端點(diǎn)p2在Ⅱ區(qū)域，線段p1p2與圓形窗口沒有交點(diǎn)，則舍棄線段p1p2。

如果端點(diǎn)p2在Ⅲ區(qū)域，線段p1p2與圓形窗口有兩個交點(diǎn)，兩交點(diǎn)間線段為裁剪結(jié)果。

（如果線段p1p2所在直線與圓形窗口相切，當(dāng)端點(diǎn)p2在Ⅲ區(qū)域，切點(diǎn)為裁剪結(jié)果）

定義1 以圓上兩切點(diǎn)為界，Ⅱ區(qū)域所對的圓弧邊界為Ⅱ區(qū)域?qū)?yīng)圓?。虎髤^(qū)域所對的圓弧邊界為Ⅲ區(qū)域?qū)?yīng)圓弧。

由于Ⅱ區(qū)域中所有點(diǎn)到 p1的距離都小于其延長線相交于該區(qū)域?qū)?yīng)圓弧所形成的交點(diǎn)到p1的距離，而Ⅱ區(qū)域?qū)?yīng)圓弧上切點(diǎn)到p1的距離最大，所以Ⅱ區(qū)域所有點(diǎn)到p1的距離都小于切點(diǎn)到 p1的距離；以此類推，Ⅲ區(qū)域所有點(diǎn)到p1的距離都大于切點(diǎn)到p1的距離。因此，本文巧妙地根據(jù)p1p2線段距離平方與p1到切點(diǎn)距離平方的比較判別p2在Ⅱ區(qū)域還是Ⅲ區(qū)域，具體操作如下：

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

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

設(shè)m=x1x2＋y1y2，p2點(diǎn)區(qū)域判別過程簡化為：如果d22+r2-2m＜0，則p2在Ⅱ區(qū)域。如果d22+ r2-2m＞0，則p2在Ⅲ區(qū)域。

（4）特殊情況處理：如果一個端點(diǎn)在圓形窗口上，而另一個端點(diǎn)在圓形窗口外。雖然這種情況可以歸入情況（2），即直接將線段參數(shù)形式代入圓方程求交點(diǎn)。如果在0＜u＜1范圍內(nèi)沒有取值，裁剪結(jié)果就只有在圓形窗口上的端點(diǎn)；如果在0＜u＜1范圍內(nèi)有值，對應(yīng)交點(diǎn)到圓形窗口上端點(diǎn)之間線段為裁剪結(jié)果。但這種處理方法對于裁剪結(jié)果只是圓形窗口上端點(diǎn)的情況也需求交運(yùn)算，增加了運(yùn)算量。本文采用另一種處理方法：假設(shè)圓形窗口外的端點(diǎn)為p1，從p1引圓的切線，則線段p1p2所在直線必在兩切線之間，如情況（3）中討論：

如果d22+r2-2m≤0，可得端點(diǎn)p2在Ⅱ區(qū)域?qū)?yīng)圓弧上，線段p1p2與圓形窗口只相交于端點(diǎn)p2，則端點(diǎn)p2為裁剪結(jié)果。

如果d22+r2-2m＞0，可得端點(diǎn)p2在Ⅲ區(qū)域?qū)?yīng)圓弧上，線段p1p2與圓形窗口除p2之外還有一個交點(diǎn)，則端點(diǎn)p2到該交點(diǎn)間線段為裁剪結(jié)果。

1.2.2 快速的求交運(yùn)算

如果線段與圓形窗口有交點(diǎn)，將線段的參數(shù)化形式代入圓方程求交點(diǎn)，具體操作如下：

對于端點(diǎn)為p1(x1, y1)和p2(x2, y2)的直線段，可使用參數(shù)形式描述為

作為線段與圓形窗口的交點(diǎn)，必滿足：x2+y2=r2，將直線參數(shù)式代入該方程得

可整理為關(guān)于u的一元二次方程

此時一元二次方程的系數(shù)都是已求出式子的組合，因而容易構(gòu)造。解此一元二次方程。

對于情況（2）和情況（4）中有一個非端點(diǎn)的交點(diǎn)情況，解一元二次方程后在0＜u＜1取值范圍必能取到一個值，該值對應(yīng)的點(diǎn)即為線段與圓形窗口的交點(diǎn)。

對于情況（3）中通過斜率比較與點(diǎn)區(qū)域判別得到的線段與圓形窗口有兩個交點(diǎn)的情況，解一元二次方程后在0＜u＜1取值范圍必能取到兩個值，這兩個值分別對應(yīng)的點(diǎn)即為線段與圓形窗口的兩個交點(diǎn)。（對于線段 p1p2與圓相切情況，只得到對應(yīng)的一個切點(diǎn)）

2 算法比較

本文與文獻(xiàn)[3]在算法設(shè)計(jì)過程中都利用了線段兩端點(diǎn)到圓心的距離作為判斷條件，但文獻(xiàn)[3]先用矢量叉乘法計(jì)算出圓心到線段的距離，在劃分出部分線段同時也增加了較大的計(jì)算量，另外利用旋轉(zhuǎn)矢量法求交點(diǎn)并未減少求交的計(jì)算量。表1列出本文算法與文獻(xiàn)[3]算法對于常規(guī)外切正方形邊界判斷無法排出的各種端點(diǎn)類型線段所需主要數(shù)學(xué)運(yùn)算量的比較。

表1 本算法與文獻(xiàn)[3]算法對于各種端點(diǎn)類型線段裁剪所需運(yùn)算量的比較

從表1比較可知，對于各種類型線段本算法所需總運(yùn)算量都要比文獻(xiàn)[3]小很多，特別對于線段與圓形窗口有交點(diǎn)的情況。

在同等硬件條件下，應(yīng)用C++編程實(shí)現(xiàn)文獻(xiàn)[3]、文獻(xiàn)[5]、文獻(xiàn)[6]及本文算法，表2 列出四個裁剪算法對于不同半徑圓形窗口裁剪400萬條隨機(jī)線段所需的時間比較。

表2 四種裁剪算法裁剪400萬條線段所需時間比較（單位：秒）

由表2可以看出新算法的裁剪效率都高于現(xiàn)有的三個典型算法。

3 結(jié) 論

圓形窗口的線裁剪算法擁有很強(qiáng)的實(shí)用價(jià)值，目前具有特色的優(yōu)秀算法較少。本文在討論線段兩端點(diǎn)相對于圓形窗口位置關(guān)系的基礎(chǔ)上，首次通過線段中距離圓心較遠(yuǎn)的端點(diǎn)到圓兩切線的斜率與線段斜率的比較，以及另一端點(diǎn)在兩切線間有限區(qū)域的判別作為判斷條件來確定線段與圓形窗口的相交情況。在確定有交點(diǎn)后，利用線段的參數(shù)化形式代入圓方程，從而簡化求交過程中一元二次方程的構(gòu)造，明顯提高了裁剪效率。另外本文提出的圓形窗口線裁剪很容易推廣到橢圓窗口的線裁剪，具有很強(qiáng)的參考價(jià)值。

[1]姚涵珍, 宋 鵬, 張國安. 圓形窗口裁剪算法的研究與實(shí)踐[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1992,4(3): 14-20.

[2]劉勇奎. 圓形及橢圓形裁剪窗口[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 1994, 15(4): 33-37.

[3]沈慶云, 周來水, 周儒榮. 一種圓形窗口裁剪的新方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1997, 9(6):538-542.

[4]蔡 敏, 袁春風(fēng), 宋繼強(qiáng), 等. 一種快速的圓形窗口裁剪算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2001,13(12): 1063-1067.

[5]陸國棟, 邢軍偉, 譚建榮. 基于多重編碼技術(shù)的圓形窗口線裁剪算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2002, 14(12): 1133-1137.

[6]唐 棣, 單會秋. 一種基于坐標(biāo)變換的圓形窗口線裁剪算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2006, 23(5):116-118.

[7]孫家廣, 楊長貴. 計(jì)算機(jī)圖形學(xué)(第 3版)[M]. 北京:清華大學(xué)出版社, 1998. 199-208.

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