多邊形填充算法實作

//

// 功能:  填充多邊形

//

// 參數:  lpPoints: 指向頂點坐标數組的指針，數組類型為POINT，多邊形由它們順次封閉連接配接得到

//    nCount:  頂點的個數

//    nColor:  填充的顔色 預設為黑色

//    pDC:  裝置句柄指針

//

// 傳回:  無傳回值

//

// 說明:  可以是邊相交的多邊形

//

//

void FillPolygon(LPPOINT lpPoints,int nCount, CDC *pDC, int nColor)

{

 // 檢查參數合法性

 ASSERT_VALID(pDC);

 ASSERT(lpPoints);

 ASSERT(nCount>2);

 ASSERT(nColor>=0);

 // 邊結構資料類型

 typedef struct Edge{

  int ymax;  // 邊的最大y坐标

  float x; // 與目前掃描線的交點x坐标

  float dx; // 邊所在直線斜率的倒數

  struct Edge * pNext; // 指向下一條邊

 }Edge, * LPEdge;

 int i=0,j=0,k=0;

 int y0=0,y1=0;  // 掃描線的最大和最小y坐标

 LPEdge pAET=NULL; // 活化邊表頭指針

 LPEdge * pET=NULL;  // 邊表頭指針

 pAET=new Edge; // 初始化表頭指針，第一個元素不用

 pAET->pNext=NULL;

 // 擷取y方向掃描線邊界

 y0=y1=lpPoints[0].y;

 for(i=1;i<nCount;i++)

 {

  if(lpPoints[i].y<y0)

   y0=lpPoints[i].y;

  else if(lpPoints[i].y>y1)

   y1=lpPoints[i].y;

 }

 if(y0>=y1) return;

 // 初始化邊表，第一個元素不用

 pET=new LPEdge[y1-y0+1];

 for(i=0;i<=y1-y0;i++)

 {

  pET[i]= new Edge;

  pET[i]->pNext=NULL;

 }

 for(i=0;i<nCount;i++)

 {

  j=(i+1)%nCount; // 組成邊的下一點

  if(lpPoints[i].y != lpPoints[j].y)// 如果該邊不是水準的則加入邊表

  {

   LPEdge peg;   // 指向該邊的指針

   LPEdge ppeg;  // 指向邊指針的指針

   // 構造邊

   peg =new Edge;

   k=(lpPoints[i].y>lpPoints[j].y)?i:j;

   peg->ymax=lpPoints[k].y; // 該邊最大y坐标

   k=(k==j)?i:j; 

   peg->x=(float)lpPoints[k].x; // 該邊與掃描線焦點x坐标

   if(lpPoints[i].y != lpPoints[j].y)

    peg->dx=(float)(lpPoints[i].x-lpPoints[j].x)/(lpPoints[i].y-lpPoints[j].y);// 該邊斜率的倒數

   peg->pNext=NULL;

   // 插入邊

   ppeg=pET[lpPoints[k].y-y0];

   while(ppeg->pNext)

    ppeg=ppeg->pNext;

   ppeg->pNext=peg;

  }// end if

 }// end for i

 // 掃描

 for(i=y0;i<=y1;i++)

 {

  LPEdge peg0=pET[i-y0]->pNext;

  LPEdge peg1=pET[i-y0];

  if(peg0)// 有新邊加入

  {

   while(peg1->pNext)

    peg1=peg1->pNext;

   peg1->pNext=pAET->pNext;

   pAET->pNext=peg0;

  }

  // 按照x遞增排序pAET

  peg0=pAET;

  while(peg0->pNext)

  {

   LPEdge pegmax=peg0;

   LPEdge peg1=peg0;

   LPEdge pegi=NULL;

   while(peg1->pNext)

   {

    if(peg1->pNext->x>pegmax->pNext->x)

     pegmax=peg1;

    peg1=peg1->pNext;

   }

   pegi=pegmax->pNext;

   pegmax->pNext=pegi->pNext;

   pegi->pNext=pAET->pNext;

   pAET->pNext=pegi;

   if(peg0 == pAET)

    peg0=pegi;

  }

  // 周遊活邊表，畫線

  peg0=pAET;

  while(peg0->pNext)

  {

   if(peg0->pNext->pNext)

   {

    DrawLine((int)peg0->pNext->x,i,(int)peg0->pNext->pNext->x,i,pDC,nColor);

    peg0=peg0->pNext->pNext;

   }

   else

    break;

  }

  // 把ymax=i的節點從活邊表删除并把每個節點的x值遞增dx

  peg0=pAET;

  while(peg0->pNext)

  {

   if(peg0->pNext->ymax < i+2)

   {

    peg1=peg0->pNext;

    peg0->pNext=peg0->pNext->pNext; //删除

    delete peg1;

    continue;

   }

   peg0->pNext->x+=peg0->pNext->dx; //把每個節點的x值遞增dx

   peg0=peg0->pNext;

  }

 }

 // 删除邊表

 for(i=0;i<y1-y0;i++)

  if(pET[i])

   delete pET[i];

 if(pAET)

  delete pAET;

 if(pET)

  delete[] pET;

}