多邊形填充算法
//+++++++++++++++++++++++++++++++++++
//+-----------------定義基本資料-------------------+
//+++++++++++++++++++++++++++++++++++
//----------------------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);
}