//通用掃描線填充算法
//袁國武改寫調(diào)試。2008年4月10日

#include?
#include??
#include??
#define?NULL?0??//C++中沒有NULL這個(gè)符號(hào)常量，這里用宏定義
#define?WINDOW_HEIGHT?400???//定義窗口高為400
#define?WINDOW_WIDTH?400????//定義窗口寬為400

struct?dcPt?{?//dcPt實(shí)際上是一個(gè)點(diǎn)的結(jié)構(gòu)體
???int?x;
???int?y;
};

void?setPixel（GLint?xGLint?y）??//用OpenGL函數(shù)改寫setPixel
{
????glBegin（GL_POINTS）;
	??glVertex2i（x?y）;
	glEnd（）;
}

//以下完全來自ppt，未做任何修改


typedef?struct?tEdge?{
??int?yUpper;
??float?xIntersect?dxPerScan;
??struct?tEdge?*?next;
}?Edge;


/*?Inserts?edge?into?list?in?order?of?increasing?xIntersect?field.?*/
void?insertEdge?（Edge?*?list?Edge?*?edge）
{
??Edge?*?p?*?q?=?list;
??p?=?q->next;
??while?（p?!=?NULL）?{
????if?（edge->xIntersect?xIntersect）
??????p?=?NULL;
????else?{
??????q?=?p;
??????p?=?p->next;
????}
??}
??edge->next?=?q->next;
??q->next?=?edge;
}
/*?For?an?index?return?y-coordinate
?of?next?nonhorizontal?line?*/
int?yNext?（int?k?int?cnt?dcPt?*?pts）
{
??int?j;

??if?（（k+1）?>?（cnt-1））
????j?=?0;
??else
????j?=?k?+?1;
??while?（pts[k].y?==?pts[j].y）
????if?（（j+1）?>?（cnt-1））
??????j?=?0;
????else
??????j++;
??return?（pts[j].y）;
}
/*?Store?lower-y?coordinate?and?inverse?slope?for?each?edge.??Adjust?and?store?upper-y?coordinate?for?edges?that?are?the?lower?member?of?a?monotically?increasing?or?decreasing?pair?of?edges?*/
void?makeEdgeRec
??（dcPt?lower?dcPt?upper?int?yComp?Edge?*?	edge?Edge?*?edges[]）
{
??edge->dxPerScan?=
????（float）?（upper.x?-?lower.x）?/?（upper.y?-?lower.y）;
??edge->xIntersect?=?lower.x;
??if?（upper.y?????edge->yUpper?=?upper.y?-?1;
??else
????edge->yUpper?=?upper.y;
??insertEdge?（edges[lower.y]?edge）;
}
void?buildEdgeList?（int?cnt?dcPt?*?pts?Edge?*?edges[]）
{
??Edge?*?edge;
??dcPt?v1?v2;
??int?i?yPrev?=?pts[cnt?-?2].y;
??
??v1.x?=?pts[cnt-1].x;?v1.y?=?pts[cnt-1].y;
??for?（i=0;?i????v2?=?pts[i];
????if?（v1.y?!=?v2.y）?{????????????????/*?nonhorizontal?line?*/
??????edge?=?（Edge?*）?malloc?（sizeof?（Edge））;
??????if?（v1.y?	makeEdgeRec?（v1?v2?yNext?（i?cnt?pts）?edge?edges）;
??????else?????????????????????????????/*?down-going?edge????*/
	makeEdgeRec?（v2?v1?yPrev?edge?edges）;
????}
????yPrev?=?v1.y;
????v1?=?v2;
??}
}
void?buildActiveList?（int?scan?Edge?*?active?Edge?*?edges[]）
{
??Edge?*?p?*?q;

??p?=?edges[scan]->next;
??while?（p）?{
????q?=?p->next;
????insertEdge?（active?p）;
????p?=?q;
??}
}
void?fillScan?（int?scan?Edge?*?active）
{
??Edge?*?p1?*?p2;
??int?i;
??
??p1?=?active->next;
??while?（p1）?{
????p2?=?p1->next;
????for?（i=p1->xIntersect;?ixIntersect;?i++）
??????setPixel?（（int）?i?scan）;
????p1?=?p2->next;
??}
}
void?deleteAfter?（Edge?*?q）
{
??Edge?*?p?=?q->next;

??q->next?=?p->next;
??free?（p）;
}

/*?Delete?completed?edges.?Update?‘xIntersect‘?field?for?others?*/
void?updateActiveList?（int?scan?Edge?*?active）
{
??Ed

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件???????5591??2009-04-13?10:02??scanFill\scanFill.cpp

?????文件??????45056??2009-04-13?10:03??scanFill\scanFill.exe

?????目錄??????????0??2008-04-09?11:25??scanFill

-----------?---------??----------?-----??----

????????????????50647????????????????????3