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

    还是那份图形学作业。作业的要求使用4－种子填充算法，这个算法非常简单，但是效率很低，需要使用一个非常大的栈来进行保存。
    在无聊的时候，自己实现了扫描线种子填充算法。
（因为每种图形界面工具的绘图方式不同，此处用Qt 4.4实现）
void scanlineFill(seed)
{
    QColor oldColor = image->pixel(seed);        //获取填充点颜色
   
    if(oldColor == currentColor)            //要填充的颜色和原始颜色相同，不进行填充
    {
        return;
    }
   
    QStack<QPoint> *stack = new QStack<QPoint>();
    stack->push(seed);
   
    while(!stack->isEmpty())
    {
        QPoint currentPoint = stack->top();    //获取当前填充点
        stack->pop();                //去除栈顶点
        image->setPixel(currentPoint, currentColor.rgb());    //填充当前点
        QPoint leftPoint = currentPoint;
        QPoint rightPoint = 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();
        QPoint upleftPoint = leftPoint;
        QPoint uprightPoint = rightPoint;
        QPoint downleftPoint = leftPoint;
        QPoint downrightPoint = rightPoint;
       
        if(upleftPoint.y() > 0)            //还没有到图形的最上端，扫描在leftPoint和rightPoint 之间该条扫描线需要填充的点
        {
            upleftPoint.ry()--;        //扫描上一条扫描线
           
            bool fillArea = false;        //标记进入填充区域
            uprightPoint.ry()--;        //终点向上移动一个像素
            if(image->pixel(uprightPoint) != oldColor.rgb())    //填充终点不是填充点
            {
                uprightPoint.rx()--;                //向左移动一个像素
            }
            while(upleftPoint.x() <= uprightPoint.x())
            {
                QColor pointColor = 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()++;            //向下移动，扫描下一条扫描线
           
            bool fillArea = false;
            downrightPoint.ry()++;        //终点向上移动一个像素
            if(image->pixel(downrightPoint) != oldColor.rgb())    //填充终点不是填充点
            {
                downrightPoint.rx()--;                //向左移动一个像素
            }
            while(downleftPoint.x() <= downrightPoint.x())
            {
                QColor pointColor = 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()++;                    //向右移动一个像素
            }
        }
    }
   
    delete stack;
}