任意多邊形窗口的圓裁剪算法①

楊 琴,李 寧,王亮亮

1(新疆師范高等專(zhuān)科學(xué)校,烏魯木齊 830043)

2(北京郵電大學(xué)世紀(jì)學(xué)院 移動(dòng)媒體與文化計(jì)算北京市重點(diǎn)實(shí)驗(yàn)室,北京 102101)

1 引言

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

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

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

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

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

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

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

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

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

已知被裁剪圓的方程為:

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

給定直線段P1P2,端點(diǎn)坐標(biāo)分別為P1(x1,y1),P2(x2,y2),則按照逆時(shí)針?lè)较蚩偪傻玫狡鋮?shù)方程表示.不失一般性,假設(shè)有向直線段P1P2,為逆時(shí)針?lè)较?則其參數(shù)方程表示為:

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

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

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

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

其中,

令?=b2?4ac,

若?＜0,說(shuō)明方程(3)沒(méi)有解;

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

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

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

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

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

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

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

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

考慮以下情況:

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

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

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

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

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

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

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

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

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

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

(3)?ni=1

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

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

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

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

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

按照2.1節(jié)給出的直線段和圓的交點(diǎn)的求法,依次沿逆時(shí)針?lè)较蚍謩e求多邊形窗口各個(gè)邊與圓的交點(diǎn),并將其按照順序存入數(shù)組Q中,其排序具體方法為:

取出多邊形窗口的頂點(diǎn)數(shù)組P中的首邊P1P2,按照逆時(shí)針?lè)较蛞来吻蟪龆噙呅未翱诟鱾€(gè)邊PiPi+1與圓的交點(diǎn)參數(shù)序列,記為:t1,t2,···,tk(1≤k≤2m),并將其對(duì)應(yīng)的點(diǎn)Q1,Q2,···,Qk依次存入數(shù)組Q中,記Qk+1=Q1.

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

下面判斷兩個(gè)相鄰交點(diǎn)之間是圓弧連接還是線段連接:

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

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

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

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

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

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

4.2 實(shí)例仿真

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

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

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

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

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

圖3 算法框架

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

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

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

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

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

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

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

5 結(jié)論

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