任洪海

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

0 引言

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

1 理論基礎(chǔ)

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

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

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

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

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

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

點(diǎn)在內(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ū)進(jìn)行區(qū)分，四個角區(qū)所有的角區(qū)外界構(gòu)成整個外切正方形.如果有直線相交于角區(qū)外界，可以根據(jù)交點(diǎn)坐標(biāo)的符號確定是相交于相同角區(qū)外界還是相異角區(qū)外界.

圖1 線段裁剪部分示例圖

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

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

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

由定理1可推導(dǎo)出以下結(jié)論:

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

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

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

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

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

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

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

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

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

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

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

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

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

對于相交其它兩角區(qū)外界的線段，同樣可進(jìn)行類似推導(dǎo)，并得出相應(yīng)結(jié)論，在此不再描述.

2 算法描述

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

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

圖2 線段裁剪部分示例圖

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

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

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

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

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

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

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

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

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

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

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

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

如果兩端點(diǎn)p1、p2分別在線段p1p2主射線的兩側(cè)，方法為:

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

否則線段與圓形窗口無交點(diǎn)，無裁剪結(jié)果輸出，如圖2中線段h.

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

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

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

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

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

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

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

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

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

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

如果兩端點(diǎn)p1、p2分別在線段p1p2主射線的兩側(cè)，方法為:

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

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

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

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

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

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

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

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

3 結(jié)論

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

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

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

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