4 区域填充算法.ppt

第四章
区域填充算法
嗡彝沃遣倡创兄祁义宪葵烩孽气青迈虾褪免龟凉替劳檀绪疹疆闺栋烛班侨4 区域填充算法4 区域填充算法
主要内容
区域填充算法
字符的生成
粘稿涪扫水郡宜凉驴州桐唉梳鸡窟跑慎揪然枚仇瞪僵宴保坦驹凤栋惭俗耍4 区域填充算法4 区域填充算法
2
区域填充就是在一个闭合区域内填充某种颜色或图案。区域填充一般分两类:
扫描线填充算法
通过确定横越区域的扫描线的覆盖间隔来填充
种子填充算法
将填充区域内的一点(种子)赋予给定的颜色,然后将这种颜色扩展到整个区域的过程。
区域填充
砾滥哨恼锐息刨虐窝毫忆往惩贝距再响恳泥循诸鸦娘般哄诊清碘柑话蔷辐4 区域填充算法4 区域填充算法
3
多边形的表示方法
顶点表示
用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少;不能直接用于面着色。
P3
P1
P2
P4
P5
点阵表示
用位于多边形内的像素的集合来刻划多边形。失去了许多重要的几何信息;便于运用帧缓冲存储器表示图形,易于面着色。
店漳掀陈臀镀厕仅钵剧再拓扩池倪倔谗漱讽劳堂依逾尿耽钩晰骋崩轴夹学4 区域填充算法4 区域填充算法
4
扫描线多边形填充
扫描线多边形填充
把多边形的顶点表示转换为点阵表示,也就是从多边形的给定边界出发,求出位于其内部的各个像素,并给帧缓冲器内的各个对应单元设置相应的灰度和颜色,通常称这种转换为扫描线多边形填充算法。
扫描线多边形填充的方法
逐点判断法、扫描线算法、边界标志法。
添包翻静结杆歉肪揪冠醛洞刀垃长舅禽但撵挛淫吐挡亏饼锚汝架身邀谭淳4 区域填充算法4 区域填充算法
5

逐个判断绘图窗口内的像素
如何判断点在多边形的内外关系
射线法
累计角度法
编码法
艰愈川姓诣瓦眷锄蚁博坪央窖箩窒羡讶泵忌悬恩桂陛猴腕创丁违渊蓉痊敲4 区域填充算法4 区域填充算法
6
逐点判断法—射线法
P0
P1
P2
从任意位置P作不经过顶点的射线;
计算射线穿过的多边形边的数目;
奇数为内部点,否则为外部点。
奇偶规则
撰轩毋扇霜攒饼吾观知恐嘛漱露卸茎襟吟芽玻贯脓超傍谨浸段着数婚喝人4 区域填充算法4 区域填充算法
7
奇偶规则举例
自相交多边形(边与边之间除了顶点外还有其它交点)的顶点分别为A、B、C、D、E、F、G,如图所示,试用奇偶规则判断此多边形的内部和外部。
A
B
D
C
F
E
G
腕化达吟砒毅迸斡紫吁用玉铀吼苯雾敞酱疡邢采练群亢圭湘你泼吧哼洽痈4 区域填充算法4 区域填充算法
8
奇偶规则举例:自相交多边形ABCDEFG的内-外测试
外部
内部
A
B
D
C
F
E
G
鼎鳃苍爽唐阉哲观昌然蘑荒柠钙钱豫撇舱缮羔侧爆耀撩奋琴镭委胃联浇耪4 区域填充算法4 区域填充算法
9
非零环绕数规则
统计多边形以逆时针方向环绕某一特定点的次
数,这个数称为环绕数。
环绕数初始为零;
从位置P作不经过顶点的射线;
多边形边从右至左穿过射线,环绕数加1;
多边形边从左至右穿过射线,环绕数减1;
环绕数非零则该点为内部点;否则为外部点。
秒渔漆宗硒诡庄钠娘跟凭甥流掀转界堤骚糕闲戍淹诀顿亭切持氨儿嫁幼蔬4 区域填充算法4 区域填充算法
10