2.3 区域扫描线种子填充算法#

1. 任务描述#

根据下面要求，在右侧修改代码空间，绘制出预期输出的图片。平台会对你编写的代码进行测试。

本关任务#

1. 理解扫描线种子填充算法的原理。
2. 利用 VC + OpenGL 实现基本的多边形填充算法。
3. 调试、编译、修改程序。

运行前#

输出#

具体要求#

1. 对 FindNewSeed() 函数补全，实现新种子入栈功能。
2. 对 ScanLineFlood() 函数进行补全，最终实现多边形填充后的图片。

相关知识#

为了完成本关任务，你需要掌握：扫描线种子填充算法。

1. 扫描线填充算法基本思想#

在任意不间断区间（一条扫描线上的一组相邻像素）中，只取一个种子像素，填充当前扫描线上的该段区间，然后确定与这一段相邻的上下两条扫描线位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。

2. 具体算法步骤#

1. 初始化：堆栈置空，将种子点压入堆栈。
2. 出栈：若栈为空则结束，否则栈顶元素 (x, y) 出栈，并以 y 值作为当前扫描线号。
3. 填充并确定种子点所在区段：从种子 (x, y) 出发，沿当前扫描线向左、向右两个方向逐个像素填充，直到遇到边界像素为止。分别标记区段的左、右端点坐标 left 和 right。
4. 确定新的种子点：在区间 [left, right] 中检查与当前扫描线 y 相邻的上下两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最右像素作为种子点压入堆栈，返回第 2 步。否则直接返回第 2 步。

---

开始你的任务吧，祝你成功！

2. 我的回答#

文件 step4/test4.cpp:

// 评测代码所用头文件-开始
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
// 评测代码所用头文件-结束

// 提示：写完代码请保存之后再进行评测
#include <GL/freeglut.h>
#include <math.h>
#include <string>
#include <iostream>
#include <stack>
using namespace std;

const int POINTNUM = 5;

struct Point {
    int x;
    int y;
    Point() {}
    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }
} polypoint[POINTNUM];

int MaxY, MinY;//多边形顶点沿Y轴的最小值 and 最大值

int vis[400][400];//判断该坐标的点是否为填充色，0为背景色，1为填充色

void Init() {
    polypoint[0] = Point(100, 100);
    polypoint[1] = Point(100, 300);
    polypoint[2] = Point(200, 200);
    polypoint[3] = Point(300, 300);
    polypoint[4] = Point(300, 100);
}

void FindNewSeed(stack<Point>& s,int left,int right,int y) {
    for (int i = left + 1; i < right; i++) {
        if (vis[i][y] == 0) {
            int j = i + 1;
            while (vis[j][y] == 0)
                j++;
            i = j--;
            s.push(Point(j, y));
        }
    }
}

void ScanLineFlood(int x, int y) { 
    stack<Point> s;
    Point p;
    int left, right;
    s.push(Point(x, y));
    while (!s.empty()) {
        //栈顶元素出栈
        p = s.top();
        s.pop();
        //向左填充
        for (left = p.x; vis[left][p.y] != 1; left--) {
            glVertex2f(left, p.y);
            vis[left][p.y] = 1;
        }    
        //向右填充
        for (right = p.x + 1; vis[right][p.y] != 1; right++) { 
            glVertex2f(right, p.y);
            vis[right][p.y] = 1;
        }
        //在当前行的下一行寻找确定新的种子点
        FindNewSeed(s, left, right, p.y - 1); 
        //在当前行的上一行寻找确定新的种子点
        FindNewSeed(s, left, right, p.y + 1); 
    }
}

void BoundaryPoly() {
    int i, t, k, x, y;
    for (i = 0; i < POINTNUM; i++) {
        i == 0 ? t = POINTNUM - 1 : t = i - 1;
        if (polypoint[i].y >= polypoint[t].y) {
            MinY = polypoint[t].y;
            MaxY = polypoint[i].y;
            x = polypoint[t].x;
            if (polypoint[t].x == polypoint[i].x) {
                k = 0;
            }
            else
                k = (float)(polypoint[i].y - polypoint[t].y) / (float)(polypoint[i].x - polypoint[t].x);
        }
        else
        {
            MinY = polypoint[i].y;
            MaxY = polypoint[t].y;
            x = polypoint[i].x;
            if (polypoint[t].x == polypoint[i].x) {
                k = 0;
            }
            else
                k = (float)(polypoint[t].y - polypoint[i].y) / (float)(polypoint[t].x - polypoint[i].x);
        }
        for (y = MinY; y < MaxY; y++) {
            glVertex2f(x, y);
            vis[x][y] = 1;
            x += k;
        }
        if (polypoint[t].y == polypoint[i].y && polypoint[i].x > polypoint[t].x) {
            for (x = polypoint[t].x; x < polypoint[i].x; x++) {
                glVertex2f(x, polypoint[t].y);
                vis[x][y] = 1;
            }
        }
        else if (polypoint[t].y == polypoint[i].y && polypoint[i].x < polypoint[t].x) {
            for (x = polypoint[i].x; x < polypoint[t].x; x++) {
                glVertex2f(x, polypoint[t].y);
                vis[x][y] = 1;
            }
        }
    }
}

void MyDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3f(1.0f, 1.0f, 1.0f);
    glBegin(GL_POINTS);
    glColor3f(0.0, 1.0, 0.0);//设置颜色的函数
    //将边界用像素表示并输出；
    BoundaryPoly();
    ScanLineFlood(200, 150);
    glEnd();
    glFlush();
}

void MyReshape(int w, int h)
{
    glViewport(0, 0, (GLsizei)w, (GLsizei)h);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, (GLdouble)w, 0.0, (GLdouble)h);
}

int main(int argc, char* argv[])
{
    glutInit(&argc, argv);//窗口的初始化
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//窗口模式的设定
    glutInitWindowPosition(100, 100);//窗口位置的设定
    glutInitWindowSize(400, 400);//窗口大小的设定
    glutCreateWindow("多边形的扫描填充");

    Init();
    glutDisplayFunc(MyDisplay);//调用函数
    glutReshapeFunc(MyReshape);
    glutMainLoopEvent();
  
    /*************以下为评测代码，与本次实验内容无关，请勿修改**************/
    GLubyte* pPixelData = (GLubyte*)malloc(400 * 400 * 3);//分配内存
    GLint viewport[4] = {0};
    glReadBuffer(GL_FRONT);
    glPixelStorei(GL_UNPACK_ALIGNMENT, 4);
    glGetIntegerv(GL_VIEWPORT, viewport);
    glReadPixels(viewport[0], viewport[1], viewport[2], viewport[3], GL_RGB, GL_UNSIGNED_BYTE, pPixelData);

	cv::Mat img;
    std::vector<cv::Mat> imgPlanes;
    img.create(400, 400, CV_8UC3);
    cv::split(img, imgPlanes);
 
    for(int i = 0; i < 400; i ++) {
        unsigned char* plane0Ptr = imgPlanes[0].ptr<unsigned char>(i);
        unsigned char* plane1Ptr = imgPlanes[1].ptr<unsigned char>(i);
        unsigned char* plane2Ptr = imgPlanes[2].ptr<unsigned char>(i);
        for(int j = 0; j < 400; j ++) {
            int k = 3 * (i * 400 + j);
            plane2Ptr[j] = pPixelData[k];
            plane1Ptr[j] = pPixelData[k+1];
            plane0Ptr[j] = pPixelData[k+2];
        }
    }
    cv::merge(imgPlanes, img);
    cv::flip(img, img ,0); 
    cv::namedWindow("openglGrab");
    cv::imshow("openglGrab", img);
    //cv::waitKey();
    cv::imwrite("../img_step4/test.jpg", img);
	return 0;
}