多边形填充-Y-X算法(源代码)

王朝other·作者佚名  2006-01-09
宽屏版  字体: |||超大  

//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为边集和边数

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
© 2005- 王朝网络 版权所有