計(jì)算機(jī)圖形學(xué)(簡(jiǎn)單多邊形裁剪算法)

1、 簡(jiǎn)單多邊形裁剪算法摘要：多邊形裁剪算法與線性裁剪算法具有更廣泛的實(shí)用意義，因此它是目前裁剪研究的主要課題。本文主要介紹了一種基于多邊形頂點(diǎn)遍歷的簡(jiǎn)單多邊形裁剪算法，它有效降低了任意多邊形裁剪復(fù)雜度。通過記錄交點(diǎn)及其前驅(qū)、后繼信息，生成結(jié)果多邊形，該算法簡(jiǎn)化了交點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，節(jié)省了存儲(chǔ)空間，降低了算法的時(shí)間復(fù)雜度，具有簡(jiǎn)單、易于編程實(shí)現(xiàn)、運(yùn)行效率高的特點(diǎn)。關(guān)鍵詞：多邊形裁剪；交點(diǎn)；前驅(qū)；后繼；矢量數(shù)組一、技術(shù)主題的基本原理 簡(jiǎn)單多邊形裁剪算法綜合考慮現(xiàn)有多邊形裁剪算法的優(yōu)缺點(diǎn)，它是一種基于多邊形頂點(diǎn)遍歷來實(shí)現(xiàn)簡(jiǎn)單多邊形裁剪工作的。其主要的原理是遍歷多邊形并把多邊形分解為邊界的線段逐段進(jìn)行裁剪，

2、輸出結(jié)果多邊形。二、發(fā)展研究現(xiàn)狀近年來,隨著遙感繪圖、cad輔助設(shè)計(jì)、圖象識(shí)別處理技術(shù)的發(fā)展,圖形裁剪算法從最初在二維平面上線和圖形的裁剪擴(kuò)展到三維空間里體和場(chǎng)的裁剪,國(guó)內(nèi)外相繼提出不少行之有效的算法,但越來越復(fù)雜的圖形和計(jì)算也對(duì)算法的速度和適用性提出了越來越高的要求。因此,不斷簡(jiǎn)化算法的實(shí)現(xiàn)過程,完善細(xì)節(jié)處理,滿足大量任意多邊形的裁剪也就成了當(dāng)今算法研究的焦點(diǎn)之一。 以往多邊形裁剪算法不是要求剪裁多邊形是矩形，就是必須判斷多邊形頂點(diǎn)的順時(shí)針和逆時(shí)針性，即存在不實(shí)用或者是增加了多邊形裁剪算法的難度。為了解決現(xiàn)在的問題，我們研究現(xiàn)在的新多邊形算法，其中，裁剪多邊形和被裁剪多邊形都可以是一般多邊形

3、，且不需要規(guī)定多邊形輸入方向。它采用矢量數(shù)組結(jié)構(gòu)，只需遍歷剪裁多邊形和被裁剪多邊形頂點(diǎn)即完成多邊形的裁剪，具有算法簡(jiǎn)單、運(yùn)行效率高的特點(diǎn)。三、新算法設(shè)計(jì)1、算法的思想 本算法是為了盡量降低任意多邊形裁剪算法復(fù)雜度而提出的，其主要思想是采用矢量數(shù)組結(jié)構(gòu)來遍歷裁剪多邊形和被裁多邊形頂點(diǎn)，記錄裁剪多邊形和被裁減多邊形交點(diǎn)及其前驅(qū)、后繼信息，并通過記錄相鄰交點(diǎn)的線段，然后通過射線法選擇滿足條件的線段，之后進(jìn)行線段連接，輸出對(duì)應(yīng)的裁剪結(jié)果。算法數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，即沒有用常用的數(shù)據(jù)結(jié)構(gòu)，如線性鏈表結(jié)構(gòu)、雙向鏈表結(jié)構(gòu)和樹形結(jié)構(gòu)，這樣就節(jié)省了存儲(chǔ)空間，增加算法的效率。2、主要數(shù)據(jù)結(jié)構(gòu)多邊形裁剪算法的核心是數(shù)據(jù)結(jié)構(gòu)

4、，它決定了算法的復(fù)雜度和計(jì)算效率。兼顧數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單和節(jié)省存儲(chǔ)空間的目的，簡(jiǎn)單多邊形裁剪算法是基于矢量數(shù)組vector的數(shù)據(jù)結(jié)構(gòu)進(jìn)行裁剪的，多邊形矢量數(shù)組的每個(gè)元素表示多邊形頂點(diǎn)，且按頂點(diǎn)輸入的順序存儲(chǔ)。裁剪多邊形和被裁剪多邊以下我們分別用s和c表示，其涉及的數(shù)據(jù)結(jié)構(gòu)主要如下：1）頂點(diǎn)或交點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：vertex=double x，y；bool islnpolygon；說明：vertex用來存儲(chǔ)多邊形的頂點(diǎn)或交點(diǎn)，x，y表示頂點(diǎn)的坐標(biāo)，isinpolygon為true表示該點(diǎn)在多邊形內(nèi)部或在多邊形邊上，否則，表示該點(diǎn)在多邊形外部。2）交點(diǎn)的前驅(qū)后繼數(shù)據(jù)結(jié)構(gòu)如下： crosspointindex

5、int npredecessorlndex=0前驅(qū)序號(hào)int nsuccessorindex=0后繼序號(hào)說明：crosspointindex用于記錄交點(diǎn)在多邊形中的前驅(qū)與后繼的序號(hào)信息，以及記錄同一交點(diǎn)在兩個(gè)多邊形中頂點(diǎn)序號(hào)。即若p為多邊形s與多邊形c的交點(diǎn)，為了表示p在s和c中為同一點(diǎn)，則可用crosspointindex記錄用npredecessorindex記錄p在s中的序號(hào)、用nsuccessorindex記錄p在c中序號(hào)。3）線段的數(shù)據(jù)結(jié)構(gòu)如下：segmentint nstartindex=0int nendindex=0int* pindexes;int nindexcount;說

6、明：segment表示多邊形在另一個(gè)多邊形內(nèi)(外)的線段，nstartaindex為segment起始頂點(diǎn)的序號(hào)，nendindex為segment終止頂點(diǎn)的序號(hào)，pindexes為起始頂點(diǎn)與終止頂點(diǎn)之間的頂點(diǎn)序號(hào)集合，nindexcount為pindexes中元素個(gè)數(shù)。3、算法設(shè)計(jì)1）第一階段：采用射線法計(jì)算并判斷s（或c）在c（或s）內(nèi)，并修改s（或c）頂點(diǎn)vertex的isinpolygon的值。由于射線可以任意選取，為了方便可以將射線定為從被測(cè)點(diǎn)開始射向x軸坐標(biāo)正方向的水平射線。由于多邊形的一條邊與射線的交點(diǎn)最為1個(gè)，因此可以循環(huán)遍歷每條邊并判斷邊與射線有無交點(diǎn)，若有交點(diǎn)，計(jì)數(shù)器加1,

7、。最后得到的計(jì)數(shù)器的值即多邊形與射線的交點(diǎn)個(gè)數(shù)。若交點(diǎn)個(gè)數(shù)為奇數(shù)，則被測(cè)點(diǎn)在多邊形內(nèi)部，若交點(diǎn)個(gè)數(shù)為偶數(shù)，則被測(cè)點(diǎn)在多邊形外部。對(duì)于多邊形的任意一條邊，為了盡量避免求交點(diǎn)時(shí)用到乘除法，將判斷該邊與射線有無交點(diǎn)的算法可以包含3步：1) 判斷邊的兩個(gè)頂點(diǎn)是否均在被測(cè)點(diǎn)左方或者下方或者上方，若是則無交點(diǎn)，返回假并退出；2) 若不滿足第一條原則，且滿足兩個(gè)頂點(diǎn)均在被測(cè)點(diǎn)右方，則一定有頂點(diǎn)，返回真并退出；3) 若以上兩條都不滿足，求出邊與射線的交點(diǎn)，比較交點(diǎn)的x坐標(biāo)與被測(cè)點(diǎn)的x坐標(biāo)，若前者大于后者則返回真并退出，否則返回假并退出。設(shè)邊的兩個(gè)頂點(diǎn)坐標(biāo)分別為（x1,y1）和（x2,y2）,則邊的直線方程可寫

8、為： x=m(y-y1)+x1其中，m=（x2-x1）/(y2-y1)為直線斜率的倒數(shù)。使用該方程時(shí)需要兩次乘除法，效率較低。為了盡量避免求交點(diǎn)，第三部可以采用二分法將邊分成兩段，對(duì)其中兩個(gè)端點(diǎn)分別跨過射線兩側(cè)的邊段重新進(jìn)行以上第一步和第二步的判斷，若以上兩步中還沒有推出，再繼續(xù)二分，直到能夠被第一步和第二步判斷并退出。采用二分法則避免了乘除法，算法中只有除2運(yùn)算和一些判斷，適合于硬件處理，二分法的循環(huán)次數(shù)一般較少，當(dāng)被測(cè)點(diǎn)位于邊上時(shí)，循環(huán)次數(shù)組最多。其具體的算法如下：（point為被測(cè)點(diǎn)變量，point1、point2為一條邊的兩個(gè)端點(diǎn)變量） if(piont2.ypoint.y|p2.yp

9、oint.y) /兩個(gè)端點(diǎn)都在被測(cè)點(diǎn)上方或者下方return false;/無交點(diǎn)else if(p1.xpoint.x&p2.xpoint.x&p2.xpoint.x）return true；有交點(diǎn)count+；else m=mypoint(p1.x+p2.x)/2,(p1.y+p2.y)/2)/得到邊的中點(diǎn)if（m.ypoint.y）p2=m;else p1=m;if(p2.xp1.x) /當(dāng)p2在p1的右方時(shí)if（p2.xpoint.x）/當(dāng)p1在被測(cè)點(diǎn)右方時(shí)，有交點(diǎn) return true;count+； else /當(dāng)p2在p1右方時(shí)if（p1.xpoint.x)/當(dāng)p2在被測(cè)點(diǎn)右方

10、時(shí)，有交點(diǎn)return true;count+ ;count+開始此點(diǎn)作一x軸正向射線選擇一條邊射線與此邊有無交點(diǎn)是否多邊形另一條邊count數(shù)值是奇數(shù)？isinpolygon=trueisinpolygon=false下一個(gè)被測(cè)點(diǎn)結(jié)束是否流程圖如圖1： 圖1.射線法判斷點(diǎn)的位置2）第二階段 按正方向遍歷s與c，計(jì)算s與c的交點(diǎn)集，交點(diǎn)的前驅(qū)后繼信息、交點(diǎn)在s和c中的對(duì)應(yīng)關(guān)系，以及相交多邊形弧段集；步驟1：按正向方向遍歷s與c并計(jì)算交點(diǎn)集vectorcrosspointset,同時(shí)生成交點(diǎn)在s和c中前驅(qū)，后繼信息vectorcrosspointindexsets和vectorcrosspoin

11、tindexsetc.其中，crosspointset中元素isinpolygon的值為true。步驟2 ;判斷crosspointindexsets或crosspointindexsetc中首尾元素的npredecessorindex與nsuccessorindex值是否相等。若想等，則將尾部元素放置到首部位置。重復(fù)判斷操作，直到首尾元素值不相等為止。步驟3：按倒序?qū)rosspointindexsets和crosspointindexsetc中元素插入到s和czhong ,計(jì)算原多邊形頂點(diǎn)的序號(hào)信息，并建立交點(diǎn)在兩個(gè)多邊形中頂點(diǎn)序號(hào)關(guān)系集合。 假設(shè)插入交點(diǎn)后的s和c成為s和c。插入同時(shí)，建

12、立交點(diǎn)在s和c中頂點(diǎn)序號(hào)對(duì)應(yīng)集合 vectorcorrespondingcrosspointlndexset，并用npredecessorlndex記錄s中頂點(diǎn)序號(hào)、nsuccessorlndex記錄c中頂點(diǎn)序號(hào)。其中，以crosspointlndexsets和crosspointlndexsetc中前驅(qū)序號(hào)為0的元素開始，交點(diǎn)序號(hào)在前驅(qū)序號(hào)的基礎(chǔ)上順序遞增。根據(jù)交點(diǎn)的前驅(qū)后繼集合信息，s和c點(diǎn)在s和c中的序號(hào)具有如下變化規(guī)律：npredecessorindex0=0successorlndexi=npredecessorlndexi+ni+1npredecessorindexi+1=nsuc

13、cessorindexi+1in,n為原多邊形頂點(diǎn)數(shù)式中：npredecessorlndexi、nsuccessorindexis、c序號(hào)為i的頂點(diǎn)在s和c中序號(hào)，nis和c中序號(hào)為i與i+1之間的交點(diǎn)個(gè)數(shù)步驟4 :釋放crosspointindexsets和crosspointindexsetc空間，修改交點(diǎn)對(duì)應(yīng)集合correspondingcrosspointindexset的元素值。步驟5 :按正方向分別連接s和c中vertex的isinpolygon為true且相鄰的頂點(diǎn)，生成線段集vectorsegmentsets和vectorsegmentsetc.步驟6 遍歷segmentset

14、s元素并取第i號(hào)元素的中點(diǎn)pi，采用射線法判斷pi是否在c中，若不在c中，則刪除segmentsets中第i號(hào)元素。同理，刪除segmentsetc中元素的中點(diǎn)不在s中的項(xiàng)，步驟7 分別合并segmentsets和segmentsetc中為相鄰元素。流程圖如圖2 第二階段流程。第三階段 對(duì)弧段集進(jìn)行合并，生成并輸出結(jié)果多邊形。即：遍歷segmentsets和segmentsetc,利用correspondingcrosspointindexset交點(diǎn)在s和c的對(duì)應(yīng)關(guān)系，將s和c互為相鄰邊或相交的線段連接起來。若segmentsets中某元素和segmentsetc中某元素的值相等或者交叉相等，

15、則表示為閉合多邊形。將尾部元素放置到首部位置取交點(diǎn)集下一條元素開始正向遍歷s與c并計(jì)算交點(diǎn)集crosspointset,生成前驅(qū)、后繼信息并令isinpolygon為true判斷交點(diǎn)集中首尾元素是否相等？按倒序?qū)⒔稽c(diǎn)集中元素插入到s和c中，建立多邊形頂點(diǎn)序號(hào)關(guān)系釋放交點(diǎn)集的空降，修改頂點(diǎn)序號(hào)集合中元素值按正向連接s和c中isinpolygon為true的相鄰點(diǎn)，生成線段集是否遍歷線段集中元素，取線段i中點(diǎn)pp在c中或p在s中？刪除線段集中第i號(hào)元素分別合并s和c中為相鄰元素結(jié)束 圖2 第二階段流程線段連接算法如下：int i,j;while（isegmentsets.size()） segem

16、nt seg1=segmentsetsi+;int nstart=seg1.nstartindex;int nend=seg1.nendindex;for(j=0;jcorrespondingcrosspointindexset.size();j+)遍歷crossespondingcrosspointindexset,得到與s的nstart、nend序號(hào)相等頂點(diǎn)的c序號(hào)，用nstart和nend記錄與s頂點(diǎn)相應(yīng)的c頂點(diǎn)序號(hào)。此處，可以刪除滿足條件的correspondingcross pointindexset,減少下次循環(huán)次數(shù) for(j=0；jpolygon2segments.count；

17、j+)segments seg2=segmentsetcj；segments seg3=segmentsetcj+1；if(nstart=seg2.nstartindex&nend=seg2.nendindex)若線段segl的起始節(jié)點(diǎn)與seg2的起始節(jié)點(diǎn)、segl的終止節(jié)點(diǎn)與seg2的終止節(jié)點(diǎn)相等，表示線段segl與seg2組成為一個(gè)相交多邊形，那么只需將seg2中點(diǎn)倒序加入到segl點(diǎn)的后面即可，即點(diǎn)的順序?yàn)椋簊egl起始點(diǎn)segl中間點(diǎn)(順序)segl終止點(diǎn)seg2中間點(diǎn)(倒序)。其中，括號(hào)中倒序則是按pindexes元素序號(hào)從小到大的先后順序插入，括號(hào)中的倒序則是按plndexes元素

18、序號(hào)從大到小的順序插入。后面的意義相同。else if(nstart=seg2.nendindex&nend=seg2.nstartlndex) 若線段segl的起始節(jié)點(diǎn)與seg2的終止節(jié)點(diǎn)、segl的終止節(jié)點(diǎn)與seg2的起始節(jié)點(diǎn)相等，表示線段seg1與seg2組成為相交多邊形，那么只需將seg2中的點(diǎn)順序加入到seg1點(diǎn)的后面即可，即點(diǎn)的順序?yàn)椋簊eg1的起始點(diǎn)seg1中間點(diǎn)（順序）seg1終止點(diǎn)seg2中間點(diǎn)（順序）。else if(nstart=seg2.nendindex&nend=seg3.nstartindex)若線段seg1的起始節(jié)點(diǎn)與seg2的終止節(jié)點(diǎn)與seg3的起始節(jié)點(diǎn)相等，

19、表示線段seg2-seg1-seg3為相交多邊形的一部分，那么只需把線段seg1和seg3頂點(diǎn)和中間點(diǎn)追加到線段seg2后面即可，點(diǎn)的操作順序?yàn)椋簊eg1起始點(diǎn)（或seg2終止點(diǎn)）-seg1中間點(diǎn)（順序）-seg1終止點(diǎn)（或seg3起始點(diǎn)）-seg3中間點(diǎn)（順序）。同時(shí)，將seg3從segmentsetc中刪除。else if(nstart=seg2.nstartindex&nend=seg3.nendindex) 若線段segl的起始節(jié)點(diǎn)與seg2的起始節(jié)點(diǎn)、segl的終止節(jié)點(diǎn)得到與seg3的終止節(jié)點(diǎn)相等，表示線段seg3一seglse92為相交多邊形的一部分，那么只需把線段segl和seg

20、2頂點(diǎn)和中間點(diǎn)追加到線段seg3后面即可，點(diǎn)的操作順序?yàn)?seg1終止點(diǎn)（或seg3終止點(diǎn)）seg1中間點(diǎn)（倒序）seg起始點(diǎn)（或seg2起始點(diǎn)）seg2中間點(diǎn)（順序）。同時(shí)，將seg2從segmentsetc中刪除。 至此算法結(jié)束，即可輸出結(jié)果多邊形。流程圖如圖3第三階段流程jcorrespondingcrosspointset.size()遍歷頂點(diǎn)對(duì)應(yīng)集合，得到與s的起始點(diǎn)相同的c中對(duì)應(yīng)的序號(hào)，并刪除頂點(diǎn)對(duì)應(yīng)集合中滿足條件的元素j=j+1開始i=0，j=0isegmentsets.size()seg1=segmentsetsi+nstart=seg1.nstartindexnend=seg

21、1.nendindexj=0i=i+1 將seg2中的點(diǎn)倒敘加入seg1點(diǎn)后面是是否是將seg1和seg3頂點(diǎn)和中間點(diǎn)追加到線段seg2后面，同時(shí)將seg3從segmentsetc中刪除否nstart=seg2.nstartindex&nend=seg3.nendindex?將seg1和seg2頂點(diǎn)和中間點(diǎn)追加到線段seg3后面，將seg2從segmentsetc中刪除將seg2中點(diǎn)順序加入到seg1點(diǎn)的后面nstart=seg2.nendindex&nend=seg2.nstartindex?nstart=seg2.nendindex&nend=seg3.nstartindex?是否jpol

22、ygon2segments.count?j =0seg2=segmentsetciseg3=segmentsetj+1nstart=seg2.nstartindex &nend=seg2.nendindex?輸出結(jié)果多邊形結(jié)束將seg2中的點(diǎn)倒敘加入seg1點(diǎn)后面是是否是將seg1和seg3頂點(diǎn)和中間點(diǎn)追加到線段seg2后面，同時(shí)將seg3從segmentsetc中刪除否nstart=seg2.nstartindex&nend=seg3.nendindex?將seg1和seg2頂點(diǎn)和中間點(diǎn)追加到線段seg3后面，將seg2從segmentsetc中刪除將seg2中點(diǎn)順序加入到seg1點(diǎn)的后面n

23、start=seg2.nendindex&nend=seg2.nstartindex?nstart=seg2.nendindex&nend=seg3.nstartindex?是否jpolygon2segments.count?j =0seg2=segmentsetciseg3=segmentsetj+1nstart=seg2.nstartindex &nend=seg2.nendindex?輸出結(jié)果多邊形結(jié)束是是否是將seg1和seg3頂點(diǎn)和中間點(diǎn)追加到線段seg2后面，同時(shí)將seg3從segmentsetc中刪除否nstart=seg2.nstartindex&nend=seg3.nendi

24、ndex?將seg1和seg2頂點(diǎn)和中間點(diǎn)追加到線段seg3后面，將seg2從segmentsetc中刪除將seg2中點(diǎn)順序加入到seg1點(diǎn)的后面nstart=seg2.nendindex&nend=seg2.nstartindex?nstart=seg2.nendindex&nend=seg3.nstartindex?是否jpolygon2segments.count?j =0seg2=segmentsetciseg3=segmentsetj+1nstart=seg2.nstartindex &nend=seg2.nendindex?輸出結(jié)果多邊形結(jié)束圖3 第三階段流程四、總結(jié) 由于數(shù)據(jù)處理的需求、計(jì)算速度的需求和數(shù)據(jù)顯示的需求，多邊形裁剪算法對(duì)于提高圖形的處理效率和質(zhì)量將會(huì)產(chǎn)生重要的意義，由于其現(xiàn)實(shí)的需求問題，多邊形裁剪算法必將會(huì)朝著更高效、更具適用性的方向發(fā)展。 縱觀這幾年多邊行裁剪算法的發(fā)展，有cohen-sutherland算法、中點(diǎn)分割算法、liang-barsky算法、foley算法、sutherland-hodgman算法、maillot算法、andereev算法等，以上幾種算法只適用于矩形窗口的裁剪，而在具體的工程中，往往遇到的裁剪窗口都是任意多邊形，這類裁剪算法主要有weiler-atherton算法、va