接着上篇博文《多边形的扫描转换》
多边形
边相关扫描线填充算法需要建立两张表:新边表(New Edge Table,NET)和活动边表(Active Edge Table,AET)
新边表 NET
记录多边形除水平边外的所有的边,记录在没条扫描线的表中,记录的格式为:
x 当前扫描线与边的交点坐标;dx从当前扫描线到下一条扫描线间x的增量((x2-x1)/(y2-y1));ymax 该边所交的最高扫描线
上图的多边形,建立的新边表如下:
活动边表 AET
记录只与当前扫描线相交的边的链表。
NET表建立以后,就知道了多边形所有的边,所以就能开始扫描转换。不同的扫描线相交的边线也不同,当对某一条扫描线进行扫描转换时,我们只需要考虑与它相交的那些边线,也就是活动边表中的边。
记录的格式还是用 x | dx | ymax 。只是这里x表示扫描线与边的交点的坐标。
以第6条扫描线为例:
第6条扫描线的活动边表如下:
合并NET得到AET
实际计算时不是去算没条扫面线与多边形边的交点得到活动边表AET(否则也看不到算法意义了),而是用NET补充得到AET。
注意到表示格式第三个量为 ymax,表示该边所交的最高扫描线,那么小于 ymax的扫描线都应该与这条边相交。
所以看NET那个表中第二条扫描线与P1P6相交,ymax为7,那么第3,4,5,6条扫描线应该都与P1P6相交。关键是求交点横坐标
x 的值。第二个量dx 表示从当前扫描线到下一条扫描线间x的增量,所以下一条扫描线交点x'=x+dx。所以第3,4,5,6条扫描线与P1P6交点横坐标都是2。
由此补全NET表:
边的扫描转换算法
两个表建立完后,开始扫描转换。整体算法步骤描述如下:
1、根据给出的多边形顶点坐标,建立NET表;
求出顶点坐标中最大y值ymax和最小y值ymin。
2、初始化AET表指针,使它为空。
3、执行下列步骤直至NET和AET都为空.
3.1、如NET中的第y类非空,则将其中的所有边取出并插入AET中;
3.2、如果有新边插入AET,则对AET中各边排序;
3.3、对AET中的边两两配对,(1和2为一对,3和4为一对,…),
将每对边中x坐标按规则取整,获得有效的填充区段,再填充.
3.4、将当前扫描线纵坐标y值递值1;
3.5、如果AET表中某记录的ymax=yj,则删除该记录 (因为每条边被看作下闭上开的);
3.6、对AET中剩下的每一条边的x递增dx,即x' = x+ dx .
参考资料:计算机绘图(重庆大学软件学院杨梦宁 徐玲)
分享到:
相关推荐
OpenCV实现的区域填充扫描线算法,通过建立活性边表的手段实现光栅图形的扫描填充
用OpenCV实现Photoshop曲线算法C++源码 。
说明: ... 在Matlab下,使用imfill可以很容易的完成孔洞填充操作,感觉这是一个极为常用的...之前了解过冈萨雷斯那本书上的孔洞填充算法,所以想着手重新写一个。这里借鉴了冈萨雷斯书上的集合运算方法(并不完全一样)
C++ Opencv imfill 孔洞填充函数
用OpenCV C++实现Photoshop色阶调整算法, 包含Levels类和demo例程
图像去雾算法opencv实现图像去雾算法opencv实现 暗原色的opencv实现
采用VC++语言编程实现多边形扫描转换的扫描线填充算法,可以画任意多边形。 多边形为任意多边形,如:凸多边形、凹多边形、含内环多边形。 上传的资源中没有采用通过鼠标画来实现多边形顶点的输入,而是在代码...
OpenCV算法精解-代码
OpenCV是一个基于BSD许可(开源)发行的跨平台计算机视觉库,可以运行在Linux、Windows、Android和Mac OS操作系统上。它轻量级而且高效——由一系列 C 函数和少量 C++ 类构成,同时提供了Python、Ruby、MATLAB等语言...
普通的OpenCV C++细化算法. 已封装成C++函数,可直接调用使用。也可用于参考, 根据需要也可自行修改源码。
OpenCV算法精解代码 OpenCV算法精解代码 OpenCV算法精解代码
Opencv实现的运动目标检测算法.zip资源matlab opencv运动目标检测程序资料Opencv实现的运动目标检测算法.zip资源matlab opencv运动目标检测程序资料Opencv实现的运动目标检测算法.zip资源matlab opencv运动目标检测...
利用opencv相关函数,及相关细化算法实现对目标ROI进行细化,骨架提取
opencv 填充 连通域 参数是二值化图像和填充的面积
c++ 实现 ,基于opencv的 视觉跟踪 代码,使用前请按照网上教程正确配置opencv3。
C++OpenCV3编程源代码漫水填充算法综合示例提取方式是百度网盘分享地址
计算机视觉,OpenCV算法精讲
采用C++基于OpenCV库的yuv和codebook算法。通过控制窗对两种算法的结果进行处理比对。
visual studio,链接opencv以c++为工具实现分水岭算法,
opencv三维扫描 相机加投影,三维扫描仪,相机标定,输出三维点云图