本文主要分析并实现了三种常见的多边形填充算法：逐点法、有序边表法和种子填充算法

1.逐点法

在逐点法实现中，用到了两个函数。

其中的实现原理十分简单，不过PointInPolygon(int pointNumOfPolygon, CPoint tarPolygon[], CPoint testPoint)函数的实现比较复杂，但这个函数也十分实用，在后面的三角剖分中也有使用。

算法描述：

（1）将给定多边形输入；

（2）求出多边形的最小包含矩形；

（3）逐点扫描最小矩形的每一点，并判断是否位于多边形内部，从最小点到最大点一次判断，如果在该多边形内部，则将该点上色；

（4）判断位于多边形内部的方法是，过每一点水平向右作射线，与多边形边界求交点，如果交点个数为奇数，则说明该点在多边形内部，偶数则说明在多边形外部。

效果如下：

计算机图形学——多边形区域填充算法 - 图1

实现代码：

  1. //逐点法填充
  2. void PointFillpoly(int pNumbers, CPoint *points, CDC *pDC)
  3. {
  4.      BoxRect_t polyRect;
  6.      polyRect = getPolygonRect(pNumbers, points);
  7.     m_pDC->MoveTo(polyRect.minX, polyRect.minY);
  9.     m_pDC->LineTo(polyRect.minX, polyRect.maxY);
  10.     m_pDC->LineTo(polyRect.maxX, polyRect.maxY);
  11.     m_pDC->LineTo(polyRect.maxX, polyRect.minY);
  12.     m_pDC->LineTo(polyRect.minX, polyRect.minY);
  14.     CPoint testPoint;
  15.     //从最小点到最大点一次判断，如果在该多边形内部，则进行填充
  16.     for (testPoint.x = polyRect.minX; testPoint.x < polyRect.maxX; testPoint.x++)
  17.         for (testPoint.y = polyRect.minY; testPoint.y < polyRect.maxY; testPoint.y++) {
  18.             if (PointInPolygon(m_pNumbers, m_pAccord, testPoint))
  19.                 pDC->SetPixel(testPoint.x, testPoint.y, RGB(255, 255, 255));
  20.         }
  21. }
  1. //得到该多边形的最大、最小的y、x值
  2. BoxRect_t getPolygonRect(int pointNumOfPolygon, CPoint tarPolygon[])
  3. {
  4.     BoxRect_t boxRect;
  6.     boxRect.minX = 50000;
  7.     boxRect.minY = 50000;
  8.     boxRect.maxX = -50000;
  9.     boxRect.maxY = -50000;
  11.     for (int i = 0; i < pointNumOfPolygon; i++) {
  12.         if (tarPolygon[i].x < boxRect.minX) boxRect.minX = tarPolygon[i].x;
  13.         if (tarPolygon[i].y < boxRect.minY) boxRect.minY = tarPolygon[i].y;
  14.         if (tarPolygon[i].x > boxRect.maxX) boxRect.maxX = tarPolygon[i].x;
  15.         if (tarPolygon[i].y > boxRect.maxY) boxRect.maxY = tarPolygon[i].y;
  16.     }
  17.     return boxRect;
  18. }
  1. //判断点是否位于区域内
  2. BOOL PointInPolygon(int pointNumOfPolygon, CPoint tarPolygon[], CPoint testPoint)
  3. {
  4.     if (pointNumOfPolygon < 3)
  5.         return false;
  7.     bool  inSide = FALSE;
  8.     float lineSlope, interSectX;
  9.     int   i = 0, j = pointNumOfPolygon - 1;
  11.     for (i = 0; i < pointNumOfPolygon; i++) {
  12.         if ((tarPolygon[i].y < testPoint.y && tarPolygon[j].y >= testPoint.y ||
  13.             tarPolygon[j].y < testPoint.y && tarPolygon[i].y >= testPoint.y) &&
  14.             (tarPolygon[i].x <= testPoint.x || tarPolygon[j].x <= testPoint.x)) {
  15.             if (tarPolygon[j].x != tarPolygon[i].x) {
  16.                 lineSlope = (float)(tarPolygon[j].y - tarPolygon[i].y) / (tarPolygon[j].x - tarPolygon[i].x);
  17.                 interSectX = (int)(tarPolygon[i].x + (testPoint.y - tarPolygon[i].y) / lineSlope);
  18.             }
  19.             else
  20.                 interSectX = tarPolygon[i].x;
  21.             if (interSectX < testPoint.x)
  22.                 inSide = !inSide;
  23.         }
  24.         j = i;
  25.     }
  27.     return inSide;
  28. }

2.有序边表法

首先给出有序边表法中定义使用的变量。

  1. int m_Begin, m_End, m_edgeNumbers, m_Scan;       //求交边集指针，有效边数，当前扫描位置
  2. float m_yMax[N], m_yMin[N], m_Xa[N], m_Dx[N];    //每条边y最大值，y最小值，每条边与扫描线x的交点，每条边斜率倒数

基本思想：用水平扫描线从上到下（或从下到上）扫描由多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。

  • 在实现中首先需要对多边形的每一条边进行处理操作，因为是采用水平线扫描填充，所以对于水平线不做处理。对其余边根据端点的y值大小进行排序，保存yMax，yMin，Xa(相对应的x坐标)以及Dx(斜率的倒数)。
  • 在进行扫描的过程中，很重要的一部分操作便是求交边集指针的移动。初始状态位0，在扫描线开始向下移动后，调用Include()函数，检查是否有边进入扫描线交集(即判断所有y最大值大于扫描线当前y值的边线)，此时将m_End++，即尾指针向后移动。在Include()函数中，也会调整起始点位置，将Dx调整为位移量。
  • 之后调用UpdateXvalue()函数，判断是否有边退出求交边集。
    • 如果没有边退出，则移动x，并根据x值大小进行排序。
    • 有边退出，更新数组，删除该边，m_Begin++，即头指针向后移动。
  • 调用pFillScan(pDC)函数，进行填充。
  • m_Scan–，回到第二步进行循环，直到m_Begin==m_End。

算法描述：

  • 建立边表的方法：

（1）与x轴平行的边不计入；

（2）多边形的顶点分为两大类：一类是局部极值点，另外一类是非极值点。当扫面线与第一类顶点相交时，应看作两个点；而当扫描线与第二类顶点相交时，应视为一个点，对于极值点则要记录两条边；

（3）扫描线按照y轴从低到高顺次记录；

（4）一条边按照y轴的高低记录；

（5）多条边以x轴递增顺序记录；

  • 算法流程：

1、根据给出的多边形顶点坐标，建立NET表，求出顶点坐标中最大y值ymax和最小y值ymin。

2、初始化AET表指针，使它为空。

3、执行下列步骤直至NET和AET都为空．

（1）如NET中的第y类非空，则将其中的所有边取出并插入AET中；

（2）如果有新边插入AET，则对AET中各边排序；

（3）对AET中的边两两配对，（1和2为一对，3和4为一对，…），

将每对边中x坐标按规则取整，获得有效的填充区段，再填充．

（4）将当前扫描线纵坐标y值递值1；

（5）如果AET表中某记录的ymax=yj，则删除该记录 （因为每条边被看作下闭上开的）；

（6）对AET中剩下的每一条边的x递增dx，即x’ = x+ dx ．

效果如下：

计算机图形学——多边形区域填充算法 - 图2

实现代码如下：

  1. //有序边表法填充
  2. void Fillpolygon(int pNumbers, CPoint* points, CDC* pDC)
  3. {
  4.     m_edgeNumbers = 0;
  5.     pLoadPolygon(pNumbers, points);   // Polygon Loading, calculates every edge's m_yMax[],m_yMin[],m_Xa[],m_Dx[]
  7.     //求交边集范围，因为数组已经根据y值大小进行边的排序，所以end向后移动即代表有边进入，start向后移动，代表有边退出
  8.     m_Begin = m_End = 0;
  9.     m_Scan = (int)m_yMax[0];          //从顶向下扫描
  10.     Include();                        //检查是否有边进入扫描线
  11.     UpdateXvalue();                   //检查是否有边退出扫描线
  12.     while (m_Begin != m_End) {
  13.         pFillScan(pDC);
  14.         m_Scan--;
  15.         Include();
  16.         UpdateXvalue();
  17.     }
  18. }
  1. void pLoadPolygon(int pNumbers, CPoint* points)
  2. {
  3.     float x1, y1, x2, y2;
  5.     x1 = points[0].x;    y1 = points[0].y + 0.5;
  6.     for (int i = 1; i < pNumbers; i++) {
  7.         x2 = points[i].x;    y2 = points[i].y + 0.5;
  8.         if (abs(int(y2 - y1)) >= 0)    //水平线不做处理
  9.         {
  10.             pInsertLine(x1, y1, x2, y2);
  11.             x1 = x2;      y1 = y2;
  12.         }
  13.         else
  14.             x2 = x1;
  15.     }
  16. }
  1. void pInsertLine(float x1, float y1, float x2, float y2)
  2. {
  3.     int i;
  4.     float Ymax, Ymin;
  6.     Ymax = (y2 > y1) ? y2 : y1;
  7.     Ymin = (y2 < y1) ? y2 : y1;
  8.     i = m_edgeNumbers;
  9.     //根据y值的大小，进行排序插入，大的在前面
  10.     while (i != 0 && m_yMax[i - 1] < Ymax) {
  11.         m_yMax[i] = m_yMax[i - 1];
  12.         m_yMin[i] = m_yMin[i - 1];
  13.         m_Xa[i] = m_Xa[i - 1];
  14.         m_Dx[i] = m_Dx[i - 1];
  15.         i--;
  16.     }
  17.     m_yMax[i] = Ymax;
  18.     m_yMin[i] = Ymin;
  19.     if (y2 > y1) m_Xa[i] = x2;    //根据y大小确定Xa的值，y大的会先于扫描线相交
  20.     else         m_Xa[i] = x1;
  22.     m_Dx[i] = (x2 - x1) / (y2 - y1);    //斜率的倒数
  23.     m_edgeNumbers++;
  24. }
  1. void Include()
  2. {
  3.     //end向后移动，找出所有边最高点y值大于当前扫描线的边，看是否有新的边进入交集
  4.     while (m_End < m_edgeNumbers && m_yMax[m_End] >= m_Scan) {
  5.         //有边进入，调整起始点位置，然后将Dx调整为位移量
  6.         m_Xa[m_End] = m_Xa[m_End] + (-0.5) * m_Dx[m_End];
  7.         m_Dx[m_End] = -m_Dx[m_End];
  8.         m_End++;
  9.     }
  10. }
  1. void UpdateXvalue()
  2. {
  3.     int i, start = m_Begin;
  5.     for (i = start; i < m_End; i++) {
  6.         if (m_Scan > m_yMin[i]) {
  7.             //当前边没有退出，则移动x，然后在进行排序
  8.             m_Xa[i] += m_Dx[i];
  9.             pXsort(m_Begin, i);
  10.         }
  11.         else {
  12.             //有边退出，更新数组，然后begin++
  13.             for (int j = i; j > m_Begin; j--) {
  14.                 m_yMin[j] = m_yMin[j - 1];
  15.                 m_Xa[j] = m_Xa[j - 1];
  16.                 m_Dx[j] = m_Dx[j - 1];
  17.             }
  18.             m_Begin++;
  19.         }
  20.     }
  21. }
  1. void pXsort(int Begin, int i)
  2. {
  3.     float temp;
  5.     while (i > Begin&& m_Xa[i] < m_Xa[i - 1]) {
  6.         temp = m_Xa[i];   m_Xa[i] = m_Xa[i - 1];   m_Xa[i - 1] = temp;
  7.         temp = m_Dx[i];   m_Dx[i] = m_Dx[i - 1];   m_Dx[i - 1] = temp;
  8.         temp = m_yMin[i]; m_yMin[i] = m_yMin[i - 1]; m_yMin[i - 1] = temp;
  9.         i--;
  10.     }
  11. }
  1. void pFillScan(CDC* pDC)
  2. {
  3.     int x, y;
  4.     FillPolyDoc* pDoc = GetDocument();
  5.     for (int i = m_Begin; i < m_End; i += 2) {
  6.         if (pDoc->m_displayMode == 1) {
  7.             pDC->MoveTo(m_Xa[i], m_Scan);
  8.             pDC->LineTo(m_Xa[i + 1], m_Scan);
  9.         }
  10.         else if (pDoc->m_displayMode == 4) {    //图案填充
  11.             y = m_Scan;
  12.             for (int x = m_Xa[i]; x < m_Xa[i + 1]; x++)
  13.                 if (m_patternData[y % 12][x % 12])
  14.                     pDC->SetPixel(x, y, RGB(255, 0, 0));
  15.         }
  16.     }
  17. }

3.种子填充算法

点填充有好几种方法，其中比较简单实现的是四连通泛填充算法。基本思路就是给定种子，然后去填充种子上下左右四个方向的像素点，如果为空，则进行填充。

实现代码如下：

  1. void FloodFill4(int x, int y, int fillColor, int oldColor)
  2. {
  3.     int current;
  4.     current = GetPixel(x,y);
  5.     if( current == oldColor ){
  6.         SetPixel(x,y,fillColor);
  7.         FloodFill4(x+1,y,fillColor,oldColor);
  8.         FloodFill4(x-1,y,fillColor,oldColor);
  9.         FloodFill4(x,y+1,fillColor,oldColor);
  10.         FloodFill4(x,y-1,fillColor,oldColor);
  11.     }
  12. }

不过如果运行这一段代码很容易就会导致栈溢出，，，虽然代码简单，但是没法用。

所以更多的是使用扫描线种子填充算法。

算法描述：

  1. 种子像素入栈。 当栈非空时，重复执行一下操作。
  2. 栈顶像素出栈。
  3. 沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止。
  4. 将上述区间内的最左、最右像素记为计算机图形学——多边形区域填充算法 - 图3和计算机图形学——多边形区域填充算法 - 图4
  5. 在区间[计算机图形学——多边形区域填充算法 - 图5 , 计算机图形学——多边形区域填充算法 - 图6]内检查与当前扫描线相邻的上下两条扫描线是否全为边界像素或已填充的像素，若为非边界和未填充，则把每一区间的最右像素计算机图形学——多边形区域填充算法 - 图7作为种子像素压入堆栈，重复执行上述操作。

效果如下：

计算机图形学——多边形区域填充算法 - 图8

实现代码如下：

  1. //扫描线种子填充
  2. int SetRP(int x, int y, COLORREF color, COLORREF mColor, CDC* pDC) {
  3.     while (pDC->GetPixel(CPoint(x, y)) == mColor) {
  4.         pDC->SetPixel(x, y, color);
  5.         x++;
  6.     }
  7.     return x - 1;
  8. }
  9. int SetLP(int x, int y, COLORREF color, COLORREF mColor, CDC* pDC) {
  10.     while (pDC->GetPixel(CPoint(x - 1, y)) == mColor) {
  11.         pDC->SetPixel(--x, y, color);
  12.     }
  13.     return x + 1;
  14. }
  1. void NewLineSeed(std::stack<CPoint>* stk, int lx, int rx, int y, COLORREF color, COLORREF mColor, CDC* pDC) {
  2.     int x, e, flag = 0;
  3.     for (x = lx + 1, e = rx + 1; x < e; x++) {
  4.         //找出每一个区间的最右像素，入栈
  5.         if (pDC->GetPixel(CPoint(x, y)) != mColor) {
  6.             if (pDC->GetPixel(CPoint(x - 1, y)) == mColor) {
  7.                 stk->push(CPoint(x - 1, y));
  8.                 flag = !flag;
  9.             }
  10.         }
  11.     }
  12.     //把rx所在点入栈
  13.     if (!flag && pDC->GetPixel(CPoint(x - 1, y)) == mColor)
  14.         stk->push(CPoint(x - 1, y));
  15. }
  1. void ScanLineFill4(int x, int y, COLORREF color, CDC* pDC)
  2. {
  3.     int pRight, pLeft;
  4.     std::stack<CPoint> stk;
  5.     int mColor = pDC->GetPixel(x, y);    //给定种子
  7.     stk.push(CPoint(x, y));
  8.     while (!stk.empty()) {
  9.         CPoint p = stk.top();    //栈顶像素出栈
  10.         stk.pop();
  12.         pRight = SetRP(p.x, p.y, color, mColor, pDC);    //向左向右进行填充
  13.         pLeft = SetLP(p.x, p.y, color, mColor, pDC);
  15.         //上下两条扫描线处理
  16.         NewLineSeed(&stk, pLeft, pRight, p.y + 1, color, mColor, pDC);
  17.         NewLineSeed(&stk, pLeft, pRight, p.y - 1, color, mColor, pDC);
  18.     }
  19. }
  1. void FloodFill4(int x, int y, int fillColor, int oldColor, CDC* pDC)
  2. {
  3.     int current;
  4.     current = pDC->GetPixel(x, y);
  5.     if (current == oldColor) {
  6.         pDC->SetPixel(x, y, fillColor);
  7.         FloodFill4(x + 1, y, fillColor, oldColor, pDC);
  8.         FloodFill4(x - 1, y, fillColor, oldColor, pDC);
  9.         FloodFill4(x, y + 1, fillColor, oldColor, pDC);
  10.         FloodFill4(x, y - 1, fillColor, oldColor, pDC);
  11.     }
  12. }