多边形填充算法实现

//

// 功能:  填充多边形

//

// 参数:  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;

}