1、第二章 實(shí)面積多邊形的生成,講授 陳禮民 2005-3-20,一、多邊形的定義和性質(zhì), 多邊形是由折線段組成的封閉圖形， 定義：有序的頂點(diǎn)的點(diǎn)集 Vini=1 有向邊的線集 Eini=1 邊的走向: 多邊形的左側(cè)為多邊形的內(nèi)部區(qū)：反時(shí)針 圖2-1是錯(cuò)誤的 環(huán)：中空的多邊形 ： 外部反時(shí)針，內(nèi)部，順時(shí)針,多邊形的凹凸的判別: 計(jì)算機(jī)自動(dòng)識(shí)別,可以用兩條有向邊的X積. Vi-1Vi , ViVi+1是兩條連接的有向邊 利用右手定則, 有 Vi-1Vi X ViVi+1 =aK 對(duì)于凸多邊形方向相外(向視點(diǎn)),定義為正,a0 對(duì)于凹多邊形方向相里(離開(kāi)視點(diǎn)),a0,多邊形的(描述)數(shù)據(jù)結(jié)構(gòu) 1. 由

2、有序的頂點(diǎn)的點(diǎn)集 Vini=1可以確定一個(gè)多邊形: CPoint vi30=0,0,20,30,.; int n,i; /n是點(diǎn)數(shù) pDC-MoveTO(vi0.x, vi0.y); for(i=0;iLineTo(vi0.x, vi0.y); 只要給出點(diǎn)序,以次可以畫(huà)出圖來(lái),2. 有向邊的線集 Eini=1 #define MAX 100 Typedef struct int PolygonNum; / 多邊形頂點(diǎn)個(gè)數(shù) Point vertexcesMAX ; /多邊形頂點(diǎn)數(shù)組 Polygon / 多邊形結(jié)構(gòu) Polygon plg; int n; Point pt; plg 的數(shù)據(jù)輸入:.

3、 n=plg.PolygonMun; pt=plg. vertexces0 pDC-MoveTo(pt,x,pt.y); for(i=0;iLineTO (pt.x, pt,y); ,3. 一種實(shí)用的數(shù)據(jù)結(jié)構(gòu),點(diǎn)數(shù)組，線用點(diǎn)的序號(hào)取點(diǎn)，面用線的序號(hào)取線。 struct point float x,y; /坐標(biāo) struct Line int sn,en; /點(diǎn)的index struct shape int ln100; ; /線的index point a100; aj.x aj.y Line Ll100; Lli.sn Lli.en - aLii.sn.x, aLii.sn.y aLii.e

4、n.x, aLii.en.y Shape sp; sp.lnj Lisp.lnj.sn, Lisp.lnj.en,Sp: aLlsp.lni.sn.x=10; aLlsp.lni.en,x=100 aLlsp.lni.sn.y=10 ; aLlsp.lni.en,y=100 pDC-MoveTO( aLlsp.ln0.sn.x, aLlsp.ln0.sn.y); for(i=0;iLineTO ( aLlsp.lni.en.x, aLlsp.lni.en.y); ,頂點(diǎn)表示的多邊形，可以用畫(huà)線的方法， 可以用VC中函數(shù)： pDC-LineTo(x,y) /x,y是終點(diǎn)坐標(biāo) pDC-Polygo

5、n(array,4); /array中是頂點(diǎn)的x,y坐標(biāo)值 /這里的Polygon是一個(gè)成員函數(shù),二、 2-D圖形的生成 多邊形的表示方法 頂點(diǎn)表示 (線) 點(diǎn)陣表示（填充）,上面已經(jīng)給出用點(diǎn)或線繪制2-D的多邊形 用填充方法可以得到實(shí)多邊形(點(diǎn)陣),這需要進(jìn)行多邊形的填充. 裁剪用于選取圖形中的一部分,三、實(shí)面積多邊形：點(diǎn)陣表示（填充）,實(shí)面積多邊形可以用多邊形填充方法實(shí)現(xiàn) 將頂點(diǎn)表示形式轉(zhuǎn)換成點(diǎn)陣表示形式 有三種方法： 逐點(diǎn)判斷法；掃描線算法；邊緣填充法。 1. 逐點(diǎn)判斷法： 逐點(diǎn)判斷繪圖窗口內(nèi)的每一個(gè)像素： 在多邊形的內(nèi)還是外 判斷點(diǎn)在多邊形的內(nèi)外關(guān)系的方法： 1）射線法： 2）累計(jì)角度

6、法 3）編碼法；,1. 射線法:,對(duì)于凸或凹的單個(gè)多邊形(非自交多邊形 ),1）射線法(p43) 對(duì)于凸或凹的單個(gè)多邊形 基本原理: 每一點(diǎn)發(fā)一水平射線,即掃描線,對(duì)于一個(gè)封閉圖形 一般外部的點(diǎn)和多邊形有偶數(shù)個(gè)交點(diǎn), 而多邊形內(nèi)部的點(diǎn)只有奇數(shù)個(gè)點(diǎn) 奇異情況除外 所以也叫交點(diǎn)計(jì)數(shù)法 設(shè)交點(diǎn)個(gè)數(shù)為k, 則K的奇偶性決定了點(diǎn)與多邊形的內(nèi)外關(guān)系 對(duì)內(nèi)部點(diǎn)進(jìn)行填充.,奇異情況處理 p 43 圖中有3個(gè)奇異點(diǎn)和一條 奇異邊(水平邊) 水平邊：不計(jì)算 線的端點(diǎn)(奇異): 按兩次計(jì)數(shù) 逐點(diǎn)判斷法程序簡(jiǎn)單， 速度太慢，效率低,并且: 奇異按兩次計(jì)數(shù),實(shí)現(xiàn)不方便,約定只處理極大點(diǎn), 極小點(diǎn)不要了.(不封閉了),2

7、）.掃描線算法scan-line algorithlm,從上面的計(jì)算過(guò)程想到,相鄰像素是連貫的， 掃描過(guò)程能夠得到掃描線和多邊形邊界的交點(diǎn) 可以確定多邊形內(nèi)部的一根線. 所以一根掃描線能夠確定和這根線對(duì)應(yīng)的所有內(nèi)部點(diǎn), 提高算法效率 處理對(duì)象： 非自交多邊形 （邊與邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)） 基本原理： 一條掃描線與多邊形的邊有偶數(shù)個(gè)交點(diǎn),P44/三 填充算法 從上到下,從左到右對(duì)所有交點(diǎn)進(jìn)行排序 依次進(jìn)行畫(huà)線,步驟(對(duì)于每一條掃描線): (1)求交點(diǎn) (2)交點(diǎn)排序 (見(jiàn)上圖2-5/b) (3)交點(diǎn)配對(duì)，填充區(qū)段。,具體處理時(shí)的問(wèn)題： 1. 如何處理任意給的非整數(shù)的點(diǎn)的取整： 2. 如何處

8、理頂點(diǎn) 3. 如何處理水平邊上的點(diǎn)（不計(jì)算交點(diǎn)的個(gè)數(shù)）,二點(diǎn)改進(jìn): 1. 改存儲(chǔ)點(diǎn)為存儲(chǔ)線(只需要2個(gè)頂點(diǎn)) 2. 加快直線求交的方法 基本思想: 由直線段和掃描線計(jì)算出交點(diǎn) 由直線的斜率可以計(jì)算出下一個(gè)交點(diǎn) 所以只需要線,交點(diǎn)是計(jì)算出來(lái)的,兩個(gè)問(wèn)題要解決: 1. 快速求交點(diǎn) 2. 排序: 交點(diǎn)需要: 依從左到右,從上到下的序列進(jìn)行排序 這樣才能夠準(zhǔn)確畫(huà)線填充,求交點(diǎn):解兩個(gè)直線方程: 兩條線的交點(diǎn):a線上的點(diǎn)能夠滿足在B線上的距離=0 對(duì)于斜線的交點(diǎn)：能否利用掃描線的等距且平行相關(guān)的特性。 簡(jiǎn)化交點(diǎn)的求取 由于填充過(guò)程是從上到下逐行進(jìn)行，故取 yi+1=yi - 1 (2. 2) 斜率 f=

9、 (x2-x1)/(y2-y1) 利用斜率可求得斜邊上對(duì)應(yīng)交點(diǎn)的x坐標(biāo)為 xi+1=xi+x (23) 其中: x=f * y = f 。,可見(jiàn):你只要得到斜線上的一個(gè)點(diǎn),就可以計(jì)算出,所有其它交點(diǎn). 而不必再去求交了 .斜率dx=-(xs-xe)/(ys-ye) (ysye) 記錄起點(diǎn) for(y=ys,x=xs; y=ye; ) y-; x=x+dx , 記錄交點(diǎn)（x,y）; ,所以只要記錄: p45:/ 有4個(gè)參數(shù):ys,xs,dx,ye 的 一條斜邊（其交點(diǎn)就可以得到） 并且可以方便的求出所有交點(diǎn)( 把求交變?yōu)榧臃ā? 這樣可以，只保存斜邊，能夠大大改善表的太大問(wèn)題,求交點(diǎn)的全過(guò)程:

10、填充時(shí), 掃描線的高度: 1. Ys=Ymax=max|Y1,Y2| Xs=x1 當(dāng) Ys=y1時(shí) Xs=x2 當(dāng) Ys=y2時(shí) 2. 以后: Yi+1=Yi - 1 Xi+1=Xi+x =Xi +f 3.當(dāng)填充掃描線的高度Ye=Ymin=min|y1,y2|時(shí)， 停止計(jì)算該斜邊上的最后一個(gè)交點(diǎn)(即忽略斜邊最低的交點(diǎn),余聲: 求掃描線和多邊形的n條邊的n*m個(gè)交點(diǎn)。 只要做 2* n*m次的加法運(yùn)算即可 x=x+f Y=y+1 做n*m次 實(shí)際上還要求n個(gè)f,2. 排序: 現(xiàn)在把點(diǎn)的排序，改為邊的排序。 活性邊表：active-edge-table ( AETable) （AEList） 在基

11、本算法中，當(dāng)處理一條掃描線時(shí)， 為了求出它與多邊形邊的所有交點(diǎn)， 必須將它與所有的邊進(jìn)行求交測(cè)試。 而實(shí)際上只有某幾條邊與該掃描線有交點(diǎn)。 活性邊表也是邊的分類表， 正是用來(lái)排除不必要的求交測(cè)試的。 指出和掃描線有關(guān)的邊 活性邊表：與當(dāng)前掃描線相交的邊集。 該邊集按交點(diǎn)x的增量順序存放在一個(gè)鏈表中；該鏈表稱作活性邊表（AEL）。,c ,d最高 先記錄,c在左最先記錄 ,把活性表用y 桶表組織起來(lái)。 構(gòu)造初始邊表(y 桶表): p46 ET: (1 ).以 y的端點(diǎn)坐標(biāo)值來(lái)組織（ymax or ymin， 考慮實(shí)際掃描是從上到下：用ymax）y 桶表 根據(jù)AET對(duì)邊的信息的要求, 邊的內(nèi)容改為：

12、 ymin,xs,斜率，鏈指針 ymin 用于表示該條邊的結(jié)束（用于控制）， xs 是 x=x+dx 的起點(diǎn) (避免盲目求交) 2 同一高度的斜邊用Xs排序 3.以指針?lè)绞?，指向鏈?鏈表包含ymin , xs,斜率，鏈指針:邊的信息 斜率=dx (或x ),（7）一個(gè)例（p48）圖2-11 ET 中的每一項(xiàng)指針指向的結(jié)點(diǎn)是邊 要畫(huà)圖時(shí)該掃描線的結(jié)點(diǎn)插入AET中，AET中結(jié)點(diǎn)對(duì)，畫(huà)一根線 要畫(huà)圖的邊的點(diǎn)的坐標(biāo)（x,y）： y 是掃描線的y , x的值由結(jié)點(diǎn)中的xs+dx 求得,掃描線算法的簡(jiǎn)單實(shí)現(xiàn),point a20= 10,20, 40,40, 30,0, jp20; Struct Line

13、 Int s,e; Float f; Ll3=0,1,0,1,2,0,2,3,0; 求出斜率,填入. 求交點(diǎn): 設(shè)置y每次+5 for( i=0;i3;i+) for(y=aLii.s.y; y aLii.e.y; y+=5) jpk.x=x+Lii.f; jpk+.y=y; 對(duì)jpk 排序,以相鄰點(diǎn)畫(huà)線填充即可,取一根邊,當(dāng)y是增方向 以 y為小值點(diǎn)作為起點(diǎn), ,否則以大值為起點(diǎn). 現(xiàn)設(shè)y為小值的點(diǎn)為s,用讀寫(xiě)象素直接測(cè)定邊界,求出掃描線和多邊形的邊的交點(diǎn)：可得到要填充的區(qū)間 一種簡(jiǎn)單的方法：利用邊和背景的不同,在掃描過(guò)程中，直接讀取多邊形的邊:即掃描線和多邊形的交點(diǎn)。 1取當(dāng)前屏幕上一點(diǎn)的

14、方法： pDC-GetPixel( x,y); current1=pDC-GetPixel(x1,y1); current2=pDC-GetPixel(x2,y2); 一根掃描線和多邊形可以有若干點(diǎn)對(duì), 所以要記住點(diǎn)對(duì) ); 以點(diǎn)對(duì)畫(huà)線,3. ( 特殊點(diǎn)的處理：SetPixel(seedx+i,seedy,RGB(250,0,0); 步驟： 1. 如果背景和線比較接近,先設(shè)置背景 for() For() pDC-SetPixel(seedx+i,seedy,RGB(,200,200); 2. 畫(huà)多邊形 CPen pen; pen.CreatePen(0,0,RGB(250,0,0 ); /重新

15、創(chuàng)建畫(huà)筆 pDC-SelectObject( 畫(huà)多邊形,3. 通過(guò)掃描，讀邊界點(diǎn):對(duì)每一根掃描線可以，得到若干點(diǎn)對(duì) current1=pDC-GetPixel(i,j); current2=pDC-GetPixel(i1,j2) 有多對(duì)時(shí),要用數(shù)組, 4.填充:對(duì)每一根掃描線與多邊形的交點(diǎn)的 點(diǎn)對(duì).直接畫(huà)線, 只要依次記錄點(diǎn)對(duì),可以簡(jiǎn)化活性鏈表,也避免了用桶形表來(lái)管理,較大的簡(jiǎn)化了掃描線算法,程序,CPen pen,*oldpen; CPoint a4=20,20, 40,140,60,20,20,20; int current=0, frist=0, end=0,I,j,c=0; CPen Pen(PS_SOLID,0,RGB(150,0,0); /不同于邊:250 CPen* oldPen=pDC-SelectObject(,for( i=20;iGet