4.1实面积图形的概念4.2有效边表填充算法4.3边缘填充算法4.4区域填充算法4.1实面积图形的概念4.1.1多边形的定义1凸多边形多边形上任意两顶点间的连线都在多边形之内，凸点对应的内角小于180°,只具有凸点的多边形称为凸多边形。2凹多边形多边形上任意两顶点间的连线有不在多边形内部的部分，凹点对应的内角大于180°,有一个凹点的多边形称为凹多边形。3环多边形内包含有另外的多边形。如果规定每条有向边的左侧为其内部实面积区域，则当观察者沿着边界行走时，内部区域总在其左侧，也就是说多边形外轮廓线的环形方向为逆时针，内轮廓线的环形方向为顺时针。这种定义了环形方向的多边形称为环。4.1.2多边形的表示多边形的顶点表示法是用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换，顶点表示法如图4-3所示。⑶多边形的扫描转换4.1.3多边形的填充4.1.4区域填充4.2有效边表填充算法4.2.1填充原理图4-5用一条扫描线填充多边形4.2.2边界像素的处理原则图4-6边界像素的问题图4-8面积3×3按照以上原则对图4-5中的一些特殊点进行处理：1.P2点的处理原则图4-5中P2是边P3P2的终点，同时也是边P2P1的起点。按照“下闭上开”的原则，可以自动处理。2.P0、P3、P5点和P4点的处理原则对局部最高点P4，根据“下闭上开”的原则，P4点不予填充，y＝5扫描线会自动填充P4点，如图4-10所示。对局部最低点P0、P3和P5的处理方法为，填充时设置一个逻辑变量（初始值为假），每访问一个结点，逻辑变量值取反一次，若逻辑变量值为真，则填充该区间，这样可以保证局部最低点处理正确。设多边形P的顶点为Pi=（xi,yi）,i=0,1,…，n-1,这些顶点可以分为两类：极值点和非极值点。如果(yi-1-yi)(yi+1-yi)≥0，则称顶点Pi为极值点（如P0、P3、P5和P4点）；否则称为非极值点（如P2点）。为使每一条扫描线与多边形P的边界的交点个数始终为偶数，规定当点是多边形P的极值点时，该点按两个交点计算，否则按一个交点计算。对于每一条扫描线，多边形的填充步骤为：计算扫描线与多边形各边的交点，设交点个数为n。把所有的交点按x值递增的顺序进行排列。将排序后的第1个和第2个交点，第3个和第4个交点，…，第n-1个和第n个交点配对，每对交点就代表扫描线与多边形的一个相交区间。把相交区间内的像素置成多边形的颜色，相交区间外的像素设置成背景色。4.2.3有效边和有效边表设有效边的斜率为k。假定有效边与当前扫描线yi的交点为（xi，yi），则有效边与下一条扫描线yi+1的交点为（xi+1，yi+1）。其中,xi+1=xi+1/k=xi+⊿x/⊿y，yi+1=yi+1。如图4-11所示。这说明随着扫描线的移动，扫描线与有效边交点的x坐标从起点开始可以按增量1/k计算出来。把有效边按照与扫描线交点x坐标递增的顺序存放在一个链表中，称为有效边表，有效边表的结点如下：有效边表的数据结构：classCAET//有效边表类{public:CAET();//构造函数virtual~CAET();//析构函数doublex;intyMax;doublek;//程序中令k=⊿x/⊿yCAET*next;}P0扫描线的最大值为Smax＝12，最小值为Smin＝1，共有12条扫描线，每条扫描线之间间隔1个像素单位。每条扫描线的有效边表为如图4～18所示。这条扫描线处理完毕后对于P3、P4和P4、P5两条边，因为下一条扫描线S=5和ymax相等，根据“下闭上开”的原则予以删除。这条扫描线处理完毕后对于P2、P3边，因为下一条扫描线S=7和ymax相等，根据“下闭上开”的原则予以删除。当S＝7时，添加上新边P1、P2。当S＝8时，添加上新边P0、P1和P0、P6。S=11的扫描线处理完毕后对于P1P2边和P0、P1边，因为下一条扫描线S=12和ymax相等，根据“下闭上开”的原则予以删除。至此，全部有效边表已经给出。4.2.4边表(1)边表是按照扫描线顺序管理边的出现情况的一个数据结构。首先，构造一个纵向扫描线链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点称为桶，对应多边形覆盖的每一条扫描线。对于每一条扫描线，如果新增多条边，则按x|ymin坐标递增的顺序存放在一个链表中，若x|ymin相等，则按照1/k由小到大排序，这样就形成边表，如图4-14所示。对于图4-13示例多边形。边表结构如图4-15所示。