//Fill.h
#define MAX_X 1024 //定义显示最大区域X坐标
#define MAX_Y 768 //定义显示最大区域Y坐标
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
typedef struct Arc //弧
{
int x1;
int y1;
int x2;
int y2;
}Arcs,*pArc;
typedef struct Node //AET,ET表的结点
{
int Ymin;
double Xs;
double detalX;
struct Node *next;
}Node,*pNode,*ET,*AET;
typedef struct YNode //Y桶的每个元素结构
{
pNode listHead; //链表头
pNode listTail; //链表尾
int num; //链表的结点个数
// int height; //桶的高度
}YNode,*pYNode;
typedef struct ET_AET_Table
{
YNode* Y_barrel[MAX_Y];
}ET_AET_Table,*EAT;
EAT createET(Arcs *arcs,int numOfArcs); //创建ET表
EAT createAET(); //创建AET表
void insertNode(EAT eat,pNode node,int height); //排序插入结点
void ET2AET(const EAT et,EAT aet); //ET表转换成AET表
//void showEAT(const EAT eat); //测试
//Fill.cpp
#include "stdafx.h"
EAT createET(Arcs *arcs,int numOfArcs)
{
EAT et = new ET_AET_Table;
int i;
for(i=0;i<MAX_Y;i++)
et->Y_barrel[i] = NULL;
for(i=0;i<numOfArcs;i++)
{
if(arcs[i].y1 != arcs[i].y2)
{
//y1 != y2
pNode node = new Node;
node->Ymin = MIN(arcs[i].y1,arcs[i].y2);
if(MAX(arcs[i].y1,arcs[i].y2) == arcs[i].y1)
node->Xs = arcs[i].x1;
else
node->Xs = arcs[i].x2;
node->detalX = (double)(arcs[i].x1-arcs[i].x2)/(double)(arcs[i].y2-arcs[i].y1);
node->next = NULL;
insertNode(et,node,MAX(arcs[i].y1,arcs[i].y2));
}
}
return et;
}
EAT createAET()
{
EAT aet = new ET_AET_Table;
int i;
for(i=0;i<MAX_Y;i++)
aet->Y_barrel[i] = NULL;
return aet;
}
void insertNode(EAT eat,pNode node,int height)
{
//排序插入结点
if(node == NULL)
{
// cout <<"Error:Node is NULL!"<<endl;
return;
}
if(eat->Y_barrel[height] == NULL)
{
//该高度结点为空，插入链表
pYNode pynode = new YNode;
eat->Y_barrel[height] = pynode;
eat->Y_barrel[height]->listHead = node;
eat->Y_barrel[height]->listTail = node;
eat->Y_barrel[height]->num = 1;
return;
}
pNode p = eat->Y_barrel[height]->listHead;
while(p != NULL)
{
if((node->Xs < p->Xs) ||
(node->Xs == p->Xs && node->detalX < p->detalX))
{
//插在前面
if(eat->Y_barrel[height]->listHead == p)
{
//只有一个结点的情况
eat->Y_barrel[height]->listHead = node;
node->next = p;
}
else
{
//插入到其他任意结点前
pNode q;
for(q=eat->Y_barrel[height]->listHead;q->next!=p;q=q->next);
q->next = node;
node->next = p;
}
break;
}
else
p = p->next;
}
if(p == NULL)
{
//不能插到任意一个结点前，则把它插入到链表最后
eat->Y_barrel[height]->listTail->next = node;
eat->Y_barrel[height]->listTail = node;
}
eat->Y_barrel[height]->num++;
}
void ET2AET(const EAT et,EAT aet)
{
int i,j;
for(i=MAX_Y-1;i>=0;i--)//找出第一个非空结点的所在高度
{
if(et->Y_barrel[i] != NULL)
break;
}
for(j=i;j>=0;j--)
{
if(aet->Y_barrel[j+1] != NULL)
{
//修改上一级的结点
pNode q = aet->Y_barrel[j+1]->listHead;
while(q != NULL)
{
if(q->Ymin != j)
{
//如果Ymin不等于改高度才插入结点
pNode node = new Node;
node->Ymin = q->Ymin;
node->Xs = q->Xs+q->detalX;
node->detalX = q->detalX;
node->next = NULL;
insertNode(aet,node,j);
}
q = q->next;
}
}
if(et->Y_barrel[j] != NULL)
{
//将et中的结点复制到aet中
pNode p = et->Y_barrel[j]->listHead;
while(p != NULL)
{
if(p->Ymin != j)
{
//如果Ymin不等于改高度才插入
pNode node = new Node;
node->Ymin = p->Ymin;
node->Xs = p->Xs;
node->detalX = p->detalX;
node->next = NULL;
insertNode(aet,node,j);
}
p = p->next;
}
}
}
}
/*
void showEAT(const EAT eat)
{
//显示et，aet表
for(int i=MAX_Y-1;i>=0;i--)
{
if(eat->Y_barrel[i] != NULL)
{
cout <<"Height:"<<i<<endl;
pNode p = eat->Y_barrel[i]->listHead;
while(p != NULL)
{
cout<<" Ymin: "<<p->Ymin
<<" Xs: "<<p->Xs
<<" detalX: "<<p->detalX<<endl;
p = p->next;
}
}
}
}
*/
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
以上为ET表，AET表的构造和转换程序，主要就是那个插入结点的函数。
以下是VC中绘图部分程序
//填充
EAT et = createET(pDoc->m_pArcs,pDoc->m_iNumOfArcs);
EAT aet = createAET();
ET2AET(et,aet);
for(int i=MAX_Y-1;i>=0;i--)
{
if(aet->Y_barrel[i] != NULL)
{
pNode p = aet->Y_barrel[i]->listHead;
while(p != NULL)
{
int beginP,endP;
beginP = (int)(p->Xs+0.5)+XO;
endP = (int)(p->next->Xs+0.5)+XO;
while(beginP<=endP)
{
pDC->SetPixelV(beginP,YO-i,RGB(255,0,0));
beginP++;
}
p = p->next;
p = p->next;
}
}
}
当中pDoc->m_pArcs,pDoc->m_iNumOfArcs为边集和边数
