多边形填充算法

多边形填充算法

//+++++++++++++++++++++++++++++++++++
//+—————–定义基本数据——————-+
//+++++++++++++++++++++++++++++++++++
//———————-struct_def.h——————————

const int MAX_Y=1028; 
const int MAX_X=1024;
const int MAX_ARC=100;  //假定边的总数最多为 100

typedef struct ArcNode  //定义边
{
 int x1,y1; 
 int x2,y2;
}ArcNode;
typedef struct Node //定义EOT，AET 表中的链表结点
{
   int Ymin;
   float Xs;
   float xx;
   Node * next;
}ElemNode, * ElemLink;
typedef struct NodeY // Y 桶表
{
 ElemLink link;
 int Y;
}NodeY;
typedef struct Table  //表EOT和表AET同样结构
{
   NodeY nodeY[MAX_Y];
}* TableList;

TableList createEOTList(ArcNode arrayARC[MAX_ARC], int n);
void ShowTable(const Table * table);
void InsertArcNode(TableList table,Node *const node,int Y);
TableList EOT_to_AET(const TableList table);

//———————————具体算法实现———————————–

TableList createEOTList(ArcNode arrayARC[MAX_ARC], int n)
{
     TableList eotList=new Table;
 int i;
  for(i=0;i<MAX_Y;i++) //初始化 Y 表
  {  
   eotList->nodeY[i].link=NULL;
   eotList->nodeY[i].Y=i;
  }

  int Y;
  for(i=0;i<n;i++)
  {  if(arrayARC[i].y1 != arrayARC[i].y2) 
  {
   Node * node=new Node;
   if(arrayARC[i].y1 < arrayARC[i].y2)  // y1 < y2
   {
     node->Ymin=arrayARC[i].y1;
     node->Xs=(float)arrayARC[i].x2;
     Y=arrayARC[i].y2;   //!!!!!!!
   }
   if(arrayARC[i].y1 > arrayARC[i].y2)  // y1 > y2  ,y1==y2 的情况不要
   {
     node->Ymin=arrayARC[i].y2;
     node->Xs=(float)arrayARC[i].x1;
     Y=arrayARC[i].y1;
   }
         node->xx=(float) -(arrayARC[i].x2-arrayARC[i].x1) / (arrayARC[i].y2-arrayARC[i].y1);
   node->next=NULL;
   InsertArcNode(eotList,node,Y);
        }
  }
  return eotList;

}

void InsertArcNode(TableList table, Node *const node,int Y)
{
        if(table->nodeY[Y].link==NULL)  
   {  //表头为空
    table->nodeY[Y].link=node;
    node->next=NULL;
    return ;
   }
         else
   {  
    ElemLink head_node=table->nodeY[Y].link;
    ElemNode *temp_node=head_node;
            
if((node->Xs < head_node->Xs) || (head_node->Xs ==
node->Xs && node->xx < head_node->xx))
             {  //插在表头
       table->nodeY[Y].link=node;
       node->next=head_node;
       return;
    }
    else
    {
     while(temp_node->next != NULL)
     {
                
if((node->Xs < temp_node->next->Xs) ||
(temp_node->next->Xs == node->Xs && node->xx <
temp_node->next->xx))
                 {    node->next=temp_node->next;
         temp_node->next=node;
      return;
     }
     else
       temp_node=temp_node->next;
     }  //end while
     if(temp_node->next==NULL)
     {
      temp_node->next=node;
      node->next=NULL;
      return;
     }
    }
  }//end else
}

TableList EOT_to_AET(const TableList table)
{
 int i,j,Y;
 float sum;
 ElemLink head=new Node; 
 TableList tableAET=new Table;

 for(i=0;i<MAX_Y;i++) //初始化 Y 表 且将 EOT copy 到 AET
  {  
   tableAET->nodeY[i].link=NULL;
   tableAET->nodeY[i].Y=i;
  }
    
 for(i=MAX_Y-1;i>0;i–)   //i=MAX_Y-1
 {  
  head=table->nodeY[i].link;
  Y=table->nodeY[i].Y;
  while(head)  
  {  
   Node * temp=new Node;
   temp->Xs =head->Xs;
   temp->Ymin=head->Ymin;
   temp->xx=head->xx;
      temp->next=NULL;
   InsertArcNode(tableAET,temp,Y);
  
   sum=head->Xs;       
   for(j=Y-1;j > head->Ymin;j–)
   {   sum = sum + head->xx;
    Node * addNode=new Node;
    addNode->Ymin=head->Ymin;
    addNode->xx=head->xx;
    addNode->Xs=sum;
    addNode->next=NULL;
       InsertArcNode(tableAET,addNode,j); 
   }
   head=head->next;
  }//END WHILE  
 }
 return tableAET;
}

//在DOC 中定义一数组，在VIEW通过pDoc->arrayARC 获得数组并在显示，数组通过对话框输入，颜色可选!

void CTestHTView::OnDraw(CDC* pDC)
{
 CTestHTDoc* pDoc = GetDocument();
 ASSERT_VALID(pDoc);
 int i,j;
   
 TableList tableEOT=new Table;
 tableEOT=createEOTList(pDoc->ArrayARC,pDoc->num); //
 TableList tableAET=new Table;
 tableAET=EOT_to_AET(tableEOT);

  Node * head=new Node;
  int X1,X2;
 for(i=MAX_Y-1;i>=0;i–)
  {
  head=tableAET->nodeY[i].link;
  while(head)
  {
   X1=head->Xs;
   head=head->next;
   X2=head->Xs;
   for(j=X1;j<X2;j++)
    pDC->SetPixel(j,i,RGB(m_R,m_G,m_B));
  
   head=head->next;
  }
 } 
    ReleaseDC(pDC);
}

Trackback:
http://tb.blog.csdn.net/TrackBack.aspx?PostId=337178