计算机图形学第3讲多边形区域填充算法

中南大学地球科学与信息物理学院GIS中心多边形的扫描转换与区域填充区域的表示方法区域的表示方法顶点表示（几何表示）用区域的顶点序列来表示区域，经过数学计算可知区域是由什么样的相连直线或曲线构成其轮廓线的点阵表示（像素表示）用位于多边形内的像素集合来刻画多边形2区域填充的概念扫描转换（scanconversion）多边形将多边形顶点表示形式转换成点阵表示形式区域填充（regionfill）要求对此区域范围内的所有像素赋予指定的颜色代码确定哪些像素位于填充区域的内部用指定颜色绘制这些像素3逐点判断法（暴力）基本原理判断绘图窗口内的像素是否位于多边形内，若是，则用指定颜色绘制该像素问题如何判断点在多边形的内外关系？射线法累计角度法4(xmin,ymin)(xmax,ymax)P1P2射线法若交点数=偶数（包括0），则点在多边形之外5BDEPABCDEPAC若交点数=奇数，则点在多边形之内扫描线算法特点程序简单测试点是否在多边形内的算法速度太慢，效率低改进逐点判断法孤立考虑各个像素与多边形的内外关系利用内部点的连贯性（Coherence）6扫描转换与区域填充暴力算法不能很好地利用空间连贯性空间连贯性性（Spatialcoherence）若当前像素在多边形内部时，与其空间临近的像素亦很有可能在多边形内部扫描转换区域填充7扫描转换与区域填充扫描转换算法区域填充算法8扫描转换算法算法目标利用相邻像素之间的连贯性，提高算法效率处理对象：简单多边形非自交多边形（边与边之间除了顶点外无其它交点）扫描线(ScanningLine)平行于坐标轴的直线一般取平行于X轴区间：扫描线与边的交点间的线段9多边形10X11需要找出扫描线上与多边形相交的像素，填充之约定：至底向上扫描(x1,y1)(x3,y3)(x2,y2)扫描线算法依顺序取出每一条射线，求其与多边形边界的交点，并对每一对交点中的像素进行填充12射线abcd扫描线算法扫描线算法求交计算扫描线与多边形各边的交点排序把所有交点按x值递增顺序排序配对第1个与第2个，第3个与第4个等，每对交点代表一个相交区间填色把相交区间内：多边形颜色相交区间外：背景色13C射线1BADEF2341abdc奇点取舍问题当射线与多边形顶点相交时，称该交点为奇点。如果奇点的计数不正确，会导致填充错误14•射线4与多边形相交时，有一个奇点。如果奇点计数为奇数个，则总共得到3个交点，此时多边形会将区域外部填充，而区域内部不予填充，出现错误。•射线2与多边形相交时，有一个奇点。如果奇点计数依照上述计为偶数个，则总共得到3个交点，仍然会造成错误填充。C射线4射线1射线2射线3BAabcd2两个交点1两个交点扫描线算法解决方法当奇点在多边形两边之下时，该点计2次，如A、D、H点当奇点在多边形两边之上时，该点计0次，如B、F、I点当奇点在多边形两边中间时，该点计1次，如C、E、G点15FBCGEAIDH扫描线算法取整问题扫描线与多边形边界交点坐标值不为整数解决方法当扫描线与多边形边界交点坐标为小数值时，如果多边形在此边界右侧，则将该小数值进1作为边界点，否则舍去小数部分并进行填充，这样可使多边形不扩大16扫描线算法水平边问题扫描线与多边形的水平边相交时，交点理论上是无穷多个解决方法对于多边形的水平边，不计它与射线的交点17扫描线算法扫描线算法填充扩大化问题若将多边形边界看成是多边形内部，并对它们填充，则该多边形会被放大解决方法采取“左闭右开，下闭上开”的方法，即将左、下边界像素视为多边形内部，需填充，而右、上边界则为多边形外部，不予填充18123123扫描线算法简单（naive）扫描线算法每条扫描线都要求交点解决：空间连贯性（spatialcoherence）19扫描线算法（改进）连贯性(Coherence)边的连贯性(EdgeCoherence)某条边与当前扫描线相交，也可能与下一条扫描线相交扫描线的连贯性(Scan-lineCoherence)当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序可能相同或类似区间的连贯性(SpanCoherence)同一区间上的像素取同一颜色属性20√√扫描线算法（改进）计算交点分类第一类交点：位于同一条边上的后继交点--(P2,P4)第二类交点：新出现的边与扫描线的交点--(P3)计算：y＝e＋1的交点第一类交点：边的连贯性！x’＝x＋1/k第二类交点：线段的下端点即为交点21P3P4P0P2P1增量算法扫描线算法(改进)排序扫描线连贯性采用插入排序复杂度为O(n)22扫描线算法(改进)数据结构——加速结构求交问题空间换时间边表（Edgetable,ET）动记录与当前扫描态表（活性边表，ActiveEdgetable，AET）链表形式23扫描线算法(改进)ET定义每条扫描线，对应一个链表链表中每个结点的结构x1/kymaxnext24typedefstruct{intymax;floatx;floatdeltax;Edge*nextEdge;}Edge;•x：交点x坐标•Deltax（1/k）：边的斜率的倒数•ymax：边的上端点的y坐标值（何时不再相交）•nextEdge：下一条边的指针扫描线算法(改进)下一条扫描线的边表（边的连续性）活性边表（AET）更新交点的计算——增量算法：当扫描线y=ymax，说明该扫描线与此边不相交（上开下闭），将该边从AET中删除Deltax不变问题初始交点如何计算新边如何得到25kxxii/11扫描线算法(改进)新边表（NewEdgeTable，NET）按边的下端点y坐标，对非水平边进行分类的链表每条扫描线（y坐标）：建立它的新边表作用避免盲目求交（增量算法的初值）计算第二类交点坐标26扫描线算法(改进)AET的建立先按下端点的y坐标值对所有的边进行分组对每条边：若低端点y值为ymin，则该边就放在ymin所对应的桶中桶中的各边：按下端点的x坐标值排序2728∧∧∧∧7-5/2373/25∧209∧13011∧0128765437-5/2973/211∧224466810128101214（7，7）（2，9）（13，11）（13，5）（7，1）（2，3）l1l2l3l4l5l6l1l6l2l5l3l4扫描线算法(改进)建立NET;AET为空;foreach扫描线iNET[i]按x顺序插入AET;按AET边顺序产生区间;填充区间;遍历AET，删除y_max=i的结点，对y_maxi的结点，令x=x+deltax;29例：活性边表的更新。30∧∧7-5/2373/25∧20913011∧0128765437-5/2973/211l1l6l2l5l3l49101117/23/25∧13011∧103/25∧20923/23/25∧20920920920917/23/21113011∧103/2117-5/2913011∧13011∧23/23/21113011∧224466810128101214（7，7）（2，9）（13，11）（13，5）（7，1）（2，3）l1l2l3l4l5l6扫描线算法(改进)9/2-5/23扫描线算法(改进)优点：每个像素只访问一次，避免了反复求交点等大量运算与设备无关缺点数据结构复杂只适合软件来实现31扫描转换在GIS上的应用多边形的矢量-栅格转换32扫描转换的边界标志算法栅格算法扫描填充算法阅读33扫描转换与区域填充扫描转换算法区域填充算法34种子填充算法区域：点阵表示的图形，像素集合表示方法内点表示区域内的所有像素具有同一颜色，而区域外的所有像素具有另一种颜色边界表示区域边界上的所有像素具有特定的颜色（可以是填充色），在区域内的所有像素均不能具有这一特定颜色，而且边界外的像素也不能具有与边界相同的颜色35表示内点表示边界点种子填充算法基本思想：假设在多边形区域内部至少有一个像素是已知的（此像素称为种子像素），由此出发找到区域内所有其他像素，并对其进行填充空间连贯性种子填充算法要求区域是连通的36种子填充算法4连通区域：区域中任意两点可通过上下左右四个方向互相到达8连通区域：区域中任意两点可通过上下左右和对角线八个方向互相到达37种子填充算法4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有不同要求依据区域内点能否访问到区域外的点，对边界的要求是4连通区域，边界只要8连通即可8连通区域，边界必须是4连通例：如左图（1）4连通区域，边界为像素（2）8连通区域，边界为和像素38种子填充算法分类四向算法从四个方向寻找下一像素点有时不能通过狭窄区域，因而不能填满多边形八向算法允许从八个方向搜索下一像素点有时会填出多边形的边界39种子填充算法40voidBoundaryFill4(intx,inty,intoldColor,intnewColor){color=GetPixel(x,y);if((color!=oldColor)&&(color!=newColor)){SetPixel(x,y,newColor);BoundaryFill4(x+1,y,oldColor,newColor);BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,newColor);}}简单的种子填充算法(四向算法)种子填充算法栈实现的种子填充算法(四向算法)41voidBoundaryFill4(intx,inty,intboundColor,intnewColor){intpx=x,py=y;stackPush(px,py);while(!stackEmpty()){stackPop(&px,&py);SetPixel(x,y,newColor);color=GetPixel(px+1,py);if((color!=boundColor)&&(color!=newColor))stackPush(px+1,py);color=GetPixel(px,py+1);if((color!=boundColor)&&(color!=newColor))stackPush(px,py+1);color=GetPixel(px-1,py);if((color!=boundColor)&&(color!=newColor))stackPush(px-1,py);color=GetPixel(px,py-1);if((color!=boundColor)&&(color!=newColor))stackPush(px,py-1);}}//填充//入栈6754S9328S24793847948479568479684797847984799479479S799填充S填充2填充3填充4填充5填充6填充7填充8填充946532897S42种子填充算法种子填充算法简单的种子填充算法的缺陷有些像素会多次入栈，降低算法效率要求有很大的存储空间来实现栈结构递归执行，算法简单，但效率不高，区域内每一像素都引起一次递归，需要进行入/出栈操作不沿四方向盲目填充有指定方向扫描线算法43区域填充的扫描线算法在任意不间断区间中只取一个种子像素不间断区间指在一条扫描线上一组相邻元素填充当前扫描线上的不间断区间；在当前填充区间上下扫描线上寻找新的种子点，作为新的填充区间可以填充有孔区域，对于每一个待填充区段，只需入栈一次，因此提高了区域填充的效率44区域填充的扫描线算法初始化：堆栈置空，将种子(x,y)入栈种子出栈（准备填充）：若栈