计算机图形学 第4章 多边形填充

这篇具有很好参考价值的文章主要介绍了计算机图形学 第4章 多边形填充。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前驱知识

  • 了解扫描转换的基本概念。
  • 熟练掌握多边形有效边表填充算法。
  • 掌握多边形边缘填充算法。
  • 熟练掌握区域四邻接点和八邻接点区域填充算法。
  • 掌握区域扫描线种子填充算法。

无论使用哪种着色模式,都意味着要使用指定颜色为多边形边界内的每一个像素着色。

多边形填充算法,win32,算法

多边形填充算法,win32,算法

多边形的表示 有两种:⑴顶点表示法;⑵点阵表示法

多边形的扫描转换

定义:将多边形的描述从顶点表示法变换到点阵表示法的过程,称为多边形的扫描转换。

即从多边形的顶点信息出发,求出位于多边形内部的各个像素点信息,并将其颜色值写入帧缓冲的相应单元中。

多边形填充算法,win32,算法
多边形可以使用平面着色模式(flat shading mode)或光滑着色模式(smooth shading mode)填充。



ET表(边表):用来存放多边形除水平边外的所有边的信息。
AET表(有效边表):与当前扫描线相交的多边形的边。

多边形填充的主要算法是扫描线算法
先确定多边形覆盖的扫描线条数,对每一条扫描线,计算扫描线与多边形边界的交点区间,如果能判断该区间在多边形内部,则将其内的像素绘制为指定的颜色。

扫描线算法在处理每条扫描线时,需要与多边形的所有边求交,处理效率很低。改进的算法是有效边表算法

对一条扫描线的填充一般分为以下4个步骤

  • 求交:计算扫描线与多边形各边的交点;
  • 排序:把扫描线上所有交点按递增顺序进行排序;
  • 配对:将第一个交点与第二个交点,第三个交点与第四个交点等等进行配对,每对交点代表扫描线与多边形的一个相交区间。
  • 着色:把区间内的像素置为填充色。

种子填充算法是从区域内的一个种子位置开始,由内向外用填充颜色绘制种子及其相邻像素直到颜色不同的边界像素为止。
种子填充算法主要分为4邻接点算法和8邻接点算法。


有效边表填充算法

原理

填充原理是按照扫描线从小到大的移动顺序,计算当前扫描线与有效边的交点,然后把这些交点按x值递增的顺序进行排序、配对,以确定填充区间,最后用指定颜色填充区间内的所有像素,即完成填充工作。

有效边表填充算法已成为目前最为有效的多边形填充算法之一。

边界像素处理原则

填充左下角为(1,1),右上角为(3,3)的正方形时,若将边界上的所有像素全部填充,就得到图示的结果。
在多边形填充过程中,常采用“左闭右开”和“下闭上开”的原则对边界像素进行处理。
多边形填充算法,win32,算法
多边形填充算法,win32,算法
多边形填充算法,win32,算法

怎么算交点

这里 相对于 扫描线 的位置都是上下关系,不是左右关系。
多边形填充算法,win32,算法

有效边

多边形填充算法,win32,算法
多边形填充算法,win32,算法
为了确定在哪条扫描线上插入了新边,就需要构造一个边表(edge table,ET),用以存放扫描线上多边形各条边出现的信息

因为水平边的1/k为∞,并且水平边本身就是扫描线,在建立边表时可以不予考虑。

桶表与边表

为了确定在哪条扫描线上插入了新边,就需要构造一个边表(edge table,ET),用以存放扫描线上多边形各条边出现的信息。因为水平边的1/k为∞,并且水平边本身就是扫描线,在建立边表时可以不予考虑。

桶表表示法

桶表是按照扫描线顺序管理边出现情况的一个数据结构。

  • 构造一个纵向扫描线链表,链表的长度为多边形所占有的最大扫描线数,链表的每个结点称为桶(bucket),对应多边形覆盖的每一条扫描线。
  • 多边形填充算法,win32,算法

桶类的代码

class CBucket  
{
public:
		CBucket();
		virtual ~CBucket();
public:
		int      ScanLine;   //扫描线
		CAET     *p;      //桶上的边表指针
		CBucket  *next;
};

  • 多边形填充算法,win32,算法

多边形填充算法,win32,算法
其实,书上所谓的新边,是指从第一条扫描线(都是从上到下)开始,依次记入与之相交的边按x/y(min)放入链表,重复的边(之前的扫描线已经放入自己的链表的边)不放入。最后所有链表中元素的个数应该等于多边形边的条数。所以这儿的新边并不是我们额外再添几条边,而是从零开始建立多边形。另外在这儿我们不能仅仅局限于书上面说的那个y=1到y=12的多边形,很多多边形并不是都是整数顶点并且这么有规律的摆放在像素坐标系上的。要深入学会桶表与边表,首先要知道我们在扫描转换的时候的坐标系,实际上是像素点构成的坐标系,每个单位点都对应一个像素点,而扫描线就是从以此构成的坐标系中每条y=Z(Z为任意整数)直线。我们要讨论的,就是把多边形以合适的方式放入坐标系后,从与这个多边形相交的第一条扫描线(从下到上,顶点相交的也算)开始写边表。

有了以上的认识后我们开始来正式的认识桶表与边表。要注意桶表与边表是一个整体的表,类似于有效边表,而非两个表。假如多边形所对应的扫描线是y=1到y=10,那么从y=1的有效边开始,把所有y=1的有效边放入y=1对应的链表,然后放y=2一直到y=10,中途如果有扫描线的有效边之前的扫描线已经放入则不能再放。知道放入所有边或者扫描线到最后一条则结束。我们手写的时候,首先画一个表以此写出多边形覆盖的扫描线,然后y=1开始用箭头引出之前没有出现过的有效边的链表即可。

最后桶表于边表中链表的内容,记住即可。有4个部分,第一部分按书上的理解很容易出错。第一部分中x|y(min)指的不是x除以y,也不是x整除y,这儿书上没说清楚,这儿的**x|y(min)指的就是在对应的有效边中与之相交的最低扫描线与这条边相交的点的x值。**第二部分是ymax,就是对应有效边与之相交的最高的扫描线。第三部分k/1是指对应有效边的斜率的倒数。第四部分是next指针,上一个链表连接下一个链表,最后一个单元指针为空。在找到所有不重复的有效边后,按照x|ymin从小到大的顺序构建(x|ymin相等则按照1/k从小到大的顺序构建)链表即可。如果一条扫描线没有任何不重复的有效边,不写就行了。理解了以上内容,便可以写桶表与边表了。是不是和数据结构构建多边形的算法类似?因为本质上都是树相关的算法,只不过图形学这方面很多没有说清楚。
————————————————
版权声明:本文为CSDN博主「SN川川」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/weixin_44724323/article/details/124647806



边缘填充算法

远离/定义:
边缘填充算法是先求出多边形的每条边与扫描线的交点,然后将交点右侧的所有像素颜色全部取为补色(或反色)。按任意顺序处理完多边形的所有边后,就完成了多边形的填充任务。

边缘填充算法利用了图像处理中的求“补”或求“反”的概念,对于黑白图像,求补就是把RGB(1,1,1)(白色)的像素置为RGB(0,0,0)(黑色),反之亦然;对于彩色图像,求补就是将背景色置为填充色,反之亦然。求补的一条基本性质是一个像素求补两次就恢复为原色。如果多边形内部的像素被求补偶数次,保持原色,如果被求补奇数次,显示填充色。

填充过程

多边形填充算法,win32,算法
过程:
(下图顺序)从左到右从上到下多边形填充算法,win32,算法
代码:

void CTestView::FillPolygon(CDC *pDC) 
{
      COLORREF BClr=RGB(255,255,255);//背景色
      COLORREF FClr=GetClr;//填充色
      int yMin,yMax;//边的最小y值与最大y值
      double x,y,k;//x,y当前点,k斜率的倒数
      for(int i=0;i<7;i++)//循环多边形所有边
     {
	int j=(i+1)%7;
	k=(P[i].x-P[j].x)/(P[i].y-P[j].y);//计算1/k
	if(P[i].y<P[j].y)//得到每条边y的最大值与最小值
	{
		yMin=Round(P[i].y);
		yMax=Round(P[j].y);
		x=P[i].x;//得到x|ymin
	}
	else
	{
		yMin=Round(P[j].y);
		yMax=Round(P[i].y);
		x=P[j].x;
	}
		
	for(y=yMin;y<yMax;y++)//沿每一条边循环扫描线
	{
	//对每一条扫描线与边的交点的右侧像素循环   
                     for(int m=Round(x);m<MaxX;m++)
                     //MaxX为包围盒的右边界
	         {
		if(FClr==pDC->GetPixel(m,Round(y)))			                      pDC->SetPixelV(m,Round(y),BClr);
		else
		          pDC->SetPixelV(m,Round(y),FClr);	
		}
		x+=k; 
	}
     }
}


多边形填充算法,win32,算法


区域填充算法/种子填充算法

原理
种子填充算法是从区域内任一个种子像素位置开始,由内向外将填充色扩散到整个多边形区域的填充过程。

优点是能对具有任意复杂闭合边界的区域进行填充。
多边形填充算法,win32,算法
多边形填充算法,win32,算法

多边形填充算法,win32,算法

种子填充算法

定义;

  • 从种子像素点开始,使用四邻接点方式搜索下一像素点的填充算法称为四邻接点填充算法。
  • 从种子像素点开始,使用八邻接点方式搜索下一像素点的填充算法称为八邻接点填充算法。

八邻接点填充算法的设计和四邻接点填充算法基本相似,只要把搜索方式由四邻接点修改为八邻接点即可。

种子填充算法一般要求区域边界色和填充色不同,输入参数只有种子坐标位置填充颜色

原理
多边形填充算法,win32,算法
代码:

void CTestView::FillPolygon(CDC *pDC)//填充多边形
{
	COLORREF BoundaryClr=RGB(0,0,0);//边界色
	COLORREF PixelClr;//当前像素的颜色
	pHead=new CStackNode;//建立栈头结点
	pHead->next=NULL;//栈的头结点总是为空
	Push(Seed); //种子像素入栈
	while(NULL!=pHead->next)//如果栈不为空
	{
		CP2 PopPoint;
		Pop(PopPoint); //种子像素出栈
		pDC->SetPixelV(Round(PopPoint.x),
                                           Round(PopPoint.y),SeedClr);
		PointLeft.x=PopPoint.x-1;//左方像素
		PointLeft.y=PopPoint.y;
		PixelClr=pDC->GetPixel(Round(PointLeft.x),
                                          Round(PointLeft.y));
		if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)
			Push(PointLeft);//左方像素入栈
		
PointTop.x=PopPoint.x;
		PointTop.y=PopPoint.y+1;//上方像素
		PixelClr=pDC->GetPixel(Round(PointTop.x),
                                               Round(PointTop.y));
		if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)
			Push(PointTop);	//上方像素入栈
		PointRight.x=PopPoint.x+1;//右方像素
		PointRight.y=PopPoint.y;
		PixelClr=pDC->GetPixel(Round(PointRight.x),
                                                 Round(PointRight.y));
		if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)
			Push(PointRight);//右方像素入栈	
		PointBottom.x=PopPoint.x;
		PointBottom.y=PopPoint.y-1;//下方像素
		PixelClr=pDC->GetPixel(Round(PointBottom.x),
                                               Round(PointBottom.y));
		if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)
			Push(PointBottom);//下方像素入栈
		}
		pDC->TextOut(rect.left+50,rect.bottom-20,"填充完毕");
		delete pHead;
		pHead = NULL;
}

扫描线种子填充算法 (更有效)

多边形填充算法,win32,算法文章来源地址https://www.toymoban.com/news/detail-785506.html

到了这里,关于计算机图形学 第4章 多边形填充的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [C++] opencv - fillPoly(填充多边形)函数介绍和使用场景

    fillPoly() 函数是OpenCV中用于绘制填充多边形的函数。函数原型如下: fillPoly() 函数适用于需要绘制填充多边形的场景,例如在图像上绘制一个封闭的图形、制作一个简单的遮罩等。   fillPoly() 函数是OpenCV中用于绘制填充多边形的函数。可以用来绘制实心三角形,实心矩形,实

    2024年02月19日
    浏览(131)
  • Opencv(C++)笔记--绘制直线、矩形、椭圆、圆、填充多边形、绘制字体和随机产生坐标点

    目录 1--cv::line()绘制直线 2--cv::Rect()绘制矩形 3--cv::ellipse()绘制椭圆 4--cv::circle()绘制圆 5--cv::fillPoly()填充多边形 6--cv::putText()绘制字体 6--cv::RNG随机产生坐标点 使用 cv::Point p1 定义坐标点; 使用 cv::line() 绘制直线,传入的参数依次为:背景图、两个点的坐标、直线的颜色、直线

    2024年02月14日
    浏览(60)
  • OpenCV-Python学习(13)—— OpenCV 多边形填充与绘制(cv.fillPoly、cv.polylines)

    1. 知识点 学习 cv.polylines 函数的使用; 学习 cv.fillPoly 函数的使用。 2. 绘制折线或多边形 cv.polylines 函数说明 2.1 函数使用 2.2 参数说明 参数 说明 img 表示要在其上绘制矩形的图像的img对象。 pts 表示一个或多个点集。 isClosed 表示标志,决定所绘制的多边形是否闭合。若为 T

    2024年02月16日
    浏览(58)
  • css 属性 clip-path:polygon实现任意图形、多边形

    最近画看板,要求点击客户自定义的不规则图形内的任意地方都可以展示相应的提示, 刚开始让UI 提供切好的不规则背景图,切换位置替换不同的图形,判断是哪个图展示对应的提示 后来查到css这个属性,太好用了 clip-path CSS 属性使用裁剪方式创建元素的可显示区域,类似

    2024年02月12日
    浏览(53)
  • 计算两个多边形的交集

    已知两个多边形Polygon1和Polygon2,分别由点集C1={P1,P2,...,Pm}和C2={Q1,Q2,...,Qn}表示,求这两个多边形的交集。 两个多边形相交后,其顶点要么是两个多边形边的交点,要么是在多边形内部的点。 计算两个多边形每条边之间的交点。 计算包含在多边形内部的点。 将交点和多边形内

    2024年02月12日
    浏览(70)
  • 计算两个多边形的最近距离(MATLAB)

            本文意在介绍关于计算两组坐标点的最近距离的简单方法,可用此方法来计算两个多边形的最近距离以及距离最近的两个点。下面展示具体实例。 函数代码         该函数可以比较快速的计算两组坐标点之间的最小距离,并返回相应的坐标。缺点是只能计算整数

    2024年02月08日
    浏览(44)
  • 【计算几何】判断多边形边界顺逆时针 & C++代码实现

    多边形可以由一个点集 { v 1 , v 2 , . . . , v n } {v_1,v_2,...,v_n} { v 1 ​ , v 2 ​ , ... , v n ​ } 表示,构成多边形的点集确定,多边形边界的顺序也就确定了 有关多边形边界的顺序的示意图,如下图所示: 有时候关于数据格式有规定,要求多边形边界必须为顺时针或者逆时针。 因

    2024年02月07日
    浏览(60)
  • Elasticsearch计算距离,根据距离排序,地理点和地理多边形范围查找

    Elasticsearch 计算并返回距离一共有两种方法: sort 和 script_fields CentOS 7.6 Elasticsearch 7.10 响应结果如下, hits 下的 sort 字段就是距离,单位:km。 5.x 以前支持:distanceInKm(lat, lon) 函数,后来被废弃。现在只支持 arcDistance(lat, lon) 函数:计算两点距离,单位为:m。响应结果如下,

    2024年02月09日
    浏览(45)
  • 再说不会用python计算地球表面多边形面积,可不能了!(记录五种可行方法)

    由于地理投影导致导致每个像元实际地面面积不同,越靠近北极实际面积越小,越靠近赤道实际面积越大, 如果不进行面积加权就简单平均,会导致温度较实际温度偏低。 直接使用卫星地图的计算面积功能就会遇到这样的问题,多数卫星地图的计算面积功能是将地图假设为

    2024年02月01日
    浏览(44)
  • 计算机图形学06:中点Bresenham画圆(并填充边界,例如:边界用红色,内部用绿色填充)

    作者 :非妃是公主 专栏 :《计算机图形学》 博客地址 :https://blog.csdn.net/myf_666 个性签:顺境不惰,逆境不馁,以心制境,万事可成。——曾国藩 专栏名称 专栏地址 软件工程 专栏——软件工程 计算机图形学 专栏——计算机图形学 操作系统 专栏——操作系统 软件测试 专

    2024年01月24日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包