實驗報告

實驗?zāi)康?/p>

1、掌握有序邊表算法填充多邊形區(qū)域;

2、理解多邊形填充算法的意義；

3、增強(qiáng)C語言編程能力。

算法原理介紹

根據(jù)多邊形內(nèi)部點的連續(xù)性知：一條掃描線與多邊形的交點中，入點和出點之間所 有點都是多邊形的內(nèi)部點。所以，對所有的掃描線填充入點到出點之間所有的點就可填 充多邊形。

判斷掃描線上的點是否在多邊形之內(nèi)，對于一條掃描線，多邊形的掃描轉(zhuǎn)換過程可 以分為四個步驟：

(1)求交：計算掃描線與多邊形各邊的交點；

(2)排序：把所有交點按x值遞增順序排序；

(3)配對：第一個與第二個，第三個與第四個等等；每對交點代表掃描線與多邊 形的一個相交區(qū)間；

(4)著色：把相交區(qū)間內(nèi)的象素置成多邊形顏色，把相交區(qū)間外的象素置成背景 色。

p1,p3,p4,p5屬于局部極值點，要把他們兩次存入交點表中。如掃描線y=7上的交

點中，有交點(2,7,13)，按常規(guī)方法填充不正確，而要把頂點(7,7)兩次存入交點表中 (2,7,7,13)。p2, p6為非極值點，則不用如上處理。

為了提高效率，在處理一條掃描線時，僅對與它相交的多邊形的邊進(jìn)行求交運(yùn)算。 把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標(biāo)遞增的順序存放 在一個鏈表中，稱此鏈表為活性邊表(AET)。

對每一條掃描線都建立一個與它相交的多邊形的活性邊表(AET。每個AET的一

個節(jié)點代表一條活性邊，它包含三項內(nèi)容

x -當(dāng)前掃描線與這條邊交點的x坐標(biāo)；

△ x -該邊與當(dāng)前掃描線交點到下一條掃描線交點的x增量；

ymax -該邊最高頂點相交的掃描線號。

每條掃描線的活性邊表中的活性邊節(jié)點按照各活性邊與掃描線交點的x值遞增排序

連接在一起。

當(dāng)掃描線y移動到下一條掃描線y = y+1時，活性邊表需要更新，即刪去不與新掃 描線相交的多邊形邊，同時增加與新掃描線相交的多邊形邊，并根據(jù)增量法重新計 算掃描線與各邊的交點x。

當(dāng)多邊形新邊表ET構(gòu)成后，按下列步驟進(jìn)行：

對每一條掃描線i，初始化ET表的表頭指針ET[i];

將ymax = i的邊放入ET[i]中；

使y=多邊形最低的掃描線號；

初始化活性邊表AET為空；

循環(huán)，直到AET和ET為空。

將新邊表ET中對應(yīng)y值的新邊節(jié)點插入到AET表。

遍歷AET表，將兩兩配對的交點之間填充給定顏色值。

遍歷AET表，將ymax= y的邊節(jié)點從AET表中刪除，并將ymax> y的各邊節(jié)點 的x值遞增△ x;并重新排序。

y增加1。

三、程序源代碼

#in elude "graphics.h"

#defi ne WINDOW_HEIGHT 480

#define NULL 0

#i nclude "alloc.h"

#i nclude "stdio.h"

#i nclude "dos.h"

#i nclude "con io.h"

typedefstruct tEdge/*typedef是將結(jié)構(gòu)定義成數(shù)據(jù)類型*/

{ int ymax;/*邊所交的最高掃描線號*/

float x;/*當(dāng)前掃描線與邊的交點的x值*/

float dx;/*從當(dāng)前掃描線到下一條掃描線之間的 x增量*/

struct tEdge *n ext;

}Edge;

typedef struct poi nt{int x,y;}POINT;/*將結(jié)點插入邊表的主體函數(shù)

typedef struct poi nt{int x,y;}POINT;

/*將結(jié)點插入邊表的主體函數(shù)*/

void In sertEdge(Edge *list,Edge *edge)/* {

Edge *p,*q=list;

p=q->n ext;/*

while(p!=NULL)/*

{

if(edge->xx) /* p=NULL;

else/*

{q=p; p=p->n ext;

}

}

edge->n ext=q->n ext; q->n ext=edge;

}

活性邊edge插入活性邊表list中*/

記住q原來所指之結(jié)點*/ 按x值非遞減順序增加邊表*/ 要插入的邊的x較大不應(yīng)該在當(dāng)前插入*/

要插入的邊的x較小應(yīng)該在當(dāng)前插入*/

/* 使欲插入之結(jié)點edge指向q原來所指之結(jié)點*/

/*使q指向插入之結(jié)點*/

int yNext(int k,int cnt,POINT *pts)

/*對于多邊形中的某個頂點序號k(0,1...6)，返回下一頂點的縱坐標(biāo),如果這2 個頂點所在邊是 水平的，則順延，即返回第(k+2)個頂點的縱坐標(biāo)),cnt是頂點個數(shù) +1,pts指向多邊形頂點結(jié)構(gòu)體的指針*/

{

int j;

if((k+1)>(cnt-1))/*當(dāng)前頂點為最后一個頂點，則下一個頂點為第0個頂點*/

j=0;

e

總結(jié)

以上是生活随笔為你收集整理的计算机图形学有序边表作业,《计算机图形学》有序边表填充算法.docx的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。