【代码】使用C++实现改进的有效边表算法。

算法的解释和一些细节晚一些再上传，先直接上代码：

如果有错误可以在评论区指出。

//由于opengl使用实数的坐标，所以，本程序将使用画线代替画点

#include<GL/glut.h>
#include<Windows.h>
#include<cmath>
#include<vector>
#include<list>
#include <iostream>


using namespace std;

class point2f {
public:
    float x;
    float y;
    point2f(float x, float y) : x(x),y(y){}
};

class line4bucket {
public:
    float x_st;//会变化
    int ymax;
    float dx;
    int ymin; // 由于有效边表算法，这个使用整数
    float x_ed;
    line4bucket(point2f p1,point2f p2) 
    {
        if (p1.y > p2.y)
        {
            ymax = p1.y;
            x_st = p2.x;
            ymin = p2.y;
            x_ed = p1.x;
        }
        else
        {
            ymax = p2.y;
            x_st = p1.x;
            ymin = p1.y;
            x_ed = p2.x;
        }
        dx=(p1.x - p2.x) / (p1.y - p2.y);
    };

    bool operator<(line4bucket p2)
    {
        return x_st < p2.x_st;
    }
    bool operator>(line4bucket p2)
    {
        return x_st > p2.x_st;
    }
};



void reshape(int x, int y)
{
    int dis = x > y ? y : x; //取小的
    glViewport(0, 0, dis, dis);
}

list<line4bucket> *bucket;
vector<point2f> point_list;
int maxY = -10086;

void initbucket() {
    int flag;
    int n;
    cout << "测试/按顺序输入顶点坐标/手动输入线段(0/1/2):\n";
    cin >> flag;
    switch (flag)
    {
    case 0:
        n = 7;
        point_list.push_back(point2f(3, 1));
        point_list.push_back(point2f(1, 7));
        point_list.push_back(point2f(3, 12));
        point_list.push_back(point2f(7, 8));
        point_list.push_back(point2f(12, 9));
        point_list.push_back(point2f(8, 1));
        point_list.push_back(point2f(6, 5));
        break;
    case 1:
        
        cout << "请输入顶点个数:\n";
        cin >> n;
        cout << "请输入顶点(x和y之间用空格或者逗号隔开):\n";
        for (int i = 0; i < n; i++)
        {
            float x, y;
            cin >> x >> y;
            point_list.push_back(point2f(x, y));
        }
        break;
    case 2:
        cout << "请输入线段个数:\n";
        cin >> n;
        cout << "请输入顶点坐标中y的最大值:\n";
        cin >> maxY;
        bucket = new list<line4bucket>[maxY + 1];
        cout << "请输入顶点(两个一组,x和y之间用空格或者逗号隔开):\n";
        for (int i = 0; i < n; i++)
        {
            float x1, y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            point2f p1 = point2f(x1, y1);
            point2f p2 = point2f(x2, y2);
            line4bucket tmpline = line4bucket(p1, p2);
            bucket[tmpline.ymin].push_back(tmpline);
        }
        return;
    default:
        n = 7;
        point_list.push_back(point2f(3, 1));
        point_list.push_back(point2f(1, 7));
        point_list.push_back(point2f(3, 12));
        point_list.push_back(point2f(7, 8));
        point_list.push_back(point2f(12, 9));
        point_list.push_back(point2f(8, 1));
        point_list.push_back(point2f(6, 5));
        break;
    }



    

    maxY=point_list[0].y;
    for (int i=1;i<n;i++)
    {
        if (point_list[i].y > maxY)
        {
            maxY = point_list[i].y;
        }
    }
    
    bucket = new list<line4bucket>[maxY+1];
    
    for (int i = 0; i < n; i++)
    {
        line4bucket tmpline = line4bucket(point_list[i], point_list[(i + 1)%n]);
        bucket[tmpline.ymin].push_back(tmpline);
    }
}



void draw()
{
    glClearColor(0.0, 0.0, 0.0, 0.0);
    glClear(GL_COLOR_BUFFER_BIT);
    
    

    list<line4bucket> tmplst;
    for (int i = 0; i <= maxY; i++)
    {
        //删除到达最高点的线
        auto jtr = tmplst.begin();
        while (jtr != tmplst.end())
        {

            if (i > (*jtr).ymax)
            {
                if (jtr == tmplst.begin())
                {
                    tmplst.erase(jtr);
                    jtr = tmplst.begin();
                    continue;
                }
                else
                {
                    auto tmpjtr = jtr;
                    jtr--;
                    tmplst.erase(tmpjtr);
                }
                
            }

            jtr++;
        }
        //加入
        auto itr = bucket[i].begin();
        while (itr != bucket[i].end())
        {
            //删除旧线段末尾与新线段起点重合的旧线段
            auto jtr = tmplst.begin();
            while (jtr != tmplst.end())
            {

                if (((*itr).x_st - (*jtr).x_ed) <= 1e-7 && (*itr).ymin == (*jtr).ymax && !isinf((*itr).dx))
                {
                    if (jtr == tmplst.begin())
                    {
                        tmplst.erase(jtr);
                        jtr = tmplst.begin();
                        continue;
                    }
                    else
                    {
                        auto tmpjtr = jtr;
                        jtr--;
                        tmplst.erase(tmpjtr);
                    }

                }

                jtr++;
            }
            
            if(!isinf((*itr).dx))
            tmplst.push_back((*itr));
            itr++;
        }
        
        //排序
        tmplst.sort();

        //绘制
        //先检查一下
        if (tmplst.size() % 2 != 0)
        {
            cerr << "出现错误！";
            exit(10);
        }
        //绘制
        glColor3f(1.0, 1.0, 1.0);//白色点
        glBegin(GL_LINES);
        list<line4bucket>::iterator jtr_last;
        list<line4bucket>::iterator jtrt;
        if (tmplst.empty())goto STEP;
        
        jtr_last = tmplst.begin();
        jtrt = tmplst.begin();
        jtrt++;
        cout << "y = " << i << endl;
        while (true)
        {
            //opengl窗口的坐标范围是(-1,1)，需要变换一下
            cout << "Draw(" << (*jtr_last).x_st << "," << (*jtrt).x_st << ")\n";
            glVertex2f(((*jtr_last).x_st) / ((float)20)-0.5, (((float)i) / ((float)20))-0.5);
            glVertex2f(((*jtrt).x_st) / ((float)20)-0.5, (((float)i) / ((float)20))-0.5);
            
            jtr_last++;
            jtr_last++;
            if (jtrt == tmplst.end())break;
            jtrt++;
            if (jtrt == tmplst.end())break;
            jtrt++;
            
        }
        cout << endl;
        
        STEP:
        //迭代
        for (auto jtr = tmplst.begin(); jtr != tmplst.end(); jtr++)
        {
            (*jtr).x_st += (*jtr).dx;
        }

    }

    glEnd();

    glFlush();
}

int main(int argc, char** argv)
{
    initbucket();
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGBA);
    glutInitWindowPosition(0, 0);
    glutInitWindowSize(500, 500);
    glutCreateWindow("多边形的扫描转换");
    glutDisplayFunc(draw);
    glutReshapeFunc(reshape);
    glutMainLoop();
    return 0;
}

/*

0 0 5 0
5 0 5 5
5 5 0 5
0 5 0 0
1 1 4 1
4 1 4 4
4 4 1 4
1 4 1 1
这是回字形线段输入

*/