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

任洪海， 張飛俠

（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.