根据课件第三章中的“扫描线算法”原理,编制一任意二维多边形的填充程序。要求:无遗漏点,无重复点。并使用下列数据进行验证:(181, 306)、(144, 199)、( 20, 199)、(120, 133)、( 82, 26)、(181, 90)、(280, 26)、(242, 133)、(342, 199)、(218, 199)。

题目要求

题目要求

注:在提交开发工程的同时,需要提交一个说明文档。写出自己的编程思路、关键变量的意义、函数的功能、特殊情况的处理等,并附一张屏幕截图。

实现思路

(1) 基本思路是扫描线算法。

  • (a)求交:计算扫描线与多边形各边的交点;
  • (b)排序:把所有交点按x值递增顺序排序;
  • (c)配对:奇偶交点配对,每对交点代表扫描线与多边形的一个相交区间。
  • (d)着色:把相交区间内的象素置成多边形颜色。

(2)为了提高效率,在处理一条扫描线时,仅对与它相交的多边形的边进行求交运算。与当前扫描线相交的边称为活性边,把它们按与扫描线交点x坐标递增的顺序存放在一个链表中,此链表称为活性边表(AET)。在代码中,定义结构体用于活性边表AET和新边表NET,并构造了PolyScan函数进行了扫描过程。

C++源代码

#include<gl/glut.h> 
#include<windows.h> 
#include<iostream>
#include <string>  
#include<fstream>  //必要头文件
using namespace std;
const int POINTNUM = 10;      //多边形点数.  
float a[20];

void godBless(void)
{
    //                              _ooOoo_
    //                             o8888888o
    //                             88" . "88
    //                             (| -_- |)
    //                              O\ = /O
    //                           ____/`---'\____
    //                        .   ' \\| |// `.
    //                         / \\||| : |||// \
    //                        / _||||| -:- |||||- \
    //                         | | \\\ - /// | |
    //                       | \_| ''\---/'' | |
    //                        \ .-\__ `-` ___/-. /
    //                    ___`. .' /--.--\ `. . __
    //                  ."" '< `.___\_<|>_/___.' >'"".
    //                 | | : `- \`.;`\ _ /`;.`/ - ` : | |
    //                    \ \ `-. \_ __\ /__ _/ .-` / /
    //           ======`-.____`-.___\_____/___.-`____.-'======
    //                              `=---='
    //
    //           .............................................
    //                     佛祖保佑             永无BUG
}

//定义结构体用于活性边表AET和新边表NET
typedef struct XET
{
    float x;
    float dx, ymax;
    XET* next;
}AET, NET;

//定义点结构体point
struct point
{   
    float x;
    float y;
}polypoint[POINTNUM] = {181,306,144,199,20,199,120,133,82,26,181,90,280,26,242,133,342,199,218,199};

void PolyScan()
{
    //计算最高点的y坐标(扫描到此结束)
    float MaxY = 0;
    int i;
    for (i = 0; i < POINTNUM; i++)
        if (polypoint[i].y > MaxY)
            MaxY = polypoint[i].y;

    //初始化AET表
    AET* pAET = new AET;
    pAET->next = NULL;

    //初始化NET表
    NET* pNET[1024];
    for (i = 0; i <= MaxY; i++)
    {
        pNET[i] = new NET;
        pNET[i]->next = NULL;
    }
    glClear(GL_COLOR_BUFFER_BIT);        //赋值的窗口显示.    
    glColor3f(0.5, 0.5, 0.0);             //设置直线的颜色红色  
    glBegin(GL_POINTS);
    //扫描并建立NET表
    for (i = 0; i <= MaxY; i++)
    {
        for (int j = 0; j < POINTNUM; j++)
            if (polypoint[j].y == i)
            {                       //一个点跟前面的一个点形成一条线段,跟后面的点也形成线段     
                if (polypoint[(j - 1 + POINTNUM) % POINTNUM].y > polypoint[j].y)
                {
                    NET* p = new NET;
                    p->x = polypoint[j].x;
                    p->ymax = polypoint[(j - 1 + POINTNUM) % POINTNUM].y;
                    p->dx = (polypoint[(j - 1 + POINTNUM) % POINTNUM].x - polypoint[j].x) / (polypoint[(j - 1 + POINTNUM) % POINTNUM].y - polypoint[j].y);
                    p->next = pNET[i]->next;
                    pNET[i]->next = p;

                }
                if (polypoint[(j + 1 + POINTNUM) % POINTNUM].y > polypoint[j].y)
                {
                    NET* p = new NET;
                    p->x = polypoint[j].x;
                    p->ymax = polypoint[(j + 1 + POINTNUM) % POINTNUM].y;
                    p->dx = (polypoint[(j + 1 + POINTNUM) % POINTNUM].x - polypoint[j].x) / (polypoint[(j + 1 + POINTNUM) % POINTNUM].y - polypoint[j].y);
                    p->next = pNET[i]->next;
                    pNET[i]->next = p;
                }
            }
    }
    //建立并更新活性边表AET
    for (i = 0; i <= MaxY; i++)
    {
        //计算新的交点x,更新AET  
        NET* p = pAET->next;
        while (p)
        {
            p->x = p->x + p->dx;
            p = p->next;
        }
        //更新后新AET先排序
        //断表排序,不再开辟空间  
        AET* tq = pAET;
        p = pAET->next;
        tq->next = NULL;
        while (p)
        {
            while (tq->next && p->x >= tq->next->x)
                tq = tq->next;
            NET* s = p->next;
            p->next = tq->next;
            tq->next = p;
            p = s;
            tq = pAET;
        }              //                     (改进算法)先从AET表中删除ymax==i的结点
        AET* q = pAET;
        p = q->next;
        while (p)
        {
            if (p->ymax == i)
            {
                q->next = p->next;
                delete p;
                p = q->next;
            }
            else
            {
                q = q->next;
                p = q->next;
            }
        }                    //将NET中的新点加入AET,并用插入法按X值递增排序
        p = pNET[i]->next;
        q = pAET;
        while (p)
        {
            while (q->next && p->x >= q->next->x)
                q = q->next;
            NET* s = p->next;
            p->next = q->next;
            q->next = p;
            p = s;
            q = pAET;
        }                            //配对填充颜色

        p = pAET->next;
        while (p && p->next)
        {
            for (float j = p->x; j <= p->next->x; j++)
                glVertex2i(static_cast<int>(j), i);
            p = p->next->next;                  //考虑端点情况  
        }
    }
    glEnd();
    glFlush();
}
void init(void)
{
    glClearColor(1.0, 1.0, 1.0, 0.0);     //窗口的背景颜色设置为白色  
    glMatrixMode(GL_PROJECTION);
    gluOrtho2D(-100, 400.0, -100, 400);
}

void main(int argc, char* argv)
{   
    ReadNum();
    glutInit(&argc, &argv);                //初始化 GLUT.  
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);    //设置显示模式:单个缓存和使用RGB模型  
    glutInitWindowPosition(50, 50);        //设置窗口的顶部和左边位置  
    glutInitWindowSize(700, 700);        //设置窗口的高度和宽度  
    glutCreateWindow("SY2207105_");    //创建显示窗口  
    init();                                //调用初始化过程  
    glutDisplayFunc(PolyScan);        //图形的定义传递给我window.  
    glutMainLoop();                        //显示所有的图形并等待  
}

运行结果

最终运行结果


版权声明 ▶ 本网站名称:陶小桃Blog
▶ 本文链接:https://www.52txr.cn/2022/openglsaomioxian.html
▶ 本网站的文章部分内容可能来源于网络,仅供大家学习与参考,如有侵权,请联系站长进行核实删除。
▶ 转载本站文章需要遵守:商业转载请联系站长,非商业转载请注明出处!!
▶ 站长邮箱 [email protected][email protected] ,如不方便留言可邮件联系。

最后修改:2022 年 10 月 30 日
如果觉得我的文章对你有用,请随意赞赏