[转载]图形填充——种子填充算法

   还是那份图形学作业。作业的要求使用4－种子填充算法，这个算法非常简单，但是效率很低，需要使用一个非常大的栈来进行保存。
   在无聊的时候，自己实现了扫描线种子填充算法。
（因为每种图形界面工具的绘图方式不同，此处用Qt 4.4实现）
void scanlineFill(seed)
{
    QColoroldColor =image->pixel(seed);      //获取填充点颜色
   
    if(oldColor==currentColor)         //要填充的颜色和原始颜色相同，不进行填充
    {
      return;
    }
   
   QStack<QPoint> *stack = newQStack<QPoint>();
   stack->push(seed);
   
   while(!stack->isEmpty())
    {
       QPointcurrentPoint =stack->top();   //获取当前填充点
      stack->pop();            //去除栈顶点
      image->setPixel(currentPoint,currentColor.rgb());   //填充当前点
       QPointleftPoint = currentPoint;
       QPointrightPoint = currentPoint;
      //对当前点左侧进行填充
      while(leftPoint.x() >0)      //没有超出图形左边界，继续向左遍历
       {
         leftPoint.rx()--;      //向左移一个单位
         if(image->pixel(leftPoint) ==oldColor.rgb())   //如果需要填充，则填充成当前颜色
          {
            image->setPixel(leftPoint,currentColor.rgb());
          }
         else            //如果不需要填充，则跳出循环
          {
            leftPoint.rx()++;
             break;
          }
       }
      //对当前点右侧进行填充
      while(rightPoint.x() < image->width()- 1)
       {
         rightPoint.rx()++;      //向右移一个单位
         if(image->pixel(rightPoint) == oldColor.rgb())
          {
            image->setPixel(rightPoint,currentColor.rgb());
          }
          else
          {
            rightPoint.rx()--;
             break;
          }
       }
//this->repaint();
       QPointupleftPoint = leftPoint;
       QPointuprightPoint = rightPoint;
       QPointdownleftPoint = leftPoint;
       QPointdownrightPoint = rightPoint;
      
      if(upleftPoint.y() >0)         //还没有到图形的最上端，扫描在leftPoint和rightPoint 之间该条扫描线需要填充的点
       {
         upleftPoint.ry()--;      //扫描上一条扫描线
         
          boolfillArea =false;      //标记进入填充区域
         uprightPoint.ry()--;      //终点向上移动一个像素
         if(image->pixel(uprightPoint) !=oldColor.rgb())   //填充终点不是填充点
          {
            uprightPoint.rx()--;            //向左移动一个像素
          }
         while(upleftPoint.x() <= uprightPoint.x())
          {
             QColorpointColor = image->pixel(upleftPoint);
             if(!fillArea&& pointColor ==oldColor)         //如果不在填充范围，但需要填充
             {
                fillArea =true;            //标记进入填充范围
             }
            
             if(fillArea&& pointColor !=oldColor)         //如果在填充范围，但不需要填充
             {
               upleftPoint.rx()--;            //向左回退一个像素
               stack->push(upleftPoint);         //将该点放入栈中
               upleftPoint.rx()++;            //将该点重新置为当前坐标
                fillArea =false;            //标记退出填充范围
             }
            
             if(fillArea&& upleftPoint.x() ==uprightPoint.x())   //如果在填充范围之内，也需要填充，但是是扫描范围的终点
             {
               stack->push(upleftPoint);         //将该点放入栈中
             }
            
            upleftPoint.rx()++;               //向右移动一个像素
          }
       }
      
      if(downleftPoint.y() <image->height() -1)   //还没有到图形的下边界
       {
         downleftPoint.ry()++;         //向下移动，扫描下一条扫描线
         
          boolfillArea = false;
         downrightPoint.ry()++;      //终点向上移动一个像素
         if(image->pixel(downrightPoint) !=oldColor.rgb())   //填充终点不是填充点
          {
            downrightPoint.rx()--;            //向左移动一个像素
          }
         while(downleftPoint.x() <= downrightPoint.x())
          {
             QColorpointColor = image->pixel(downleftPoint);
             if(!fillArea&& pointColor ==oldColor)         //如果不在填充范围，但需要填充
             {
                fillArea =true;            //标记进入填充范围
             }
            
             if(fillArea&& pointColor !=oldColor)         //如果在填充范围，但不需要填充
             {
               downleftPoint.rx()--;            //向左回退一个像素
               stack->push(downleftPoint);         //将该点放入栈中
               downleftPoint.rx()++;            //将该点重新置为当前坐标
                fillArea =false;            //标记退出填充范围
             }
            
             if(fillArea&& downleftPoint.x() ==downrightPoint.x())   //如果在填充范围之内，也需要填充，但是是扫描范围的终点
             {
               stack->push(downleftPoint);         //将该点放入栈中
             }
            
            downleftPoint.rx()++;               //向右移动一个像素
          }
       }
    }
   
    deletestack;
}