精华内容
下载资源
问答
  • 多边形的有效边表填充算法,程序可运行,供计算机图形学学习者参考。
  • 有序边表法是常用的多边形填充方法,之前有大神提出了完整的链接,小弟进行研究后重新整理下了内容,所得代码如下或者参考Git,可能有不对之处,请各位大神指正: /********************** * 填充测试:有序边表...

    有序边表法是常用的多边形填充方法,之前有大神提出了完整的链接,小弟进行研究后重新整理下了内容,所得代码如下或者参考Git,可能有不对之处,请各位大神指正:  

    /**********************
     * 填充测试:有序边表法
     * 参照案例:https://blog.csdn.net/orbit/article/details/7368996
     * ********************/
    #include <iostream>
    #include <vector>
    #include <list>
    #include "assert.h"
    
    typedef struct tagPoint
    {
        int x;
        int y;
    
        tagPoint(int nx, int ny){
            x = nx;
            y = ny;
        }
    }Point;
    
    typedef std::vector<Point> Polygon;
    
    typedef struct tagEDGE
    {
        double xi;
        double dx;
        int ymax;
    }EDGE;
    
    void ScanLinePolygonFill(const Polygon& py, int color);
    void GetPolygonMinMax(const Polygon& py, int &ymin, int &ymax);
    void InitScanLineNewEdgeTable(std::vector<std::list<EDGE>> &slNet,
                                  const Polygon& py, int ymin, int ymax);
    void ProcessScanLineFill(std::vector<std::list<EDGE>> &slNet,
                             int ymin, int ymax, int color);
    
    void InsertNetListToAet(std::list<EDGE> &edges, std::list<EDGE> &aet);
    void FillAetScanLine(std::list<EDGE> &aet, int y, int color);
    void RemoveNonActiveEdgeFromAet(std::list<EDGE>& aet, int y);
    void UpdateAndResortAet(std::list<EDGE>& aet);
    bool EdgeXiComparator(EDGE& e1, EDGE& e2){return e1.xi <= e2.xi;}
    
    int main()
    {
        Polygon py;
        py.push_back(Point(1,1));
        py.push_back(Point(1,3));
        py.push_back(Point(4,4));
        py.push_back(Point(7,3));
        py.push_back(Point(7,2));
        py.push_back(Point(7,1));
        py.push_back(Point(4,2));
    
        ScanLinePolygonFill(py, 1);
        return 0;
    }
    
    //主填充函数
    void ScanLinePolygonFill(const Polygon &py, int color){
        assert(py.size());
    
        int ymin = 0;
        int ymax = 0;
        GetPolygonMinMax(py, ymin, ymax);
        std::vector<std::list<EDGE>> slNet(ymax - ymin + 1);
        InitScanLineNewEdgeTable(slNet, py, ymin, ymax);
        //HorizonEdgeFill(py, color); //水平边填充
        ProcessScanLineFill(slNet, ymin, ymax, color);
    }
    
    void GetPolygonMinMax(const Polygon &py, int &ymin, int &ymax){
        ymax = ymin = py.at(0).y;
        for (int i = 0; i < py.size(); i++)
        {
            int ty = py.at(i).y;
            ymin = ty > ymin ? ymin : ty;
            ymax = ty < ymax ? ymax : ty;
        }
    }
    
    //初始化边表
    void InitScanLineNewEdgeTable(std::vector<std::list<EDGE>> &slNet, const Polygon &py, int ymin, int ymax){
        EDGE e;
        for (int i = 0; i < py.size(); i++)
        {
            const Point& ps = py.at(i);
            const Point& pe = py.at((i + 1) % py.size());
            const Point& pss = py.at((i - 1 + py.size()) % py.size());
            const Point& pee = py.at((i + 2 + py.size()) % py.size());
    
            if (pe.y != ps.y) //仅处理非水平线
            {
                e.dx = double(pe.x - ps.x) / double(pe.y - ps.y);
                if (pe.y > ps.y)
                {
                    e.xi = ps.x;
    //                if (pee.y >= pe.y)
    //                    e.ymax = pe.y - 1;
    //                else
                        e.ymax = pe.y;
    
                    slNet[ps.y - ymin].push_front(e);
                }
                else
                {
                    e.xi = pe.x;
    //                if (pss.y >= ps.y)
    //                    e.ymax = ps.y - 1;
    //                else
                        e.ymax = ps.y;
                    slNet[pe.y - ymin].push_front(e);
                }
            }
        }
    }
    
    //进行非水平线段的填充
    void ProcessScanLineFill(std::vector<std::list<EDGE> > &slNet,
                             int ymin, int ymax, int color)
    {
        std::list<EDGE> aet;
        for (int y = ymin; y < ymax; y++)
        {
            InsertNetListToAet(slNet[y-ymin], aet);//从新边表中取值给活动边表
            FillAetScanLine(aet, y, color);        //进行填充
            RemoveNonActiveEdgeFromAet(aet, y + ymin);    //删除非活动边(这里应该修复为y+ymin)
            UpdateAndResortAet(aet);               //更新活动边表中的xi值,并根据xi重新排序
        }
    }
    
    //从新边表(NET)中构建活动边表(AET)
    void InsertNetListToAet(std::list<EDGE> &edges, std::list<EDGE> &aet){
        if (edges.size() == 0) return;
    
        aet.push_back(*(edges.cbegin()));
        std::list<EDGE>::iterator i;
        for ( i = (++edges.begin()); i != edges.end(); i++)
        {
            double tx = i->xi;
            bool tb = false;
            for (std::list<EDGE>::iterator j = aet.begin(); j != aet.end(); j++)
            {
                if (j->xi > tx)
                {
                    aet.insert(j, *i);
                    tb = true;
                    break;
                }
            }
    
            if (!tb) aet.push_back(*i);
        }
    }
    
    void FillAetScanLine(std::list<EDGE> &aet, int y, int color){
        std::list<EDGE>::iterator itrator = aet.begin();
        std::cout << "In height " << y;
        do{
           std::cout << " " << itrator->xi;
           itrator++;
        }while(aet.end() != itrator);
        std::cout << std::endl;
    }
    
    void RemoveNonActiveEdgeFromAet(std::list<EDGE> &aet, int y){
        std::list<EDGE> aetT;
        std::list<EDGE>::iterator i;
        for (i = aet.begin(); i != aet.end(); i++)
        {
            if (i->ymax > y)
                aetT.push_back(*i);
        }
        aet.swap(aetT);
    }
    
    void UpdateAndResortAet(std::list<EDGE>& aet){
        std::list<EDGE>::iterator i;
        for (i = aet.begin(); i != aet.end(); i++)
            i->xi += i->dx;
        aet.sort(EdgeXiComparator);
    }
    

     

    展开全文
  • 计算机图形学实验三:多边形填充算法之活性边表方法实现 解救众多被计算机图形学实验所困扰的学生党们,本博客仅粘贴代码,活性边表实现多边形填充的原理请自行百度或Google,网上从来不缺原理。 注意,本博客中的...

    计算机图形学实验三:多边形填充算法之活性边表方法实现

    解救众多被计算机图形学实验所困扰的学生党们,本博客仅粘贴代码,活性边表实现多边形填充的原理请自行百度或Google,网上从来不缺原理。
    注意,本博客中的代码运行不能实现含有内多边形如‘’字型多边形。
    ps:该实现结果为放大二十倍之后的结果,如果要更改放大倍数请修改函数Polyscan中末尾几行的代码glVertex2i(static_cast(j) * 20, i * 20); 内的扩大倍数20,同时将init函数中用于绘制表格的两个for循环函数中的x += 20及y += 20 的20改为你扩大的倍数。

    代码在此,参考为上,借鉴最佳

    #include "pch.h"
    #include <iostream>
    #include<windows.h>
    #include<GL/glut.h>
    
    const int POINTNUM = 4;      //多边形点数.
    const int WindowWidth = 600, WindowHeight = 320;
    
    //bresenham算法,用于多边形的绘制
    void BresenhamLine(int x0, int y0, int x1, int y1) {
    	int x01 = x0 * 20, y01 = y0 * 20, x11 = x1 * 20, y11 = y1 * 20;
    	int dx = x11 - x01, dy = y11 - y01;
    	if (dx == 0) {
    		if (dy < 0) {
    			int tempx0 = x01, tempy0 = y01;
    			x01 = x11, y01 = y11;
    			x11 = tempx0, y11 = tempy0;
    		}
    		for (int y = y01; y <= y11;) {
    			glVertex2i(x01, y);
    			y += 20;
    		}
    	}
    	else {
    		if (((dy > dx) && (dx < 0) && (dy * dx > 0)) || ((dy < dx) && (dy > 0))) {  //0<k<1
    			int tempy = y01;
    			int e = -dx;
    			if (dx < 0) {
    				int tempx0 = x01, tempy0 = y01;
    				x01 = x11, y01 = y11;
    				x11 = tempx0, y11 = tempy0;
    				dx = x11 - x01, dy = y11 - y01;
    				e = -dx;
    				tempy = y01;
    			}
    			for (int x = x01; x <= x11;) {
    				if (e < 0) {
    					glVertex2i(x, tempy);
    					e = e + 2 * dy;
    					x = x + 20;
    				}
    				else
    				{
    					e = e - 2 * dx;
    					tempy = tempy + 20;
    					glVertex2i(x, tempy);
    					e = e + 2 * dy;
    					x = x + 20;
    				}
    			}
    		}
    		else if (((dy < dx) && (dx < 0)) || ((dy > dx) && (dx > 0))) {  //k>1
    			int tempx = x01;
    			int e = -dy;
    			if (dx < 0) {
    				int tempx0 = x01, tempy0 = y01;
    				x01 = x11, y01 = y11;
    				x11 = tempx0, y11 = tempy0;
    				dx = x11 - x01, dy = y11 - y01;
    				e = -dy;
    				tempx = x01;
    			}
    			for (int y = y01; y <= y11;) {
    				if (e < 0) {
    					glVertex2i(tempx, y);
    					e = e + 2 * dx;
    					y = y + 20;
    				}
    				else
    				{
    					e = e - 2 * dy;
    					tempx = tempx + 20;
    					glVertex2i(tempx, y);
    					e = e + 2 * dx;
    					y = y + 20;
    				}
    			}
    		}
    		else if (((dy + dx < 0) && (dx > 0)) || ((dy + dx > 0) && (dx < 0))) {  //k<-1
    			int tempx = x01;
    			int e = -dy;
    			if (dy < 0) {
    				int tempx0 = x01, tempy0 = y01;
    				x01 = x11, y01 = y11;
    				x11 = tempx0, y11 = tempy0;
    				dx = x11 - x01, dy = y11 - y01;
    				e = -dy;
    				tempx = x01;
    			}
    			for (int y = y01; y <= y11;) {
    				if (e < 0) {
    					glVertex2i(tempx, y);
    					e = e - 2 * dx;
    					y = y + 20;
    				}
    				else
    				{
    					e = e - 2 * dy;
    					tempx = tempx - 20;
    					glVertex2i(tempx, y);
    					e = e - 2 * dx;
    					y = y + 20;
    				}
    			}
    		}
    		else {     //-1 < k <0
    			int tempy = y01;
    			int e = -dx;
    			if (dx < 0) {
    				int tempx0 = x01, tempy0 = y01;
    				x01 = x11, y01 = y11;
    				x11 = tempx0, y11 = tempy0;
    				dx = x11 - x01, dy = y11 - y01;
    				e = -dx;
    				tempy = y01;
    			}
    			for (int x = x01; x <= x11;) {
    				if (e < 0) {
    					glVertex2i(x, tempy);
    					e = e - 2 * dy;
    					x = x + 20;
    				}
    				else
    				{
    					e = e - 2 * dx;
    					tempy = tempy - 20;
    					glVertex2i(x, tempy);
    					e = e - 2 * dy;
    					x = x + 20;
    				}
    			}
    		}
    	}
    }
    
    //定义活性边表AET和新边表NET
    typedef struct ET
    {
    	float x;
    	float dx, ymax;
    	ET* next;
    } AET, NET;
    
    //定义点结构体point
    struct point
    {
    	float x;  float y;
    } polypoint[POINTNUM] = { {1,5},{25,5},{20,12},{10,12}}; //多边形顶点
      //polypoint[POINTNUM] = { {250,50},{550,150},{560,400},{250,250} };
    
    void PolyScan()
    {
    	int linelength = sizeof(polypoint) / sizeof(polypoint[0]);
    	for (int i = 0; i < linelength; i++) {
    		if ((i + 1) == linelength) {
    			BresenhamLine(polypoint[i].x, polypoint[i].y, polypoint[0].x, polypoint[0].y);
    		}
    		else {
    			BresenhamLine(polypoint[i].x, polypoint[i].y, polypoint[i + 1].x, polypoint[i + 1].y);
    		}
    	}
    
    	//计算最高点的y坐标
    	int 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[40];
    	for (i = 0; i <= MaxY; i++)
    	{
    		pNET[i] = new NET;
    		pNET[i]->next = NULL;
    	}
    
    	glClear(GL_COLOR_BUFFER_BIT);   
    	//glColor3f(1.0, 0.0, 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) * 20, i * 20);
    			p = p->next->next;//考虑端点情况
    		}
    	}
    	glEnd();
    	glFlush();
    }
    
    void resetSize(int w, int h)
    {
    	glutReshapeWindow(WindowWidth, WindowHeight);
    }
    
    void init(int argc, char** argv)
    {
    	glutInit(&argc, argv);  //I初始化 GLUT.
    	glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);  //设置显示模式:单个缓存和使用RGB模型
    	glutInitWindowPosition(50, 50);  //设置窗口的顶部和左边位置
    	glutInitWindowSize(WindowWidth, WindowHeight);  //设置窗口的高度和宽度
    	glutCreateWindow("多边形填充");
    
    	//glClearColor(1.0, 1.0, 1.0, 0); //窗口背景颜色为白色
    	//glMatrixMode(GL_PROJECTION);
    	gluOrtho2D(0, WindowWidth, 0, WindowHeight);
    	//glBegin(GL_POINTS);
    	glClear(GL_COLOR_BUFFER_BIT);
    	glColor3f(0.2, 0.1, 0.1);
    	glPointSize(2);
    	glBegin(GL_POINTS);
    	for (int x = (-WindowWidth); x < WindowWidth; x++) {
    		for (int y = (-WindowHeight); y < WindowHeight; y += 20) {
    			glVertex2i(x, y);
    		}
    	}
    	for (int y = (-WindowHeight); y < WindowHeight; y++) {
    		for (int x = (-WindowWidth); x < WindowWidth; x += 20) {
    			glVertex2i(x, y);
    		}
    	}
    	glEnd();
    }
    
    void myDisplay(void)
    {
    	//glClear(GL_COLOR_BUFFER_BIT);
    	glColor3f(0.7, 0.7, 0.6);
    	glPointSize(2);
    	glBegin(GL_POINTS);
    	glVertex2i(0, 0);
    	PolyScan();
    	glEnd();
    	
    	
    	glFlush();
    }
    
    
    int main(int argc, char** argv)
    {
    	init(argc, argv);
    	glutDisplayFunc(myDisplay);        //图形的定义传递给我window.
    	glutMainLoop();
    	return 0;
    }
    
    

    pch.h文件源码

    #ifndef PCH_H
    #define PCH_H
    
    // TODO: 添加要在此处预编译的标头
    
    #endif //PCH_H
    

    另外,博主在做实验时参考了网上的部分代码以及室友的各种版本的建议,如有雷同,不是巧合,是兄贵的一手好代码造福了我,感谢兄贵。如果实在不喜,请联系删除。

    展开全文
  • 多边形扫描转换算法中的边表(Edge Table, ET)

    千次阅读 多人点赞 2019-05-20 12:10:00
    我们在初始化时建立一个全局的边表(ET),它包含多个,它包含多边形的所有边,并且这些边按照它们各自y坐标较小值排序。 一般地,ET是基于桶排序的方式建立的,有多少扫描线就有多少个桶。在每个桶中,根据边的较低的...

    目录

    边表(Edge Table, ET)

    在多边形的扫描转换算法中,我们首先需要建立一个全局的边表(ET),它包含多边形的所有边并且这些边按照它们各自y坐标较小值( y m i n y_{min} ymin)排序
    有资料也把这个全局的边表称为新边表(New Edge Table, NET),但是意思是一样的,即多边形扫描转换算法初始化时建立的全局边表。

    ET是基于桶排序的方式建立的,有多少扫描线就有多少个桶(一般在最下面的桶下面再多加一个,看下面的例子就知道是什么意思了),每一个桶对应一个链表,每一个链表中的边的下端端点的纵坐标是相同的。然后在每个桶中,根据边的较低的端点的x坐标( x m i n x_{min} xmin),按照增序的方式对边进行排序。

    ET(边表)中每一个链表的节点(每个节点对应一条边)包含下列信息:

    • 边的 y m a x y_{max} ymax坐标值
    • 边的下端端点的x坐标 x m i n x_{min} xmin
      注意这里 x m i n x_{min} xmin is the x at the minimum y for the edge, not necessarily the minimum x of the edge. Hence x m i n = 7 x_{min} = 7 xmin=7 for edge AB in 图3.14.
    • 随着扫描线递变到下一条线时的x坐标的增量1/m, (斜率的导数,m是斜率,slope)

    形象的展示一下:

    y m a x y_{max} ymax x m i n x_{min} xmin1/m

    边表包含所有的边

    • sorted by their smaller y coordinate of edge. ( y m i n y_{min} ymin)
    • If smaller y coordinates of edge are equal
      • edges are sorted in order of increasing x coordinate of the lower endpoint of edge. ( x m i n x_{min} xmin)
    • And if two x coordinates of the lower endpoint of edge are equal
      • edges are sorted according to the slope(斜率) of edge. ( m m m)

    总结一下如何构建边表
    1.按照每条边的 y m i n y_{min} ymin进行桶排序。
    2.在一个桶中,按照 x m i n x_{min} xmin递增的顺序进行排序。
    3.如果 x m i n x_{min} xmin也相同,那就按照边的斜率递增的顺序进行排列。

    光说不练假把式。
    下图中有个多边形ABCDEF,
    在这里插入图片描述
    格点的坐标写上去之后就是下面这个图。
    在这里插入图片描述
    该多边形的边表(ET)如下:
    在这里插入图片描述
    1.有多少条扫描线就有多少桶。
    最低点是1, 我不知道为什么要把0也写上,暂时就多写一个吧。
    最高点是11, 所以扫描线最高是11,没有问题

    2.根据每个边的 y m i n y_{min} ymin对边进行桶排序
    一共有多少个 y m i n y_{min} ymin?,分别是多少?对应那几条边?

    1 -> AB, BC
    3 -> FA
    5 -> CD
    7 -> EF, DE 
    

    所以0,2,4,6,8,9,10,11都是空的,这里用 λ \lambda λ进行占位。(为什么要用 λ \lambda λ,记住就好了)。

    3.如果边的 y m i n y_{min} ymin相同,则按照 x m i n x_{min} xmin的顺序进行排列。(这个我感觉是针对水平边的,因为水平边是被忽略的,这样以来,水平边的两个端点的 x m i n x_{min} xmin就不同了)

    4.如果边的 y m i n y_{min} ymin x m i n x_{min} xmin都相同,则按照边的斜率进行排序。
    所以这就是扫描线7,中EF排在前,DE排在后的原因了。

    OK,到此多边形扫描转换中的边表就讲清楚了,接下来讲解活性边表(Active Edge Table, AET)

    展开全文
  • 1、实 验 报 告一、 实验目的1、 掌握有序边表算法填充多边形区域;2、 理解多边形填充算法的意义;3、 增强C语言编程能力。二、 算法原理介绍根据多边形内部点的连续性知:一条扫描线与多边形的交点中,入点和出点...

    《《计算机图形学》有序边表填充算法》由会员分享,可在线阅读,更多相关《《计算机图形学》有序边表填充算法(10页珍藏版)》请在人人文库网上搜索。

    1、实 验 报 告一、 实验目的1、 掌握有序边表算法填充多边形区域;2、 理解多边形填充算法的意义;3、 增强C语言编程能力。二、 算法原理介绍根据多边形内部点的连续性知:一条扫描线与多边形的交点中,入点和出点之间所有点都是多边形的内部点。所以,对所有的扫描线填充入点到出点之间所有的点就可填充多边形。判断扫描线上的点是否在多边形之内,对于一条扫描线,多边形的扫描转换过程可以分为四个步骤:(1)求交:计算扫描线与多边形各边的交点;(2)排序:把所有交点按x值递增顺序排序;(3)配对:第一个与第二个,第三个与第四个等等;每对交点代表扫描线与多边 形的一个相交区间;(4)着色:把相交区间内的象素置成多。

    2、边形颜色,把相交区间外的象素置成背景色。p1,p3,p4,p5属于局部极值点,要把他们两次存入交点表中。 如扫描线y=7上的交点中,有交点(2,7,13),按常规方法填充不正确,而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2,p6为非极值点,则不用如上处理。为了提高效率,在处理一条扫描线时,仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边,并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中,称此链表为活性边表(AET)。 对每一条扫描线都建立一个与它相交的多边形的活性边表(AET)。每个AET的一个节点代表一条活性边,它包含三项内容1. x -当前扫描。

    3、线与这条边交点的x坐标;2. x -该边与当前扫描线交点到下一条扫描线交点的x增量;3. ymax -该边最高顶点相交的扫描线号。每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。当扫描线y移动到下一条扫描线y = y+1时,活性边表需要更新,即删去不与新扫描线相交的多边形边,同时增加与新扫描线相交的多边形边,并根据增量法重新计算扫描线与各边的交点x。当多边形新边表ET构成后,按下列步骤进行:1 对每一条扫描线i,初始化ET表的表头指针ETi;2 将ymax = i的边放入ETi中;3 使y =多边形最低的扫描线号;4 初始化活性边表AET为空;5 循环,直到。

    4、AET和ET为空。l 将新边表ET中对应y值的新边节点插入到AET表。l 遍历AET表,将两两配对的交点之间填充给定颜色值。l 遍历AET表,将 ymax= y的边节点从AET表中删除,并将ymax y的各边节点的x值递增x;并重新排序。l y增加1。三、 程序源代码#include graphics.h#define WINDOW_HEIGHT 480#define NULL 0#include alloc.h#include stdio.h#include dos.h#include conio.htypedef struct tEdge /*typedef是将结构定义成数据类型*/ in。

    5、t ymax; /* 边所交的最高扫描线号 */float x; /*当前扫描线与边的交点的x值 */float dx; /*从当前扫描线到下一条扫描线之间的x增量*/struct tEdge *next;Edge;typedef struct pointint x,y;POINT;/*将结点插入边表的主体函数*/void InsertEdge(Edge *list,Edge *edge)/*活性边edge插入活性边表list中*/ Edge *p,*q=list;p=q-next; /*记住q原来所指之结点*/while(p!=NULL) /*按x值非递减顺序增加边表*/if(edge-xx。

    6、) /*要插入的边的x较大不应该在当前插入*/p=NULL; else /*要插入的边的x较小应该在当前插入*/q=p;p=p-next;edge-next=q-next; /*使欲插入之结点edge指向q原来所指之结点*/q-next=edge; /*使q指向插入之结点*/int yNext(int k,int cnt,POINT *pts) /*对于多边形中的某个顶点序号k(0,1.6),返回下一顶点的纵坐标,如果这2个顶点所在边是 水平的,则顺延,即返回第(k+2)个顶点的纵坐标),cnt是顶点个数+1,pts指向多边形顶点结构体的指针*/int j;if(k+1)(cnt-1)/*当前。

    7、顶点为最后一个顶点,则下一个顶点为第0个顶点 */j=0;elsej=k+1; /*当前顶点不是最后一个顶点,下一个顶点为数组下标加一*/while(ptsk.y=ptsj.y)/*扫描线扫过平行顶点,需分情况找到当前顶点下下个顶点*/if(j+1)(cnt-1)j=0;elsej+;return(ptsj.y); /*返回下一个顶点的y值 */* 计算增量,修改AET*/*生成边表结点,并插入到边表中的主体函数*/void MakeEdgeRec(POINT lower,POINT upper,int yComp,Edge *edge,Edge *edges) /*把边结点edge,放到lo。

    8、wer.y扫描线所在的边结点指针数组edges中 */edge-dx=(float)(upper.x-lower.x)/(upper.y-lower.y);edge-x=lower.x;if(upper.yymax=upper.y-1; /*缩短上层顶点*/*奇点,应该把这点当作两个点而分开,所以把y的最大值减一,向下移动*/elseedge-ymax=upper.y; /*不是奇点,不需改变y值 */insertEdge(edgeslower.y,edge); /*插入一个边缘扫描线,插入到列表 */ /*创建边表的主体函数*/void BuildEdgeList(int cnt,POINT。

    9、 *pts,Edge *edges) /*建立新边表,cnt:多边形顶点个数+1,edges:指向活性边结点的指针数组*/Edge *edge;POINT v1,v2;int i,yPrev=ptscnt-2.y;/*当前顶点的前一个顶点的y值,在当前顶点不是奇点时使用该参数*/v1.x=ptscnt-1.x;v1.y=ptscnt-1.y;for(i=0;inext; /*查找当前扫描线对应的y桶*/while(p) /*y桶不空*/q=p-next; /*找到最后一个边结点,插入*/InsertEdge(active,p); /*把更新后的边表重新插入边表中保存*/p=q;/*填充一对交点。

    10、的主体函数*/void FillScan(int scan,Edge *active,int color) /*填充扫描线:填充扫描线上,且在下一结点到再下一结点之间的点*/Edge *p1,*p2;int i;p1=active-next;while(p1)p2=p1-next;for(i=p1-x;ix;i+)putpixel(int)i,scan,color); /*画出图形内部的点*/p1=p2-next; /*活性表的下一条边表 */void DeleteAfter(Edge *q) /*删除链表中结点,删除边结点q的后续结点p*/ Edge *p=q-next;q-next=p-n。

    11、ext; /*删除结点*/free(p);/* 删除 y=ymax 的边 */*填充完后,更新活动边表的主体函数*/void UpdateActiveList(int scan,Edge *active) /*删除扫描线scan完成交点计算的活性边,同时更新交点x域*/Edge *q=active,*p=active-next;while(p)if(scan=p-ymax) /*扫描线超过边的最大y值,此条边的节点应该删掉*/p=p-next;deleteAfter(q);else /*扫描线未超过边的最大y值,相应的x值增加*/p-x=p-x+p-dx;q=p;p=p-next;/*对活性边。

    12、表结点重新排序的主体函数*/void ResortActiveList(Edge *active) /*活性边表active中的结点按x域从小到大重新排序*/Edge *q,*p=active-next;active-next=NULL;while(p)q=p-next;InsertEdge(active,p); /*把更新后的边表重新插入边表中保存 */p=q;/*多边形填充的主体程序*/void ScanFill(int cnt,POINT *pts,int color) /*填充函数,输入:多边形顶点个数+1=cnt, 指向多边形顶点的指针数组pts*/Edge *edgesWINDOW。

    13、_HEIGHT,*active;int i,scan,scanmax=0,scanmin=WINDOW_HEIGHT;for(i=0;iptsi.y)scanmin=ptsi.y;for(scan=scanmin;scannext=NULL;BuildEdgeList(cnt,pts,edges); /*建立有序边表*/active=(Edge *)malloc(sizeof(Edge);active-next=NULL;for(scan=scanmin;scannext) /*活性边表不为空*/FillScan(scan,active,color); /*填充当前扫描线*/UpdateAct。

    14、iveList(scan,active); /*更新活化边表*/ResortActiveList(active); /*重排活化边表*/*开始菜单*/void main() POINT pts7; /*保存数组*/int gdrive=DETECT,gmode;pts0.x=100;pts0.y=40; /*多边形顶点x、y坐标*/pts1.x=220;pts1.y=140;pts2.x=280;pts2.y=80;pts3.x=350;pts3.y=300;pts4.x=200;pts4.y=380;pts5.x=50;pts5.y=280;pts6.x=100;pts6.y=40; /*合。

    15、并桶中的新边,按次序插入到 AET 中*/ initgraph(&gdrive,&gmode,C:TC3.0BGI); /*设置graphic模式*/ScanFill(7,pts,2);getch();四、 实验结果图1 用有序边表算法生成的多边形五、 总结与体会实验步骤1) 分析多边形区域扫描线填充算法的原理,确定算法流程1 初始化:构造边表,AET表置空2 将第一个不空的ET表中的边插入AET表3 由AET表取出交点进行配对(奇偶)获得填充区间,依次对这些填充区间着色4 y=yi+1时,根据x=xi+1/k修改AET表所有结点中交点的x坐标。同时如果相 应的ET表不空,则将其中的结点插入A。

    16、ET表,形成新的AET表5 AET表不空,则转(3),否则结束。2) 编程实现1 首先确定多边形顶点和ET/AET表中结点的结构2 编写链表相关操作(如链表结点插入、删除和排序等)3 根据1)中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体功能4 编写主函数,测试该算法通过运用C语言环境下的图像显示设置,本次实验我学会了多边形区域扫描线填充的有序边表算法,设计相关的数据结构(如链表结构、结点结构等),并将实现的算法应用于任意多边形的填充,为深一步的学习做好了铺垫。六、 参考文献1张家广 等编著.计算机图形学(第3版).北京:清华大学出版社,1998年9月.2陈传波,陆枫主编,计算机图形学基础,电子工业出版社,2002年3月。

    展开全文
  • PAGEPAGE 8实 验 报 告实验目的掌握有序边表算法填充多边形区域;理解多边形填充算法的意义;增强C语言编程能力。算法原理介绍根据多边形内部点的连续性知:一条扫描线与多边形的交点中,入点和出点之间所有点都是...
  • 《计算机图形学(多边形的扫描转换).ppt》由会员分享,可在线阅读,更多相关《计算机图形学(多边形的扫描转换).ppt(27页珍藏版)》请在装配图网上搜索。1、计算机图形学 第三章 基本光栅图形算法 本章内容 1 直线的...
  • 实验报告实验目的1、掌握有序边表算法填充多边形区域;2、理解多边形填充算法的意义;3、增强C语言编程能力。算法原理介绍根据多边形内部点的连续性知:一条扫描线与多边形的交点中,入点和出点之间所 有点都是多边形...
  • 二、扫描线算法(Scan-... 扫描线算法适合对矢量图形进行区域填充,只需要直到多边形区域的几何位置,不需要指定种子点,适合计算机自动进行图形处理的场合使用,比如电脑游戏和三维CAD软件的渲染等等。 对矢量多...
  •  对于一个给定的多边形,用一组水平(垂直)的扫描线进行扫描,对每一条扫描线均可求出与多边形边的交点,这些交点将扫描线分割成落在多边形内部的线段和落在多边形外部的线段;并且二者相间排列。于是,将落在多边形...
  • 活性边表(Active Edge Table, AET) 在上一节中,我们讲解了如何生成根据多边形生成ET 这一节我们讲解活性边和活性边表。 首先,什么是活性边? 活性边 与当前扫描线相交的边称为活性边(active edge),把它们按与扫描...
  • 如图对围出的多边形进行填充:                             &...
  •  对于一个给定的多边形,用一组水平(垂直)的扫描线进行扫描,对每一条扫描线均可求出与多边形边的交点,这些交点将扫描线分割成落在多边形内部的线段和落在多边形外部的线段;并且二者相间排列。于是,将落在多边形...
  • 边表构造的算法: (1) 首先构造一个纵向链表,链表的长度为多边形所占有的最大扫描线数,链表的每个结点,称为一个桶,则对应多边形覆盖的每一条扫描线。 (2) 将每条边的信息链入与该边最小y坐标相对的桶处。也...
  • 裁剪法实现多边形裁剪

    千次阅读 2019-07-22 16:18:57
    已经处理退化多边形裁剪算法 //编译环境:Visual C++ 6.0,EasyX_20190219(beta) #include<graphics.h> #include<conio.h> #include<iostream> #define max 30 using namespace std; //设置...
  • 来源:https://blog.csdn.net/u013044116/article/details/49737585二、扫描线算法(Scan-Line Filling) 扫描线算法适合对矢量图形进行区域填充,只需要直到多边形区域的几何... 对矢量多边形区域填充,算法核心...
  • 有序边表算法----计算机图形学

    千次阅读 2019-10-13 17:30:25
    有序边表算法的基本思想是:用水平扫描线从上到下(或从下到上)扫描由多条首尾相连的线段构成的多边形,每根扫描线与多边形的某些边产生一系列交点。将这些交点按照x坐标排序,将排序后的点两两成对,作为线段的两...
  • 活性边表算法

    2012-12-30 10:55:41
    计算机图形学中采用活性边表算法,实现多边形光栅化,本题目主要是在C语言和Win32控制台应用程序的基础上在屏幕上绘制多边形
  • 有效边表填充算法

    万次阅读 2018-06-18 16:31:47
    有效边表填充算法通过维护边表和有效边表,避开了扫描线与多边形所有边求交的复杂运算。填充原理是按照扫描线从小到大的移动顺序,计算当前扫描线与有效边的交点,然后把这些交点按x值递增的顺序进行排序、配对,以...
  • 一、基本扫描线填充算法基础知识 ...计算扫描线与多边形的交点。 ②排序。把所有交点按x值的递增顺序排序。x1、x2、x3、x4、x5、x6…… ③配对。[x1, x2],[ x3, x4] , [x5, x6]……每对交点代表扫描线
  • 二、扫描线算法(Scan-Line Filling) 扫描线算法适合对矢量图形进行区域填充,只需要直到多边形区域的几何位置,不需要指定种子点,适合计算机自动进行图形处理的场合使用,比如电脑游戏和三维CAD软件的渲染等等。...
  • 扫描线法填充多边形

    千次阅读 2015-10-20 19:30:52
    原理 如下图所示多边形: 简述 直线y=1,2,3……8顺序扫描多边形,以直线y=3为例,它与多边形有4个交点,将这4个交点的x坐标保存...可以观察到p1是多边形边的一个端点,是两条的交点,因此,可以选择将p1看
  • 实 验 报 告实验目的掌握有序边表算法填充多边形区域;理解多边形填充算法的意义;增强C语言编程能力。算法原理介绍根据多边形内部点的连续性知:一条扫描线与多边形的交点中,入点和出点之间所有点都是多边形的内部...
  • 活性边表法对多边形上色 如果不知道何为活性边表法的同学可以参阅: ... 我们对一个多边形进行从上至下的...将即将扫描到的边加入新边表新边表进行排序 每条扫描线不断向下逐行像素求交点(线段的交点的横坐标可以用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,249
精华内容 2,899
关键字:

多边形的新边表