第5讲 多边形区域填充算法

《第5讲 多边形区域填充算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第5讲多边形区域填充算法中南大学地学院GIS中心区域的表示方法区域的表示方法顶点表示（几何表示）用区域的顶点序列来表示区域，经过数学计算可知区域是由什么样的相连直线或曲线构成其轮廓线的点阵表示（像素表示）用位于多边形内的像素集合来刻画多边形2区域填充的概念区域填充即给出一个区域的定义，要求对此区域范围内的所有像素赋予指定的颜色代码确定哪些像素位于填充区域的内部用指定颜色绘制这些像素扫描转换多边形将多边形顶点表示形式转换成点阵表示形式3逐点判断法基本原理判断绘图窗口内的像素是否位于多边形内，若是，则用指定颜色绘制该像素问题如

2、何判断点在多边形的内外关系？射线法累计角度法编码法(xmin,ymin)(xmax,ymax)P1P24算法假设判断点是否在多边形内的函数为IsInside（）#defineMAX100typedefstruct{//多边形顶点个数intPolygonNum;//多边形顶点数组Pointvertexces[MAX]}Polygon;//多边形结构voidFillPolygon(Polygon*P,intpolygonColor){intx,y;for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xma

3、x;x++)if(IsInside(P,x,y))SetPixel(x,y,polygonColor);elseSetPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP()*/5射线法若交点数=偶数（包括0），则点在多边形之外BDEPABCDEPAC若交点数=奇数，则点在多边形之内6依顺序取出每一条射线，求其与多边形边界的交点，并对每一对交点中的像素进行填充射线abcd7射线法的缺陷填充扩大化问题若将多边形边界看成是多边形内部，并对它们填充，则该多边形会被放大解决方法采取“

4、左闭右开，下闭上开”的方法，即将左、下边界像素视为多边形内部，需填充，而右、上边界则为多边形外部，不予填充1231238取整问题射线与多边形边界交点坐标值不为整数解决方法当射线与多边形边界交点坐标为小数值时，如果多边形在此边界右侧，则将该小数值进1作为边界点，否则舍去小数部分并进行填充，这样可使多边形不扩大9奇点取舍问题当射线与多边形顶点相交时，称该交点为奇点。如果奇点的计数不正确，会导致填充错误射线4与多边形相交时，有一个奇点。如果奇点计数为奇数个，则总共得到3个交点，此时多边形会将区域外部填充，而区域内部不予填充，出现

5、错误。若将奇点计数为偶数个，问题可解决射线2与多边形相交时，有一个奇点。如果奇点计数依照上述计为偶数个，则总共得到3个交点，仍然会造成错误填充。如果将奇点计数为奇数个，问题可解决C射线4射线1射线2射线3BAabcd10解决方法当奇点在多边形两边之下时，该点计2次，如A、D、H点当奇点在多边形两边之上时，该点计0次，如B、F、I点当奇点在多边形两边中间时，该点计1次，如C、E、G点具体实现方法检查顶点的两条边的另外两个端点的y值，由这两个y值中大于交点y值的个数是0、1、2来决定FBCGEAIDH11水平边问题射线与多边形

6、的水平边相交时，交点理论上是无穷多个解决方法对于多边形的水平边，不计它与射线的交点12逐点判断法的特点特点程序简单测试点是否在多边形内的算法速度太慢，效率低改进逐点判断法孤立考虑各个像素与多边形的内外关系利用内部点的连续性13扫描线多边形填充算法目标利用相邻像素之间的连贯性，提高算法效率处理对象：简单多边形非自交多边形（边与边之间除了顶点外无其它交点）扫描线(ScanningLine)平行于坐标轴的直线一般取平行于X轴区间：扫描线与边的交点间的线段14连贯性(Coherence)边的连贯性(EdgeCoherence)某条

7、边与当前扫描线相交，也可能与下一条扫描线相交扫描线的连贯性(Scan-lineCoherence)当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序可能相同或类似区间的连贯性(SpanCoherence)同一区间上的像素取同一颜色属性15基本原理将整个绘图窗口内扫描多边形的问题分解到一条条扫描线，只要完成每条扫描线的绘制就实现了多边形的扫描转换一条扫描线与多边形的边有偶数个交点，每2个点形成一区间多边形的填充过程可以分为四个步骤：求交：计算扫描线与多边形各边的交点排序：把所有交点按x值递增顺序排序配对：第一个与第二个

8、，第三个与第四个等，每对交点代表扫描线与多边形的一个相交区间填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色16计算交点分类第一类交点：位于同一条边上的后继交点--(P2,P4)第二类交点：新出现的边与扫描线的交点--(P3)计算：由扫描线y＝e与多边形的交点递推计算扫描线y＝e＋1