基于端點區(qū)域分布的圓形窗口線裁剪算法

任洪海

(大連交通大學 軟件學院，遼寧 大連 116052)

0 引言

圓形窗口線裁剪擁有很強的實用價值，人們一直努力尋求高效的裁剪算法［1-6］.確定線段是否與圓形窗口相交是該類算法的關鍵.很多算法都引入窗口圓的外切正方形與內(nèi)接正方形作為預處理操作.一般外切正方形指四邊分別平行于坐標軸且與圓相切的正方形;而內(nèi)接正方形指四邊分別平行于坐標軸且包含在圓內(nèi)部的最大正方形.這樣定義往往只能獨立確定一部分完全在外切正方形之外和完全在內(nèi)接正方形之內(nèi)的特殊線段，后續(xù)還需進一步判斷剩余的線段.多數(shù)算法為此都應用了較為煩瑣的輔助操作.例如，文獻［3］中的旋轉矢量法、文獻［4］中制備規(guī)范化交點表、文獻［5］需要進行多重編碼、文獻［6］中幾何變換和逆變換等都需要花費很大精力.本文通過巧妙地定義外切正方形與內(nèi)接正方形使圓心為坐標原點的圓形窗口在四個象限的圓弧分別位于四個三角區(qū)域，將其定義為角區(qū).由此，將裁剪窗口所在平面劃分為內(nèi)接正方形之內(nèi)、外切正方形之外和角區(qū)三部分.根據(jù)線段兩端點在不同區(qū)域的分布情況完成裁剪過程.在裁剪過程中很多較復雜的判斷都轉化為線段所在直線與角區(qū)外界的相交情況進行處理，通過簡單判別快速確定線段是否與圓形窗口相交，從而顯著提高裁剪效率.

1 理論基礎

不失一般性，假設裁剪算法中圓形窗口的圓心為坐標原點，半徑為r;被裁剪線段的兩個端點為 p1(x1，y1)和 p2(x2，y2).

定義1 本文中的“外切正方形”指四邊平行于坐標軸，且與圓相切的正方形.

點在外切正方形之內(nèi)(或上)的判斷條件為:︱x︱≤r且 ︱y︱≤r;

點在外切正方形之外的判斷條件為:︱x︱ ＞r或 ︱y︱ ＞ r.

定義2 本文中的“內(nèi)接正方形”指順序連接外切正方形與圓的四個切點所形成的正方形.

點在內(nèi)接正方形之內(nèi)(或上)的判斷條件為:︱x︱ +︱y︱≤r;

點在內(nèi)接正方形之外的判斷條件為:︱x︱ +︱y︱ ＞ r.

定義3 在外切正方形之內(nèi)(或上)且內(nèi)接正方形之外的四個等腰直角三角形區(qū)域分別定義為角區(qū)，并根據(jù)所在象限區(qū)分為:第Ⅰ角區(qū)、第Ⅱ角區(qū)、第Ⅲ角區(qū)、第Ⅳ角區(qū)，如圖1.

定義4 每個角區(qū)的兩條直角邊稱為角區(qū)外界.角區(qū)外界根據(jù)各自所屬角區(qū)進行區(qū)分，四個角區(qū)所有的角區(qū)外界構成整個外切正方形.如果有直線相交于角區(qū)外界，可以根據(jù)交點坐標的符號確定是相交于相同角區(qū)外界還是相異角區(qū)外界.

圖1 線段裁剪部分示例圖

定義5 如果端點在某角區(qū)內(nèi)，進一步判斷端點與圓形窗口的位置關系:如果端點在圓形窗口之內(nèi)(或上)，稱該點在內(nèi)角區(qū);如果端點在圓形窗口之外，稱該點在外角區(qū).

定理1 如果一條直線相交于兩相異角區(qū)外界，則該直線一定與圓形窗口相交.

證明:不失一般性，假設直線相交于第一角區(qū)水平角區(qū)外界，設交點為I1(如圖1中線段a所在直線)，過該點向圓形窗口作切線.其中一條是與外切正方形部分水平邊重合，而另一條切線一定與第一角區(qū)垂直外界相交，設交點為I2.如果過I1點的直線與圓外切正方形相交于兩相異角區(qū)外界，則該直線一定在兩切線之間，因而與圓形窗口相交.

由定理1可推導出以下結論:

結論1 如果線段兩端點分別在兩相異外角區(qū)，可得線段一定與圓形窗口相交(如圖1中線段b).

結論2 如果線段一端點在外角區(qū)，另一端點在外切正方形之外，且線段相交于端點所在角區(qū)的相異角區(qū)外界，可得線段一定與圓形窗口相交(如圖1中線段c).

結論3 如果線段兩端點都在外切正方形之外，且線段相交于兩相異角區(qū)外界，可得線段一定與圓形窗口相交(如圖1中線段a).

結論4 如果線段一端點在外角區(qū)，另一端點在外切正方形之外，線段相交于本角區(qū)外界但延長外角區(qū)內(nèi)端點后延長線相交于相異角區(qū)外界，可得線段一定不與圓形窗口相交(如圖1中線段d).

結論5 如果線段兩端點分別在同一外角區(qū)內(nèi)，并且線段所在直線相交于不同角區(qū)外界，可得該線段一定不與圓形窗口相交(如圖1中線段e).

結論1～3由定理1很容易推出，結論4與結論5證明過程為:兩種情況都是線段所在直線相交于不同角區(qū)外界，根據(jù)定理1，線段延長后的直線與圓形窗口相交，而線段兩端點都在兩交點的同側，因而該線段本身一定不與圓形窗口相交.

以上結論所涉及的線段可以歸納為線段所在直線相交于不同角區(qū)外界的各種情況.當線段所在直線與某角區(qū)兩角區(qū)外界相交時，可根據(jù)該角區(qū)外界上兩個交點坐標判斷線段所在直線是否與圓形窗口相交.下面以線段相交于第Ⅰ角區(qū)兩角區(qū)外界為例討論該線段與圓形窗口的位置關系.

對于任意相交于第Ⅰ角區(qū)外界的線段f，兩交點為I1(xT，r)，I3(r，yR).可以取兩個交點任意一個，過該點作圓形窗口的切線.假設取I1，作圓形窗口的切線，與第Ⅰ角區(qū)垂直方向角區(qū)外界的交點設為I2(r，y'R)(如圖1)，根據(jù)切線長定理有:

由于相交于第Ⅰ角區(qū)外界，將上面兩個公式整理可得:xT×y'R=r2－(xT+y'R)r，由此求出:

比較yR與y'R的大小可得線段f與圓形窗口的位置關系:

如果yR＞y'R，可得線段f與圓形窗口相離;

如果yR=y'R，可得線段f與圓形窗口相切;

如果yR＜y'R，可得線段f與圓形窗口相交;

對于相交其它兩角區(qū)外界的線段，同樣可進行類似推導，并得出相應結論，在此不再描述.

2 算法描述

根據(jù)被裁剪線段兩端點區(qū)域分布情況裁剪過程討論如下:

(一)如果線段兩端點都在內(nèi)接正方形之內(nèi)，可得線段完全在圓形窗口之內(nèi)，保留該線段作為裁剪結果，如圖2中線段a.

圖2 線段裁剪部分示例圖

(二)如果線段一端點在內(nèi)接正方形之內(nèi)，而另一端點在外切正方形之外，可得線段與圓形窗口相交，求交點.內(nèi)接正方形之內(nèi)的端點到交點間線段為裁剪結果，如圖2中線段b.

(三)如果線段一端點在內(nèi)接正方形之內(nèi)，而另一端點在角區(qū)內(nèi)，進一步判斷角區(qū)內(nèi)的端點在內(nèi)角區(qū)還是外角區(qū).

(1)如果端點在內(nèi)角區(qū)，可得線段完全在圓形窗口之內(nèi)，保留該線段作為裁剪結果，如圖2中線段c.

(2)如果端點在外角區(qū)，可得線段與圓形窗口相交，求交點.內(nèi)接正方形之內(nèi)的端點到交點間線段為裁剪結果，如圖2中線段d.

(四)如果線段一端點在角區(qū)，而另一端點在切正方形之外，進一步判斷角區(qū)內(nèi)的端點在內(nèi)角區(qū)還是外角區(qū).

(1)如果端點在內(nèi)角區(qū)，可得線段與圓形窗口相交，求交點.角區(qū)內(nèi)端點到交點間線段為裁剪結果，如圖2中線段e.

(2)如果端點在外角區(qū)，線段一定與某角區(qū)外界相交，判斷是否相交于內(nèi)端點所在角區(qū)外界.

①如果線段相交于相異角區(qū)外界，根據(jù)結論2可得線段一定與圓形窗口相交，兩交點間線段為裁剪結果，如圖1中線段c.

②如果線段相交于本角區(qū)外界但延長線相交于其它角區(qū)外界，根據(jù)結論4可得線段一定不與圓形窗口相交，如圖1中線段d.

③如果線段所在直線相交于內(nèi)端點所在角區(qū)外界，求線段所在直線與該角區(qū)兩角區(qū)外界的交點，設交點為I1、I2，判斷線段I1I2與圓形窗口的位置關系:

a.如果I1I2與圓形窗口相離，可得線段不與圓形窗口相交，無裁剪結果輸出，如圖2中線段f.

b.如果I1I2與圓形窗口相交或相切，判斷兩端點p1、p2與線段p1p2主射線的位置關系.

如果兩端點p1、p2分別在線段p1p2主射線的兩側，方法為:

如果min(y1/x1，y2/x2)＜ (x1－x2)/(y2－y1)＜max(y1/x1，y2/x2)，線段與圓形窗口有交點，交點間線段為裁剪結果，如圖2中線段g.

否則線段與圓形窗口無交點，無裁剪結果輸出，如圖2中線段h.

(五)如果線段兩端點都在角區(qū)，進一步判斷兩端點在內(nèi)角區(qū)還是外角區(qū).

(1)如果兩端點都在內(nèi)角區(qū)，則線段完全在圓形窗口內(nèi)，保留該線段作為裁剪結果，如圖2中線段 i.

(2)如果一個端點在內(nèi)角區(qū)，另一個端點在外角區(qū)，則線段與圓形窗口有一交點，內(nèi)角區(qū)內(nèi)端點到交點間線段為裁剪結果，如圖2中線段j.

(3)如果兩個端點都在外角區(qū)，根據(jù)端點所在象限區(qū)分是否在相同外角區(qū):

①如果兩端點分別在不同外角區(qū)，根據(jù)結論1可得線段與圓形窗口有兩個交點，交點間線段為裁剪結果，圖1中線段b.

②如果兩端點在同一外角區(qū)，測試線段所在直線與外切正方形的相交情況:

a.如果相交于不同角區(qū)外界，根據(jù)結論5可得線段不與圓形窗口相交，無裁剪結果輸出，如圖1中線段e.

b.如果相交于同一角區(qū)外界，設交點為I1、I2，判斷線段I1I2與圓形窗口的位置關系:

c.如果I1I2與圓形窗口相離，可得線段不與圓形窗口相交，無裁剪結果輸出，如圖2中線段k.

d.如果I1I2與圓形窗口相交或相切，判斷兩端點p1、p2與線段p1p2主射線的位置關系:

如果兩端點p1、p2分別在線段p1p2主射線的兩側，方法為:

如果min(y1/x1，y2/x2)＜ (x1－x2)/(y2－y1)＜max(y1/x1，y2/x2)，線段與圓形窗口有交點，交點間線段為裁剪結果，如圖2中線段l.

否則線段與圓形窗口無交點，無裁剪結果輸出，如圖2中，在線段h上取角區(qū)內(nèi)一小線段.

(六)如果兩個端點都在外切正方形之外.進一步判斷線段與外切正方形的相交情況.

(1)如果線段不與外切正方形相交，可得線段一定不與圓形窗口相交，即無裁剪結果輸出，如圖2中線段m.

(2)如果線段與外切正方形相交于兩不同角區(qū)外界，可得線段一定與圓形窗口相交，兩交點間線段為裁剪結果，如圖1中線段a.

(3)如果線段與外切正方形相交于同一角區(qū)外界，設兩交點為I1、I2，判斷線段I1I2與圓形窗口的位置關系:

①如果I1I2與圓形窗口相離，可得線段不與圓形窗口相交，無裁剪結果輸出，如圖1中線段f.

②如果I1I2與圓形窗口相交或相切，可得線段與圓形窗口有交點，交點間線段為裁剪結果，如圖1中線段g.

3 結論

作為圓形窗口線裁剪算法，快速確定線段與圓形窗口的相交情況是提高效率的關鍵.本文提出的新算法在未增加其它復雜輔助操作前提下，通過判斷被裁剪線段兩端點相對于外切正方形與內(nèi)接正方形所劃分的不同區(qū)域情況完成裁剪過程.在算法中通過角區(qū)及角區(qū)外界等概念的引入，首次提出根據(jù)被裁剪線段相交于外切正方形及內(nèi)接正方形的情況直接確定是否與圓形窗口相交，避免大量不必要的求交運算及其它輔助操作.同時，新算法設計簡單，容易實現(xiàn).應用C++編程實現(xiàn)文獻［4-6］及本文算法，附表列出四個裁剪算法對于不同半徑圓形窗口裁剪300萬條隨機線段所需的時間比較.

附表 種裁剪算法裁剪300萬條線段所需時間比較 s

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

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