楊 琴,李 寧,王亮亮

1(新疆師范高等?？茖W(xué)校,烏魯木齊 830043)

2(北京郵電大學(xué)世紀(jì)學(xué)院 移動媒體與文化計算北京市重點實驗室,北京 102101)

1 引言

在日常生活中,隨著計算機(jī)動畫、人機(jī)交互以及虛擬現(xiàn)實等技術(shù)的不斷融入,人們對計算機(jī)圖形學(xué)技術(shù)提出了更高要求.計算機(jī)圖形學(xué)研究的內(nèi)容十分廣泛,如基本圖形生成、裁剪、三維幾何造型、真實感圖形的顯示、交互技術(shù)等等.裁剪作為計算機(jī)圖形學(xué)的基礎(chǔ)操作,也是圖像處理、模式識別等問題的基礎(chǔ).

在實際應(yīng)用中,裁剪窗口可能是各種形狀,比較常用的裁剪窗口為矩形或者多邊形.目前,對裁剪算法的研究工作主要包括:矩形窗口的線裁剪[1,2]、圓裁剪[3]和多邊形裁剪[4],多邊形窗口的線裁剪[5,6]、圓的裁剪[7,8]和多邊形裁剪[9]等等.這些研究為后續(xù)的算法研究奠定的一定的基礎(chǔ).但是,由于多邊形窗口的凹凸性和無規(guī)則性,與矩形窗口內(nèi)圖形裁剪相比,多邊形窗口內(nèi)圖形裁剪更為復(fù)雜.在實際應(yīng)用中經(jīng)常會遇到關(guān)于任意多邊形窗口的圓裁剪問題,如兩個或多個實體間的碰撞、檢測等等.因此,研究多邊形窗口內(nèi)圓的裁剪問題具有重要的意義.

為了提升已有的矢量圓裁剪算法效率和減少算法對內(nèi)存占用率等問題,一種具有線性復(fù)雜度的任意多邊形窗口的矢量圓裁剪算法被提出[7],該算法結(jié)合投影和射線法的線性幾何思想,借助向量叉積和向量共線基本定理,降低了裁剪過程的運算量,提高了裁剪效率,具有較高的魯棒性和通用性.

文獻(xiàn)[8]中提出了一種任意多邊形窗口的圓裁剪算法,該算法按照逆時針方向依次求出圓與多邊形各條邊之間的交點并排序,然后借助“中點檢測法”判定相鄰兩點是線還是弧的連接,最終完成圓的裁剪.該算法在效率和穩(wěn)定性上都取得了比較理想的結(jié)果.但該算法只考慮了圓和多邊形窗口相交及圓在多邊形窗口內(nèi)的情況,并未考慮圓與多邊形窗口相離以及多邊性窗口在圓內(nèi)的情況.針對該問題,如果更加全面的討論多邊形窗口和圓的位置關(guān)系的情況下完成圓的裁剪是十分有必要的.

本文提出了一種更加有效全面的多邊形窗口的圓裁剪算法.在考慮任意多邊形窗口與圓的不同位置關(guān)系的情況下,能夠全面的分析多邊形窗口各頂點、各邊與圓之間的關(guān)系,并對其進(jìn)行了不同的裁剪.最后仿真例子驗證該方法的有效性和全面性.

2 直線段和圓的位置關(guān)系

基于任意多邊形窗口,圓的裁剪關(guān)鍵要解決以下兩個問題:

(1)圓與多邊形窗口每條直線段是否有相交;如果相交,如何求交點;

(2)圓和多邊形的位置關(guān)系如何確定.

已知被裁剪圓的方程為:

其中,圓心坐標(biāo)O為(x0,y0),半徑為r.

給定直線段P1P2,端點坐標(biāo)分別為P1(x1,y1),P2(x2,y2),則按照逆時針方向總可得到其參數(shù)方程表示.不失一般性,假設(shè)有向直線段P1P2,為逆時針方向,則其參數(shù)方程表示為:

按逆時針方向,考慮直線段和圓的位置關(guān)系,有5種可能的情況(如圖1).

圖1 直線段和圓的位置關(guān)系

確定直線段和圓的位置關(guān)系:

將(2)代入(1),化簡整理可得:

其中,

令?=b2?4ac,

若?＜0,說明方程(3)沒有解;

綜上,如果?≥0,說明方程(3)有解,則需要判斷ti(i=1,2)的取值范圍來進(jìn)一步確定直線段和圓的交點個數(shù).如果ti∈[0,1],則其對應(yīng)的點(代入方程(3)可得對應(yīng)的點的坐標(biāo))即為直線段和圓的交點,否則不是直線段和圓的交點.

3 基于多邊形窗口的圓的裁剪

給定任意多邊形窗口P1P2···Pm,Pi(xi,yi)(i=1,2,···,m)為多邊形窗口的頂點.

考慮任意多邊形窗口和被裁剪圓的位置關(guān)系,有四種可能的情況(如圖2):

圖2 多邊形窗口和圓的位置關(guān)系

3.1 x?掃描線算法判斷多邊形窗口和圓的位置關(guān)系

借助x?掃描線算法填充多邊形的基本思想,這里研究如何利用x?掃描線算法判斷多邊形窗口與圓的位置關(guān)系,其基本思想為:

從多邊形各個頂點Pi(xi,yi)(i=1,2,···,m)出發(fā),依次做平行于x軸的掃描線(方向向右),并計算每條掃描線與圓的交點個數(shù)情況ni,ni∈{0,1,2}.

考慮以下情況:

如果?ni=0或?ni=2,則說明圓在多邊形窗口外,如圖2(a);

如果ni的取值即有0也有2,則說明圓在多邊形窗口內(nèi),如圖2(b);

如果?ni=1,則說明多邊形窗口在圓內(nèi),如圖2(c);

如果ni的取值中0,1,2都有,則說明圓在多邊形窗口內(nèi),如圖2(d).

備注:借助于x?掃描線算法,不僅能夠確定多邊形窗口和圓的位置關(guān)系,而且能夠準(zhǔn)確的區(qū)分圖2所示的不同情況,對多邊形窗口和圓的位置關(guān)系給出更加準(zhǔn)確的判定.x?掃描線算法避免了由計算確定位置關(guān)系的大量計算,而且解決了由計算不能區(qū)分圖2中(a),(b),(c)中多邊形和圓位置關(guān)系判定的問題.

3.2 基于多邊形窗口的圓的裁剪.

根據(jù)3.1節(jié)基于x?掃描線算法對多邊形窗口和圓的位置關(guān)系的判斷,接下來討論確定圓關(guān)于多邊形窗口的裁剪的問題.針對以上四種不同情況進(jìn)行不同的討論:

在這種情況,被裁剪圓要么落在多邊形窗口外(如圖2(a)),則整個圓被裁剪;

(2)ni的 取值即有0也有2

在這種情況,被裁剪圓落在多邊形窗口內(nèi)(如圖2(b)),則繪制整個圓;

(3)?ni=1

在這種情況下,多邊形窗口在被裁剪圓內(nèi)(如圖2(c)),則繪制整個多邊形;

(4)ni的取值中0,1,2都有

在這種情況下,則說明多邊形窗口與圓相交(如圖2(d)).

下面針對情況(4),討論圓弧是否被裁剪:

為了方便,首先引入輸入頂點數(shù)組P(多邊形頂點)和輸出頂點數(shù)組(圓與多邊形窗口交點),輸入頂點數(shù)組P中以逆時針方向列出,即首先定義多邊形窗口頂點的首點,然后以逆時針方向?qū)⒍噙呅雾旤c依次存入數(shù)組P.

按照2.1節(jié)給出的直線段和圓的交點的求法,依次沿逆時針方向分別求多邊形窗口各個邊與圓的交點,并將其按照順序存入數(shù)組Q中,其排序具體方法為:

取出多邊形窗口的頂點數(shù)組P中的首邊P1P2,按照逆時針方向依次求出多邊形窗口各個邊PiPi+1與圓的交點參數(shù)序列,記為:t1,t2,···,tk(1≤k≤2m),并將其對應(yīng)的點Q1,Q2,···,Qk依次存入數(shù)組Q中,記Qk+1=Q1.

同時,判斷多邊形窗口的頂點Pi是否在圓內(nèi),如果在圓內(nèi),將其按照逆時針方向存入數(shù)組Q中.如果Pi?1Pi與圓有交點Qj,且Pi點在圓內(nèi),則將點Pi存入數(shù)組Q中,并將其存放在Qj后面,記為Qj+1.

下面判斷兩個相鄰交點之間是圓弧連接還是線段連接:

① 如果Qi,Qi+1為多邊形窗口中同一條直線段與圓的交點,則弧QiQj被裁剪,繪制直線段;

② 如果Qi,Qi+1為多邊形窗口中不同直線段與圓的交點,則弧QiQi+1被繪制;

③ 如果Qi,Qi+1中,一個點為多邊形窗口中一條邊與圓的交點,另一點為圓內(nèi)的多邊形頂點,則繪制直線段QiQi+1.

4 算法實現(xiàn)與實例仿真

4.1 多邊形窗口和圓的位置關(guān)系

按照上述原理,給出本文方法的基本框架,如圖3所示.

4.2 實例仿真

根據(jù)本文提出的任意多邊形窗口的圓裁剪算法的有效性和全面性,討論了圖2給出的四種多邊形窗口和圓的位置關(guān)系的情況下圓的裁剪.

圖4驗證了當(dāng)多邊形窗口和圓分離時,根據(jù)本文提出算法,得到的裁剪結(jié)果為:圓被裁減掉.

圖5驗證了當(dāng)圓在多邊形窗口內(nèi)時,根據(jù)本文提出算法,得到的裁剪結(jié)果為:繪制整個圓.

圖6驗證了當(dāng)多邊形窗口在圓內(nèi)時,根據(jù)本文提出算法,得到的裁剪結(jié)果為:繪制整個多邊形.

圖7驗證了當(dāng)多邊形窗口及圓相交時,根據(jù)本文提出算法,得到的裁剪結(jié)果為:繪制圓在多邊形窗口內(nèi)部分及新生成的圓弧.

圖3 算法框架

圖4 多邊形窗口與圓分離及裁剪結(jié)果

圖5 圓在多邊形窗口內(nèi)及裁剪結(jié)果

圖6 多邊形窗口在圓內(nèi)及裁剪結(jié)果

對于任意多邊形窗口和圓的位置關(guān)系,圖4-7中的結(jié)果驗證了本文提出方法的全面性和有效性.

相比于文獻(xiàn)[8]的算法,本文提出的算法對于圓在多邊形窗口外的情況進(jìn)行了完善,增加了多邊形窗口和圓相離及多邊形窗口在圓內(nèi)的兩種不同情況,其裁剪結(jié)果驗證了本文提出方法的全面性.

圖7 多邊形窗口與圓相交及裁剪結(jié)果

對于相鄰兩點之間是圓弧連接還是直線段連接上,文獻(xiàn)[8]中提出的“中點檢測法”需要計算兩點中點與當(dāng)前圓弧段之間的位置關(guān)系,從而確定其連接方式;本文在決定兩點之間到底是圓弧還是直線段連接的判斷只需判斷相鄰兩點及前后點之間的位置關(guān)系斷定,節(jié)省了一定的計算量.相比,本文提出方法不僅能夠全面有效地完成任意多邊形窗口內(nèi)圓的裁剪問題,而且能夠節(jié)省一定的工作量.

5 結(jié)論

本文討論了任意多邊形窗口內(nèi)圓的一種更加全面、有效地裁剪算法.其主要思想為:首先,通過x?掃描線的思想,確定由圓心出發(fā)的射線與多邊形窗口的交點個數(shù),如果交點個數(shù)為奇數(shù),說明圓在多邊形窗口內(nèi),則繪制整個圓;如果交點個數(shù)為偶數(shù),說明圓在多邊形窗口外,則整個圓被裁剪掉.其次,對于圓和多邊形窗口相交的情況,按照逆時針方向,判斷多邊形頂點是否在圓內(nèi),在圓內(nèi)存入數(shù)組Q,否則不存入;然后求出多邊形窗口每條直線段與圓的交點,并存入數(shù)組Q.最后,通過判斷兩點間的關(guān)系,決定兩點之間畫線還是畫弧,完成圓的裁剪.實驗結(jié)果表明,該方法不僅能夠全面、有效地完成任意多邊形窗口內(nèi)圓的裁剪,而且大大降低了裁剪過程中的計算量.