多边形填充-Y-X算法（源代码）

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

本文地址：http://com.8s8s.com/it/it22165.htm