《计算机图形学》微课版 孔令德 三、填充多边形 期末复习

多边形的定义
多边形是由折线段组成的平面封闭图形。

1. 凸多边形

含有凸点的多边形称为凸多边形。凸点对应的内角小于180度。多边形上任意两顶点间的连线都在多边形之内

1. 凹多边形

至少有一个凹点的多边形称为凹多边形。凹点对应的内角大于180度。多边形上任意两顶点间的连线有不在多边形内部的部分

多边形的表示

1. 点元表示法

用多边形的顶点序列来表示多边形
特点是直观、几何意义强，易于图形变换，而且占用内存较少，但是不能区分多边形的内外部。

1. 面元表示法

用位于多边形内部的像素点集来表示多边形
特点是可以明确多边形的内部区域，并将内部区域的像素点显示成要求的颜色，但是缺少多边形顶点的几何信息。

1. 多边形的光栅化

将多边形的描述从点元表示法变换到面元表示法的过程，称为多边形的光栅化。

平面着色模式填充三角形（翻看教材了解）

有效边表算法

x扫描线算法

1. 确定多边形所占有的最大扫描线数：得到顶点的最小和最大y值（ymin和ymax）。
2. 从y＝ymin到y＝ymax每次用一条扫描线进行填充。

对每条扫描线的填充过程可分为以下4个步骤

1. 求交：计算扫描线与多边形各个边的交点。
2. 排序：将所有交点按x值的递增顺序排序。
3. 配对：将交点按递增顺序两两配成区间对
4. 填色：将区间对内的像素点设置成要求的颜色

当扫描线y＝1时，从边表中取出有效边，通过排序组成有效边表，将有效边表中的边的x值两两构成区间对填充，然后修改有效边的值：

如果ymax＜ymin，则该边已经处理完，不再为有效边，将其从有效边表中删除。
扫描线y=1

扫描线y＝2

当边表中的所有边都已经取出，而且有效边表也成为空表，说明所有边都已经处理，此时多边形内部全部填充完毕，扫描转换结束

注意：
y1为终点的y值 y0为起点的y值
k=(y1-y0)/(x1-x0)
教材有效边表表示方式：

桶表与边表

边填充算法

按任意顺序处理多边形的每条边。处理时，先求出该边与扫描线的交点，再对扫描线上交点右方的所有像素颜色取反。边缘填充算法思路简单，但对于复杂图形，每一像素可能被访问多次。

区域填充算法

区域填充要求区域是连通的。区域连通有四向连通区域和八向连通区域两种，四向连通区域指的是从区域上一点出发，通过上、下、左、右移动，即可到达区域内的任意像素；八向连通区域除了四向连通区域的四个方向外，还需要通过左上、右上、左下、右下这四个方向，才能到达区域内的任意位置。

八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。

两种边界，使用四向连通任何一种边界都能确保种子像素不会跨越边界。