李曉武, 陳 平

(北京科技大學(xué) 機(jī)械工程學(xué)院, 北京 100083)

裁剪是計(jì)算機(jī)圖形學(xué)的基本問(wèn)題之一, 也是CAD軟件系統(tǒng)的一個(gè)重要圖形編輯功能, 裁剪一般是指把一個(gè)封閉區(qū)域作為裁剪窗口, 去裁剪其他圖形, 把其他圖形中不在窗口內(nèi)的部分裁剪掉, 只保留窗口內(nèi)的部分. 裁剪功能除了在CAD軟件中大量使用外, 在計(jì)算機(jī)動(dòng)畫、機(jī)器人運(yùn)動(dòng)學(xué)仿真、建筑設(shè)計(jì)、地理信息系統(tǒng)、平面繪畫、影視特技圖像處理以及模式識(shí)別等領(lǐng)域都有廣泛應(yīng)用.

目前, 裁剪算法的研究主要集中在多邊形裁剪方面, 裁剪算法比較豐富, 有適合矩形裁剪窗口的逐邊裁剪法、Liang-Barsky算法、中點(diǎn)分割算法, 適合凸多邊形裁剪窗口的線裁剪Cyrus-Beck 算法、Sutherland-Hodgman算法、外接矩形判別法和分區(qū)判斷直接裁剪法以及適合任意多邊形裁剪窗口的Weiler-Atherton雙邊裁剪算法等[1–13].

圓裁剪也是一個(gè)重要的圖形裁剪功能, 具有廣泛的應(yīng)用, 圓裁剪有兩種類型, 一是圓做裁剪窗口對(duì)各種圖形進(jìn)行裁剪, 例如圓窗口對(duì)直線段的裁剪[14–18], 二是多邊形或者其他圖形作為裁剪窗口對(duì)圓進(jìn)行裁剪, 裁剪后只保留窗口內(nèi)的圓弧部分. 在第二種圓裁剪類型中, 矩形窗口的圓裁剪在視窗顯示時(shí)應(yīng)用較多, 裁剪算法有逐邊裁剪法、區(qū)域編碼法及投影法等[19–22]. 除了矩形窗口的圓裁剪外, 在實(shí)際應(yīng)用中, 也存在任意多邊形做裁剪窗口的圓裁剪情況, 因此, 研究任意多邊形窗口的圓裁剪也具有重要的實(shí)用價(jià)值. 關(guān)于多邊形做裁剪窗口的圓裁剪, 文獻(xiàn)[23]提出了一種方法: 首先, 計(jì)算多邊形每條邊與圓的交點(diǎn), 再對(duì)交點(diǎn)在圓周方向排序, 然后再進(jìn)一步判斷相鄰交點(diǎn)間的圓弧是否在窗口內(nèi), 該方法為多邊形窗口的圓裁剪提供了一條有效的途徑, 但是, 文獻(xiàn)中的算法需要開平方計(jì)算交點(diǎn)和反三角計(jì)算檢測(cè)圓弧的可見性, 效率低且耗資源; 文獻(xiàn)[24]將圓裁剪分成相交性檢測(cè)求交點(diǎn)、點(diǎn)在多邊形內(nèi)外判斷、交點(diǎn)排序以及可見性檢測(cè)等5個(gè)步驟, 在圓與多邊形相交性檢測(cè)時(shí)利用投影和射線法相結(jié)合, 降低了運(yùn)算的耗費(fèi), 對(duì)交點(diǎn)排序和圓弧可見性檢測(cè)方法也做了相應(yīng)改進(jìn), 算法的效率相比文獻(xiàn)[23]有所提高. 文獻(xiàn)[25]提出了和文獻(xiàn)[24]類似的方法, 利用X-掃描線法分析圓與多邊形的位置關(guān)系, 再利用多邊形頂點(diǎn)與圓的相對(duì)位置對(duì)交點(diǎn)排序. 文獻(xiàn)中提出的方法, 除了細(xì)節(jié)不同外, 算法的整體思路基本上是相同的: 均是先求出多邊形與圓的交點(diǎn), 再對(duì)交點(diǎn)在圓矢量方向上排序,然后, 判斷相鄰兩個(gè)交點(diǎn)之間的圓弧段是否在多邊形裁剪窗口內(nèi)(即可見性檢測(cè)), 從而實(shí)現(xiàn)對(duì)圓的裁剪. 在上述思路中, 除了計(jì)算交點(diǎn)外, 交點(diǎn)排序和相鄰交點(diǎn)之間圓弧的可見性檢測(cè)也是非常重要的環(huán)節(jié), 文獻(xiàn)采用的交點(diǎn)排序方法有三三排序法[24]、比較頂點(diǎn)和圓心距離的排序法[25]等, 但是, 這些排序方法只適用于多邊形裁剪窗口只有外環(huán)的情況, 當(dāng)多邊形裁剪窗口除了外環(huán)外還含有一個(gè)或多個(gè)內(nèi)環(huán)多邊形時(shí), 文獻(xiàn)中的交點(diǎn)排序方法就會(huì)出錯(cuò), 則后續(xù)的圓弧可見性檢測(cè)方法也會(huì)失效, 因此, 文獻(xiàn)中的方法不適合有內(nèi)環(huán)的任意多邊形做裁剪窗口的圓裁剪情況.

筆者在進(jìn)行相關(guān)課題研究時(shí), 對(duì)任意多邊形裁剪窗口的圓裁剪問(wèn)題也進(jìn)行了探討. 通過(guò)分析發(fā)現(xiàn), 當(dāng)多邊形裁剪窗口和圓相交時(shí), 利用交點(diǎn)相對(duì)裁剪窗口的進(jìn)出點(diǎn)特性, 即可判斷圓弧段的可見性, 不需要再對(duì)圓弧的可見性單獨(dú)進(jìn)行檢測(cè), 而通過(guò)比較圓與多邊形邊所在直線相交的參數(shù)值大小就能夠直接確定交點(diǎn)的進(jìn)出點(diǎn)特性信息, 也不再需要其他額外的計(jì)算判斷.

為此, 本文提出了一種基于交點(diǎn)參數(shù)值分析的任意多邊形裁剪窗口的圓裁剪算法, 與文獻(xiàn)中的方法相比, 本算法只需對(duì)交點(diǎn)參數(shù)值進(jìn)行比較, 即可判斷出裁剪窗口內(nèi)的圓弧部分, 判斷步驟簡(jiǎn)潔明了, 效率要明顯高于文獻(xiàn)中的方法, 適用于包括含內(nèi)環(huán)多邊形在內(nèi)的任意多邊形做裁剪窗口對(duì)圓進(jìn)行裁剪的情況.

1 基于進(jìn)出點(diǎn)特性的多邊形窗口對(duì)圓裁剪

在任意多邊形裁剪窗口對(duì)多邊形的裁剪算法中, 基于交點(diǎn)進(jìn)出點(diǎn)特性的Weiler- Atherton雙邊裁剪算法是一種非常有效的解決方案, 該方法通過(guò)將兩個(gè)多邊形設(shè)置為有向多邊形, 當(dāng)兩個(gè)多邊形有交點(diǎn)時(shí), 沿著多邊形的方向, 通過(guò)判斷交點(diǎn)是進(jìn)入裁剪窗口的進(jìn)點(diǎn)還是離開裁剪窗口的出點(diǎn), 并保留進(jìn)點(diǎn)和出點(diǎn)之間的多邊形,實(shí)現(xiàn)裁剪. 該方法利用交點(diǎn)的進(jìn)出點(diǎn)特性獲得裁剪窗口內(nèi)的部分, 對(duì)多邊形裁剪窗口的圓裁剪具有借鑒意義.

圖1所示為一個(gè)多邊形裁剪窗口對(duì)圓裁剪, 其中,多邊形為P0P1P2P3P4P5P6P7P8, 順時(shí)針走向,O是被裁剪圓, 逆時(shí)針走向. 圓O與多邊形相交的交點(diǎn)為:I0、I1、I2、I3、I4和I5. 根據(jù)交點(diǎn)的進(jìn)出點(diǎn)分析方法, 沿著圓的走向, 進(jìn)入多邊形裁剪窗口內(nèi)的交點(diǎn)稱為進(jìn)點(diǎn), 離開多邊形裁剪窗口內(nèi)的交點(diǎn)稱為出點(diǎn), 由于圓本身是封閉的, 裁剪窗口的內(nèi)部區(qū)域也是連通的, 所以, 進(jìn)點(diǎn)和出點(diǎn)成對(duì)出現(xiàn), 數(shù)量相同. 沿著圓的走向, 從進(jìn)點(diǎn)到出點(diǎn)之間的圓弧位于多邊形裁剪窗口內(nèi)部, 在裁剪時(shí)應(yīng)予以保留, 從出點(diǎn)到進(jìn)點(diǎn)之間的圓弧在多邊形裁剪窗口的外部, 應(yīng)裁剪掉. 因此, 在求出多邊形裁剪窗口和圓的交點(diǎn)后, 首先, 沿著圓的走向?qū)稽c(diǎn)進(jìn)行排序,然后, 對(duì)排序后的交點(diǎn), 進(jìn)行進(jìn)點(diǎn)? 出點(diǎn)的組合, 這樣,就可以獲得多邊形裁剪窗口內(nèi)部的圓弧. 例如, 圖1中,將多邊形裁剪窗口和圓的交點(diǎn)沿著圓的逆時(shí)針走向排序, 順序 為:I0(進(jìn)點(diǎn))?I5(出點(diǎn))?I4(進(jìn)點(diǎn))?I3(出點(diǎn)) ?I2(進(jìn)點(diǎn))?I1(出點(diǎn)), 則進(jìn)點(diǎn)? 出點(diǎn)的組合為:I0?I5、I4?I3和I2?I1, 對(duì)應(yīng)這些進(jìn)點(diǎn)到出點(diǎn)之間的圓弧為裁剪后需保留的部分.

圖1中的多邊形裁剪窗口是只有一個(gè)外環(huán)的一般多邊形的情況. 下面對(duì)形狀更為復(fù)雜的含內(nèi)環(huán)的任意多邊形裁剪窗口的圓裁剪情況進(jìn)行分析.

圖1 多邊形窗口的圓裁剪進(jìn)出交點(diǎn)分析

圖2為一個(gè)含內(nèi)環(huán)的多邊形對(duì)圓進(jìn)行裁剪, 多邊形的外環(huán)頂點(diǎn)依次為P0P1P2P3P4P5P6, 外環(huán)按順時(shí)針走向, 內(nèi)環(huán)頂點(diǎn)依次為Q0Q1Q2Q3Q4, 內(nèi)環(huán)按逆時(shí)針走向,O是被裁剪圓, 逆時(shí)針走向. 圓O分別與多邊形裁剪窗口的內(nèi)外環(huán)相交, 圓與外環(huán)的交點(diǎn)以及交點(diǎn)的進(jìn)出點(diǎn)特性為:I0(進(jìn)點(diǎn))、I3(出點(diǎn))、I2(進(jìn)點(diǎn))和I1(出點(diǎn)),圓與內(nèi)環(huán)的交點(diǎn)以及交點(diǎn)的進(jìn)出點(diǎn)特性為:I4(出點(diǎn))和I5(進(jìn)點(diǎn)). 沿著圓的逆時(shí)針走向, 對(duì)所有交點(diǎn)進(jìn)行排序, 順序?yàn)?I0(進(jìn) 點(diǎn))?I4(出 點(diǎn))?I5(進(jìn) 點(diǎn))?I3(出點(diǎn)) ?I2(進(jìn)點(diǎn))?I1( 出點(diǎn)). 則排序后的交點(diǎn)進(jìn)行進(jìn)點(diǎn)?出點(diǎn)組合為:I0?I4、I5?I3和I2?I1, 對(duì)應(yīng)這些進(jìn)點(diǎn)到出點(diǎn)之間的圓弧也為裁剪后需保留的部分.

圖2 含內(nèi)環(huán)的任意多邊形裁剪窗口的圓裁剪

因此, 利用交點(diǎn)的進(jìn)出點(diǎn)特性也可以實(shí)現(xiàn)對(duì)含內(nèi)環(huán)多邊形在內(nèi)的任意多邊形裁剪窗口的圓裁剪.

本裁剪算法的步驟歸納如下:

第1步. 依次判斷多邊形外環(huán)和內(nèi)環(huán)的每條邊與圓是否相交, 如相交, 則計(jì)算交點(diǎn);

第2步. 判斷交點(diǎn)是進(jìn)點(diǎn)還是出點(diǎn), 并在交點(diǎn)信息中記錄其進(jìn)出點(diǎn)特性;

第3步. 沿圓的走向?qū)⒔稽c(diǎn)進(jìn)行排序;

第4步. 根據(jù)交點(diǎn)的進(jìn)出點(diǎn)特性, 將排序后的交點(diǎn)進(jìn)行進(jìn)點(diǎn)? 出點(diǎn)組合, 保留進(jìn)點(diǎn)? 出點(diǎn)之間對(duì)應(yīng)的圓弧.

2 交點(diǎn)進(jìn)出點(diǎn)特性和直線參數(shù)的關(guān)系

在上述的裁剪算法中, 判斷交點(diǎn)的進(jìn)出點(diǎn)特性是整個(gè)算法的關(guān)鍵. 對(duì)于多邊形裁剪窗口對(duì)多邊形的裁剪, 可以通過(guò)被裁剪邊的兩個(gè)頂點(diǎn)和裁剪邊的相對(duì)位置關(guān)系來(lái)判斷交點(diǎn)是進(jìn)點(diǎn)還是出點(diǎn), 但是對(duì)于圓裁剪,由于圓本身沒有頂點(diǎn), 所以, 不能再借鑒多邊形的進(jìn)出點(diǎn)判斷法來(lái)分析圓與多邊形交點(diǎn)的進(jìn)出點(diǎn)特性, 因此,還需要尋找新的方法來(lái)判斷交點(diǎn)的進(jìn)出點(diǎn)信息.

設(shè)線段P0P1是多邊形裁剪窗口的一條邊, 兩個(gè)端點(diǎn)分別為P0(x0,y0) 和P1(x1,y1) , 邊的方向是P0指 向P1,則該邊所在直線的參數(shù)方程表示為:

如圖3所示, 參數(shù)將邊所在直線劃分為3個(gè)區(qū)域:(-∞,0)、 [ 0,1]和 ( 1,+∞), 其中, 當(dāng)參數(shù)值t∈[0,1]時(shí), 對(duì)應(yīng)直線上的點(diǎn)在P0和P1之間的線段上, 即在多邊形的邊上, 而且參數(shù)值從P0到P1逐 漸增大; 當(dāng)t?[0,1]時(shí), 對(duì)應(yīng)直線上點(diǎn)不在P0和P1之間的線段上, 而是在該線段兩側(cè)的延長(zhǎng)線上; 當(dāng)t＜0 時(shí), 點(diǎn)在P1指 向P0的線段延長(zhǎng)線上,t值越來(lái)越小, 當(dāng)t＞1時(shí) , 點(diǎn)在P0指 向P1的線段延長(zhǎng)線上,t值越來(lái)越大, 也即直線上的點(diǎn)在沿著P0指 向P1的方向上, 對(duì)應(yīng)的參數(shù)值t越來(lái)越大, 反之, 參數(shù)值t越來(lái)越小.

圖3 邊所在直線的參數(shù)表示

設(shè)多邊形為有向多邊形, 其中, 外環(huán)為順時(shí)針走向,內(nèi)環(huán)為逆時(shí)針走向, 則多邊形內(nèi)部所在區(qū)域具有這樣的特點(diǎn): 不管是外環(huán)邊還是內(nèi)環(huán)邊, 沿著邊的走向前進(jìn),即沿著P0點(diǎn) 指向P1點(diǎn)的方向前進(jìn), 這時(shí), 邊的右側(cè)均為多邊形的內(nèi)側(cè)區(qū)域. 即使多邊形的各邊具有不同的傾斜方向, 該特點(diǎn)仍然存在, 如圖4所示.

圖5所示是多邊形的一個(gè)邊所在直線與圓相交的情況, 圓的走向是逆時(shí)針, 邊直線的方向是P0點(diǎn)指向P1點(diǎn), 則沿著直線走向的右側(cè)是多邊形的內(nèi)側(cè)區(qū)域. 若圓與直線P0P1相 交, 交點(diǎn)記為I0和I1, 則從圖中可以看到, 圓在交點(diǎn)I0處進(jìn)入多邊形內(nèi)側(cè)區(qū)域, 即I0為進(jìn)點(diǎn), 在交點(diǎn)I1處 離開多邊形內(nèi)側(cè)區(qū)域, 即I1為 出點(diǎn), 設(shè)交點(diǎn)I0和I1在 直線的參數(shù)方程式(1)中對(duì)應(yīng)的參數(shù)值分別為t0和t1, 這時(shí), 參數(shù)值t0和t1的大小關(guān)系是:

圖5 有向邊直線和圓相交

式(2)也是圖4中有向邊所在直線第一種傾斜情況下, 和圓相交時(shí)交點(diǎn)的進(jìn)出點(diǎn)特性和交點(diǎn)在直線上參數(shù)值大小的對(duì)應(yīng)關(guān)系.

圖4 有向邊的右側(cè)為多邊形內(nèi)側(cè)區(qū)域

圖6是圖4中有向邊所在直線的另外3種傾斜方向下和逆時(shí)針走向圓相交的情況, 直線的方向是P0點(diǎn)指向P1點(diǎn) ,I0和I1是 兩個(gè)交點(diǎn), 其中,I0為進(jìn)點(diǎn),I1為出點(diǎn),從圖6也可以得出和圖5相同的結(jié)論: 沿著邊所在直線的走向, 如果右側(cè)是多邊形裁剪窗口的內(nèi)側(cè)區(qū)域, 圓沿逆時(shí)針走向, 圓和直線相交的兩個(gè)交點(diǎn)分別是進(jìn)點(diǎn)和出點(diǎn), 則進(jìn)點(diǎn)在直線上的參數(shù)值小于出點(diǎn)在直線上的參數(shù)值, 即進(jìn)點(diǎn)和出點(diǎn)在直線上的參數(shù)值具有和式(2)相同的大小關(guān)系.

圖6 各種傾斜位置有向邊直線和圓相交

因此, 圓和多邊形裁剪窗口相交時(shí)交點(diǎn)的進(jìn)出點(diǎn)特性, 通過(guò)判斷交點(diǎn)在對(duì)應(yīng)邊所在直線的參數(shù)值大小即可確定下來(lái), 這樣, 就利用第1節(jié)提出的基于交點(diǎn)進(jìn)出點(diǎn)特性的多邊形窗口的圓裁剪算法, 即可實(shí)現(xiàn)對(duì)圓的裁剪.

3 圓與邊所在直線的交點(diǎn)計(jì)算及處理

上述的圓與多邊形邊相交是指圓與多邊形邊所在直線相交, 這時(shí), 交點(diǎn)可能在多邊形的邊上, 也可能在邊的延長(zhǎng)線上. 只有落在多邊形的實(shí)際邊上而不是在其延長(zhǎng)線上的交點(diǎn)才用于裁剪, 這個(gè)交點(diǎn)稱為實(shí)交點(diǎn),在邊的延長(zhǎng)線的交點(diǎn)稱為虛交點(diǎn). 當(dāng)邊與圓沒有實(shí)交點(diǎn)時(shí), 圓和該邊不存在裁剪, 不必計(jì)算. 只有存在實(shí)交點(diǎn)時(shí), 才計(jì)算交點(diǎn)的參數(shù)值, 并比較大小, 判斷該實(shí)交點(diǎn)是進(jìn)點(diǎn)還是出點(diǎn).

判斷直線與圓是否存在交點(diǎn)的方法如下:

設(shè)圓的半徑是R, 圓心為Pc(xc,yc), 逆時(shí)針方向, 圓方程為:

將式(1)中的直線參數(shù)化表示代入式(3)中, 建立參數(shù)t的一元二次方程. 該方程的解為:

其中,

令Δ=B2-4AC, 則t=

當(dāng)Δ ＜0時(shí), 方程無(wú)解, 即直線和圓沒有交點(diǎn).

當(dāng)Δ =0時(shí), 方程只有一個(gè)解, 即直線和圓相切, 此時(shí)也不必考慮裁剪.

當(dāng)Δ ＞0時(shí), 直線與圓有兩個(gè)交點(diǎn), 這時(shí)需進(jìn)一步判斷是否存在實(shí)交點(diǎn), 當(dāng)有實(shí)交點(diǎn)時(shí), 計(jì)算方程的兩個(gè)解t1和t2:

由于t1＜t2, 所以,t1對(duì)應(yīng)的交點(diǎn)為圓在直線上的進(jìn)點(diǎn),t2對(duì)應(yīng)的交點(diǎn)為圓在直線上的出點(diǎn).

當(dāng)0≤t1,t2≤1時(shí) , 則t1和t2對(duì)應(yīng)的兩個(gè)交點(diǎn)均為實(shí)交點(diǎn), 將t1和t2代入式(1), 即得交點(diǎn)值, 將兩個(gè)交點(diǎn)插入交點(diǎn)序列中, 并標(biāo)識(shí)每個(gè)交點(diǎn)的進(jìn)出點(diǎn)特性.

當(dāng)t1和t2中僅有一個(gè)值在[ 0,1] 區(qū) 間時(shí), 則在[ 0,1]區(qū)間的t值對(duì)應(yīng)的交點(diǎn)為實(shí)交點(diǎn), 將該交點(diǎn)插入交點(diǎn)序列中, 并標(biāo)識(shí)其進(jìn)出點(diǎn)特性.

4 圓周方向交點(diǎn)排序

所有的實(shí)交點(diǎn)沿著圓周方向排序是實(shí)現(xiàn)裁剪的重要一步. 文獻(xiàn)中的交點(diǎn)排序方法是比較每個(gè)點(diǎn)在圓的逆時(shí)針方向?qū)?yīng)的圓弧角大小, 需要進(jìn)行反三角運(yùn)算,比較耗性能. 由于所有的交點(diǎn)都在圓上, 所以, 本文采用比較交點(diǎn)與 (R,0) 或 者( -R,0)距離的方法進(jìn)行排序,如圖7所示.

圖7 圓周方向交點(diǎn)排序

當(dāng)交點(diǎn)的坐標(biāo)值y≥0 (即交點(diǎn)在圓上0°到180°之間)時(shí), 按交點(diǎn)到(R,0)的距離大小排序:

當(dāng)交點(diǎn)坐標(biāo)值y＜0 (即交點(diǎn)在圓上180°到360°之間)時(shí), 按交點(diǎn)到圓上( -R,0) 的距離大小排序:

然后, 將兩組交點(diǎn)序列合在一起, 獲得所有交點(diǎn)的排序.

5 算法實(shí)例及與文獻(xiàn)算法的分析比較

為了驗(yàn)證本文提出的基于交點(diǎn)參數(shù)的多邊形裁剪窗口的圓裁剪方法, 筆者在Visual C++平臺(tái)下進(jìn)行了圖形編程, 在生成直線、圓、圓弧以及各種類型多邊形的基礎(chǔ)上, 實(shí)現(xiàn)了本文第1節(jié)提出的基于交點(diǎn)進(jìn)出點(diǎn)特性的多邊形窗口的圓裁剪算法, 在算法中, 利用第3節(jié)的方法計(jì)算多邊形邊與圓的交點(diǎn), 交點(diǎn)的進(jìn)出點(diǎn)特性則根據(jù)第2節(jié)提出的交點(diǎn)所在邊直線的參數(shù)判斷,并按第4節(jié)的方法在圓周方向?qū)稽c(diǎn)進(jìn)行排序.

圖8和圖9是利用本算法實(shí)現(xiàn)的裁剪效果實(shí)列,其中, 圖8是僅有外環(huán)多邊形裁剪窗口對(duì)圓的裁剪, 其中, 圖8(a)是裁剪前的多邊形裁剪窗口和被裁剪的圓,圖8(b)是裁剪后效果. 圖9是帶內(nèi)環(huán)的多邊形裁剪窗口對(duì)圓的裁剪, 其中, 圖9(a)是裁剪前的多邊形裁剪窗口和被裁剪的圓, 圖9(b)是裁剪后效果. 圖8和圖9中的多邊形均通過(guò)隨機(jī)交互方式構(gòu)造生成, 無(wú)任何特殊設(shè)定, 裁剪結(jié)果證實(shí)本文提出的算法是切實(shí)可行的.

圖8 僅有外環(huán)的多邊形裁剪窗口的圓裁剪

圖9 帶內(nèi)環(huán)的多邊形裁剪窗口的圓裁剪

本實(shí)驗(yàn)中采用的直線、多邊形、圓以及圓弧這些圖形的生成方法均為筆者自己開發(fā)的算法實(shí)現(xiàn), 沒有借助Visual C++平臺(tái)或者其他如OpenGL圖形庫(kù)現(xiàn)有的繪圖函數(shù)生成, 為了說(shuō)明本文算法的效率和性能, 下面列出本文方法和文獻(xiàn)方法在步驟上的區(qū)別比較.

表1是本文算法與文獻(xiàn)算法的比較. 其中, 在判斷和計(jì)算裁剪邊界直線和圓的交點(diǎn)時(shí), 本文算法的時(shí)間復(fù)雜度是 O (n) , 其中n為多邊形的邊的數(shù)量, 空間復(fù)雜度為O (k), 其中k為實(shí)交點(diǎn)的數(shù)量, 對(duì)交點(diǎn)排序時(shí)的復(fù)雜度為O (k), 空間復(fù)雜度為O (1), 也即本文和文獻(xiàn)在共有的算法步驟中的時(shí)間復(fù)雜度和空間復(fù)雜度是相同的.但是, 除了共有的步驟外, 文獻(xiàn)算法還需要其他步驟才能實(shí)現(xiàn), 而本文的算法, 僅根據(jù)交點(diǎn)在多邊形邊所在直線的參數(shù)值大小, 判斷出交點(diǎn)的進(jìn)出點(diǎn)特性, 即可進(jìn)行裁剪, 不需要太多步驟, 因此效率更高. 另外, 文獻(xiàn)也沒有考慮多邊形裁剪窗口帶內(nèi)環(huán)的情況, 本文算法不僅適用于僅有外環(huán)的一般多邊形裁剪窗口, 也適用于帶內(nèi)環(huán)的任意多邊形裁剪窗口的圓裁剪, 因此, 算法更具有通用性.

表1 本文算法和文獻(xiàn)算法[23–25]的比較

6 結(jié)論

本文提出了一種基于交點(diǎn)參數(shù)信息分析的任意多邊形裁剪窗口的圓裁剪算法, 在計(jì)算多邊形邊與圓交點(diǎn)的同時(shí), 通過(guò)交點(diǎn)在邊所在直線的參數(shù)信息, 即可識(shí)別出交點(diǎn)的進(jìn)出點(diǎn)特性, 從而實(shí)現(xiàn)對(duì)圓的裁剪. 與文獻(xiàn)中的方法相比較, 本算法步驟較少, 編程實(shí)例結(jié)果也驗(yàn)證了本文算法的可行性. 本文的算法不僅對(duì)僅有外環(huán)的一般多邊形裁剪窗口的圓裁剪適用, 也適用于帶內(nèi)環(huán)的任意多邊形裁剪窗口的圓裁剪.