實面積多邊形的生成匯總課件

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

2、=0;iLineTo(vi0.x, vi0.y);只要給出點序,以次可以畫出圖來2. 有向邊的線集 Eini=1#define MAX 100 Typedef struct int PolygonNum; / 多邊形頂點個數(shù) Point vertexcesMAX ; /多邊形頂點數(shù)組 Polygon / 多邊形結(jié)構(gòu)Polygon plg; int n; Point pt;plg 的數(shù)據(jù)輸入:. n=plg.PolygonMun; pt=plg. vertexces0 pDC-MoveTo(pt,x,pt.y); for(i=0;iLineTO (pt.x, pt,y); 3. 一種實用的數(shù)據(jù)結(jié)

3、構(gòu)點數(shù)組，線用點的序號取點，面用線的序號取線。struct point float x,y; /坐標(biāo)struct Line int sn,en; /點的indexstruct shape int ln100; ; /線的indexpoint a100; aj.x aj.y Line Ll100; Lli.sn Lli.en- aLii.sn.x, aLii.sn.y aLii.en.x, aLii.en.yShape sp; sp.lnj Lisp.lnj.sn, Lisp.lnj.enSp: aLlsp.lni.sn.x=10; aLlsp.lni.en,x=100 aLlsp.lni.sn

4、.y=10 ; aLlsp.lni.en,y=100pDC-MoveTO( aLlsp.ln0.sn.x, aLlsp.ln0.sn.y); for(i=0;iLineTO ( aLlsp.lni.en.x, aLlsp.lni.en.y);頂點表示的多邊形，可以用畫線的方法，可以用VC中函數(shù)：pDC-LineTo(x,y) /x,y是終點坐標(biāo)pDC-Polygon(array,4); /array中是頂點的x,y坐標(biāo)值/這里的Polygon是一個成員函數(shù)二、 2-D圖形的生成多邊形的表示方法頂點表示 (線) 點陣表示（填充）上面已經(jīng)給出用點或線繪制2-D的多邊形用填充方法可以得到實多邊形(點

5、陣),這需要進(jìn)行多邊形的填充.裁剪用于選取圖形中的一部分三、實面積多邊形：點陣表示（填充）實面積多邊形可以用多邊形填充方法實現(xiàn)將頂點表示形式轉(zhuǎn)換成點陣表示形式有三種方法：逐點判斷法；掃描線算法；邊緣填充法。1. 逐點判斷法：逐點判斷繪圖窗口內(nèi)的每一個像素： 在多邊形的內(nèi)還是外判斷點在多邊形的內(nèi)外關(guān)系的方法：1）射線法：2）累計角度法3）編碼法；1. 射線法:對于凸或凹的單個多邊形(非自交多邊形 )1）射線法(p43) 對于凸或凹的單個多邊形基本原理: 每一點發(fā)一水平射線,即掃描線,對于一個封閉圖形 一般外部的點和多邊形有偶數(shù)個交點, 而多邊形內(nèi)部的點只有奇數(shù)個點 奇異情況除外 所以也叫交點計數(shù)

6、法設(shè)交點個數(shù)為k,則K的奇偶性決定了點與多邊形的內(nèi)外關(guān)系對內(nèi)部點進(jìn)行填充.奇異情況處理 p 43圖中有3個奇異點和一條奇異邊(水平邊)水平邊：不計算 線的端點(奇異): 按兩次計數(shù)逐點判斷法程序簡單，速度太慢，效率低并且:奇異按兩次計數(shù),實現(xiàn)不方便,約定只處理極大點,極小點不要了.(不封閉了)2）.掃描線算法scan-line algorithlm從上面的計算過程想到,相鄰像素是連貫的，掃描過程能夠得到掃描線和多邊形邊界的交點可以確定多邊形內(nèi)部的一根線.所以一根掃描線能夠確定和這根線對應(yīng)的所有內(nèi)部點, 提高算法效率處理對象： 非自交多邊形 （邊與邊之間除了頂點外無其它交點）基本原理： 一條掃描

7、線與多邊形的邊有偶數(shù)個交點P44/三 填充算法從上到下,從左到右對所有交點進(jìn)行排序依次進(jìn)行畫線步驟(對于每一條掃描線):(1)求交點(2)交點排序 (見上圖2-5/b)(3)交點配對，填充區(qū)段。具體處理時的問題：1. 如何處理任意給的非整數(shù)的點的取整：2. 如何處理頂點3. 如何處理水平邊上的點（不計算交點的個數(shù)）二點改進(jìn): 1. 改存儲點為存儲線(只需要2個頂點) 2. 加快直線求交的方法基本思想:由直線段和掃描線計算出交點由直線的斜率可以計算出下一個交點所以只需要線,交點是計算出來的兩個問題要解決:1. 快速求交點2. 排序: 交點需要: 依從左到右,從上到下的序列進(jìn)行排序 這樣才能夠準(zhǔn)確

8、畫線填充求交點:解兩個直線方程: 兩條線的交點:a線上的點能夠滿足在B線上的距離=0對于斜線的交點：能否利用掃描線的等距且平行相關(guān)的特性。簡化交點的求取 由于填充過程是從上到下逐行進(jìn)行，故取 yi+1=yi - 1 (2. 2) 斜率 f= (x2-x1)/(y2-y1) 利用斜率可求得斜邊上對應(yīng)交點的x坐標(biāo)為 xi+1=xi+x (23) 其中: x=f * y = f 。可見:你只要得到斜線上的一個點,就可以計算出,所有其它交點.而不必再去求交了 .斜率dx=-(xs-xe)/(ys-ye) (ysye) 記錄起點 for(y=ys,x=xs; y=ye; ) y-; x=x+dx , 記

9、錄交點（x,y）; 所以只要記錄: p45:/ 有4個參數(shù):ys,xs,dx,ye 的 一條斜邊（其交點就可以得到）并且可以方便的求出所有交點( 把求交變?yōu)榧臃ā? 這樣可以，只保存斜邊，能夠大大改善表的太大問題求交點的全過程: 填充時, 掃描線的高度: 1. Ys=Ymax=max|Y1,Y2| Xs=x1 當(dāng) Ys=y1時 Xs=x2 當(dāng) Ys=y2時 2. 以后: Yi+1=Yi - 1 Xi+1=Xi+x =Xi +f 3.當(dāng)填充掃描線的高度Ye=Ymin=min|y1,y2|時，停止計算該斜邊上的最后一個交點(即忽略斜邊最低的交點余聲: 求掃描線和多邊形的n條邊的n*m個交點。 只要

10、做 2* n*m次的加法運算即可 x=x+f Y=y+1 做n*m次實際上還要求n個f2. 排序: 現(xiàn)在把點的排序，改為邊的排序?；钚赃叡恚篴ctive-edge-table ( AETable) （AEList）在基本算法中，當(dāng)處理一條掃描線時，為了求出它與多邊形邊的所有交點，必須將它與所有的邊進(jìn)行求交測試。 而實際上只有某幾條邊與該掃描線有交點?；钚赃叡硪彩沁叺姆诸惐恚?正是用來排除不必要的求交測試的。指出和掃描線有關(guān)的邊活性邊表：與當(dāng)前掃描線相交的邊集。該邊集按交點x的增量順序存放在一個鏈表中；該鏈表稱作活性邊表（AEL）。c ,d最高 先記錄,c在左最先記錄把活性表用y 桶表組織起來。

11、構(gòu)造初始邊表(y 桶表): p46ET:(1 ).以 y的端點坐標(biāo)值來組織（ymax or ymin， 考慮實際掃描是從上到下：用ymax）y 桶表根據(jù)AET對邊的信息的要求, 邊的內(nèi)容改為： ymin,xs,斜率，鏈指針 ymin 用于表示該條邊的結(jié)束（用于控制）， xs 是 x=x+dx 的起點 (避免盲目求交)2 同一高度的斜邊用Xs排序 3.以指針方式，指向鏈表 鏈表包含ymin , xs,斜率，鏈指針:邊的信息斜率=dx (或x )（7）一個例（p48）圖2-11 ET 中的每一項指針指向的結(jié)點是邊要畫圖時該掃描線的結(jié)點插入AET中，AET中結(jié)點對，畫一根線 要畫圖的邊的點的坐標(biāo)（x

12、,y）： y 是掃描線的y , x的值由結(jié)點中的xs+dx 求得 掃描線算法的簡單實現(xiàn)point a20= 10,20, 40,40, 30,0, jp20; Struct Line Int s,e;Float f; Ll3=0,1,0,1,2,0,2,3,0;求出斜率,填入.求交點: 設(shè)置y每次+5 for( i=0;i3;i+) for(y=aLii.s.y; yGetPixel( x,y); current1=pDC-GetPixel(x1,y1); current2=pDC-GetPixel(x2,y2);一根掃描線和多邊形可以有若干點對, 所以要記住點對); 以點對畫線 3. ( 特

13、殊點的處理：SetPixel(seedx+i,seedy,RGB(250,0,0); 步驟：1. 如果背景和線比較接近,先設(shè)置背景 for() For() pDC-SetPixel(seedx+i,seedy,RGB(,200,200);2. 畫多邊形 CPen pen; pen.CreatePen(0,0,RGB(250,0,0 ); /重新創(chuàng)建畫筆 pDC-SelectObject(&pen); 畫多邊形3. 通過掃描，讀邊界點:對每一根掃描線可以，得到若干點對 current1=pDC-GetPixel(i,j); current2=pDC-GetPixel(i1,j2) 有多對時,要用

14、數(shù)組, 4.填充:對每一根掃描線與多邊形的交點的點對.直接畫線, 只要依次記錄點對,可以簡化活性鏈表,也避免了用桶形表來管理,較大的簡化了掃描線算法程序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(&Pen); for(i=0;iMoveTo(ai.x,ai.y); if(i+1=3) pDC-LineTo(a0.x,a0.y); break; pDC-LineTo(ai+1.x,ai+1.y); pDC-SelectObject(oldPen); /恢復(fù)原來的畫筆Pen.Detach(); for( i=20;i138;i+) /20140 for(frist=0, j=5;jGetPixel(