Tag: 扫描多边形预览模式: 普通 | 列表

扫描多边形填充算法

多边形填充,就是把多边形所占据的栅格象素赋予指定的颜色值。要完成这个任务,一个首要的问题就是求出多边形所占据的栅格象素,判断一个网格在多边形内还是多边形外,在多边形内的象素,则赋予指定的颜色值,多边形外的象素,则不赋予指定的颜色值,具体该如何判断象素是否在多边形内呢?这里我们采用扫描线多边形填充算法

扫描多边形填充算法的基本原理——在直角坐标系中,假设有一条从左至右的扫描线穿过多边形,从左至右开始计数,与多边形交点为奇数时,开始进入多边形,与多边形交点为偶数时,走出多边形。这样在这相邻配对的奇偶交点间的所有象素都在多边形内。如图,奇数交点ac,都是进入多边形,偶数交点bd都是走出多边形,相邻的奇偶交点配对,ab之间,cd之间的象素都在多边形内,可见一条扫描线上,与多边形交点个数需要为偶数。依据这样的思路,扫描线从上到下,从左到右依次扫过多边形即可求得多边形所占据的象素。(注意退化情况的处理,也就是扫描线刚好经过顶点或者多边形的边本身就是水平的情况)

        
                                            
 
 

具体实现——首先,求多边形最上,最下的行号,以便于确定扫描线的行数,这个可以根据多边形的MBR求得;其次,确定一条扫描线上,与多边形的交点,保证交点个数为偶数,并对这些交点按列号从小到大排列;最后,扫描转换,扫描线从上到下,每条扫描线从左到右,对这些排序好的奇偶点配对连线。所采用的数据结构类似于“锯齿状的二维数组”,第一维代表行号,第二维代表一行中的交点。为了实现以上的步骤,需要对多边形边界进行栅格化,确定边界所经过的栅格,并把这些存储为“锯齿状的二维数组”(栅格化方法有:数值微分法,Bresenham算法,栅格中心线求交法)。退化情况的处理:

一、边线端点的处理。比较此端点与它相邻的前后两端点所在扫描线的行号,设此端点的行号为h0,前一端点的行号为h1,后一端点的行号为h2

1)        h0>h1 and h0>h2,如图,点ACF,这些端点的栅格点不予以记录,即扫描线经过该点,计交点为0

2)        h0<h1 and h0<h2,如图,点BEG,这些端点的栅格点记录两次,即扫描线经过该点,计交点为2

3)        h0<h1 and h0>h2 or h0>h1 and h0<h2,如图,点DH,这些端点的栅格点记录一次,即扫描线经过该点,计交点为1

   
                                       

二、水平线的处理。多边形边线段,扫描出来为一横线,即一条线段从头到尾都占据一行栅格。理论上,这种情况与扫描线有无数个交点,为了保持一行中交点个数为偶数,判断当前横线段与前后相邻两条线段的位置关系,同时先栅格化此横线,作以下规定。

1)        前后相邻两线段位于此横线段的异侧,如图,横线段AB,前后两线段AIBC位于横线段AB的异侧,则与此横线段交点计为1,记录A点或者B点,均可。

2)        前后相邻两线段位于此横线段的同侧,如图,横线段GF,前后两线段GHFE位于横线段GF的同侧,则与此横线段交点计为0,不记录任何交点。

                                    

这种判断的思想是这样的:基于动态的思想,横线AB,假设AB两点相互靠近,最终成为一点,假设为A‘,根据端点处理的方法,A’介于前后两点IC之间,应计交点一个,而对于横线GF,一样的道理,GF相互靠近最终成为一点,假设为F‘,根据端点处理的方法,F’大于前后两点EH,应计交点0。这种判断可以有效处理横线,但又带来一个新的问题,如果相邻前或者后两线段也是同此横线一样,也是在这一行水平,这样就要递推到更前或者更后的线段,直到找出以上判断的条件。

                                      

如图,判断线段AB,需要找到前一条线段AJ,后一条线段BC,由于BCAB都是水平的,需要找再下一条CD,得到AJCD位于水平线的异侧,则计交点为1。判断线段GH,前后两线段GFHI都是水平的,需要分别寻找更前,、更后的线段FEIJ,一直递归下去,直到确定判断条件。如果觉得这种情况比较麻烦,在程序端点循环的时候,找到第一段不是横线的起点开始循环,这样,只要判断,横线后面条线段的情况,直到确定判断条件即可。

     三、岛屿情况。以上退化情况的处理同样适合岛屿情况的处理,依然要对栅格按列从左往右排序,奇偶配对画线即可。

Tags: 扫描多边形 填充算法

分类:影音图形 | 固定链接 | 评论: 0 | 引用: 0 | 查看次数: 5737