文档介绍：Graphics
第4章基本光栅图形生成算法
p
多边形的分类:
0
凸多边形
凹多边形含内环的多边形
表示方法:顶点表示和点阵表示
顶点表示是用多边形的顶点的序列来描述多边形
心该表示几何意义强、占内存少
◆但它不能直观地说明哪些像素在多边形内
点阵表示是用位于多边形内的像素的集合来刻划
多边形
◇该方法虽然没有多边形的几何信息
◆是面着色所需要的图像表示形式
多边形填充就是
换为点阵表示
即从多边形的给定边
部的各个像素,并将
元素设置相应的灰庋
多边形的填充方法
扫描线方法
边缘填充方法
栅栏填充方法
边界标志方法
算法特点
充分利用了相邻象素之间的连续性,避免对象素的逐点判
断和反复求交运算,减少了计算量,提高了算法速度,是
效率较高的多边形填充算法,处理对象为非自交多边形
头于一般多边形的填充过程,对于一条扫描线,
可分为四步
心求交心排序交配对区间填色
基本概念:
区域的连续性
扫描线5
扫描线的连续性
5432
边的连续性
扫描线2
奇点的处理
23456
910X
区域的连续性
设多边形P的顶点P=(x1,y),i=,…,n,
各顶点P的纵坐标y的递减数列
Di yi yin
0≤k≤n-1
p6
p8
p1,p7,p3,p6,p2,p5,p0,p4,p8
位于y=y和y=y两条扫描线之间的长方形区域被多边形P的8
分割成若干梯形它们具有下列性质(设(x,y)为整数
(1)梯形的两底边分别在y=y和y=y两条扫描线上,腰在多边
形P的边上或在显示屏幕的边界上。
(2)梯形可分为两类:一类位于多边形P的内部;另
类在多边形P的外部
(3)两类梯形在长方形区域{,}相间的排列。
由区域的相关性知
y=yi
当知道一个区域内一与多边形的位置关系,勛可确定该区域
内所有点与多边形之间的内外关系
扫描线的连续性
扫描线的连续性是区域连续性在扫描线上的体现
设e为一整数y≥e≥y
该扫描线与P的边界各交点横坐标的递增序列
若扫描线y=e与多边形P的边
P1P相交,则记其交点的横坐标为a此交点序列具有以下性质
(1)l是偶数
由区域的连贯性和
扫描线的连续性知
(2)扫描线被分成好多区段,一部
分在多边形内,一部分在多边形外
(3)两类线段间隔排列
2
若已知某一点与多边形的位置关系就可知该点所在线段与
多边形的位置美系
边的连续性
若d为一整数,d=e-1,且y≥y≥ym;设位于扫描线y=d上的交点序列为
则两交点序列之间有以下关系:1两序列元素的个数相等
2点(x,e)与(x成,d)位于多边形P的同
边上,即
以性质称为
Cas___ca7__42
d4