计算机视觉
图像处理

【图像处理】边相关扫描线填充算法

文章目录

接着上篇博文《 多边形的扫描转换

多边形

边相关扫描线填充算法需要建立两张表:新边表(New Edge Table,NET)和 活动边表(Active Edge Table,AET)

新边表 NET

记录多边形除水平边外的所有的边,记录在没条扫描线的表中,记录的格式为:
x 当前扫描线与边的交点坐标;dx从当前扫描线到下一条扫描线间x的增量((x2-x1)/(y2-y1));ymax 该边所交的最高扫描线
上图的多边形,建立的新边表如下:

活动边表 AET

记录只与当前扫描线相交的边的链表。
NET表建立以后,就知道了多边形所有的边,所以就能开始扫描转换。不同的扫描线相交的边线也不同,当对某一条扫描线进行扫描转换时,我们只需要考虑与它相交的那些边线,也就是活动边表中的边。
记录的格式还是用 x | dx | ymax 。只是这里 表示扫描线与边的交点的坐标。
以第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. 1、根据给出的多边形顶点坐标,建立NET表;
  2.       求出顶点坐标中最大y值ymax和最小y值ymin。
  3. 2、初始化AET表指针,使它为空。
  4. 3、执行下列步骤直至NET和AET都为空.
  5.     3.1、如NET中的第y类非空,则将其中的所有边取出并插入AET中;
  6.     3.2、如果有新边插入AET,则对AET中各边排序;
  7.     3.3、对AET中的边两两配对,(1和2为一对,3和4为一对,…),
  8.     将每对边中x坐标按规则取整,获得有效的填充区段,再填充.
  9.     3.4、将当前扫描线纵坐标y值递值1;
  10.     3.5、如果AET表中某记录的ymax=yj,则删除该记录 (因为每条边被看作下闭上开的);
  11.     3.6、对AET中剩下的每一条边的x递增dx,即x’ = x+ dx .
参考资料:计算机绘图(重庆大学软件学院 杨梦宁 徐玲)
PPT讲解下载:http://pan.baidu.com/s/1eRSrKjg

转载注明来源:CV视觉网 » 【图像处理】边相关扫描线填充算法

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 5

评论前必须登录!