一、矩形填充

1. 矩形表示

2. 算法实现

3. 边界之争

当两个矩形共享一条边时，存在该边属于谁的问题。对于任一个矩形，处理它的四个边的原则是：左闭右开，下闭上开

二、任意多边形填充

1. 多边形填充的定义及实现

• 多边形表示如图：

  
  

• 多边形扫描转换（多边形填充）：从多边形给定的边界出发，求出位于其内部的各个像素，并将缓冲区内的各个对应元素设置为相应的颜色或灰度，这种转换称为多边形的扫描转换。

  
  

• 多边形填充实现：

• 问题：如何判定像素点是否在多边形内部？即函数IsInside(P,x,y)如何实现？

射线法判断内外点

--  从无穷远处向该点引一条射线，如果这条射线与多边形的交点为奇数时，此点为内点，否则为外点。

--  推导：当扫描线与多边形相交奇数次后，线上点都是内点，偶数次相交后线上点都是外点。

--  特例：顶点是交点

射线与多边形顶点相交的交点个数判定：

a）共享顶点的两条边分别位于扫描线的两边，交点算一个。

b）共享顶点的两条边都位于扫描线的下边，交点算零个。

c）共享顶点的两条边都位于扫描线的上边，交点算二个。

• 实例：

2. 多边形扫描线填充算法

2.1  算法的辅助原理：

1）扫描线的连贯性

    a. 区域连贯性在一条扫描线上的反映

    b. 若多边形与扫描线相交的交点序列为x1、x2…，由区域连通性可得该交点序列的性质：

        --  交点数目为偶数；

        --  多边形内部和多边形外部两类线段相间排列；

    c. 如果区间某点属于多边形内(外)，那么该区间内所有点均属于多边形内(外)。

2）边的连贯性

    a 直线的线性性质在光栅上的表现

    b. 相邻扫描线与多边形的同一条边的交点存在如下关系：

    c. 当知道扫描线与一条边的一个交点之后，通过上述公式可以通过增量算法迅速求出其他交点 

2.2  算法的基本思想：

--  依据“扫描线交点的奇偶数判断”法：用一根水平扫描线自左而右通过多边形而与多边形的边界相交，扫描线与边界相交奇数次后进入该多边形，相交偶次数后走出该多边形。

--  每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标成对取出，作为两个端点，以所填的色彩画水平直线。多边形被扫描完毕后，填色也就完成

1）单条扫描线的扫描过程

    a. 求扫面线y=6与多边形的交点（如何求交点？）

    b. 排序1、2、3、4

    c. 配对(1,2)，(3,4)

    d. 填充

2）扫描过程中出现的交点问题

    a. 如何快速求得扫描线与多边形的交点？

        y=1，与多边形的交点为顶点；  y=2，交点如何求得？    思路：边的连贯性

                    y++ ；     x+=1/k

    b. 交点坐标为小数，如何处理？

    --为保证交点的坐标为可以绘制的整数像素点的坐标，需对交点的x坐标取整。如简单采取四舍五入的 方法，则会导致部分像素位于多边形之外。

    --  若交点位于多边形的左边界，则x=(int)x+1；否则x=(int)x

    c. 交点坐标为整数（像素点），如何处理？

     --  处理原则：左闭右开，下闭上开

     --  落在多边形左边界的像素点，填充；落在多边形右边界的像素点不填充

    d. 交点为多边形顶点，如何处理？

    --  对于多边形的水平边，不计它与扫描线的交点（水平边，不进行处理）

2.3 算法的实现

1）算法自定义数据结构

假设多边形如下图所示：

活动边：多边形中与当前扫描线相交的边。

活动边链表(AEL)：保存活动边的链表，其中活动边按与扫描线交点x递增顺序存放。

边表(ET)：存放在每条扫描线第一次出现的边。即某边的较低端点为ymin,则该边就放在扫描线ymin的边表中。

a. 活动边的定义、存储

b. 边表的定义、存储

按边下端点的纵坐标y 对非水平边进行分类的指针数组：

首先， 下端点的纵坐标y 值等于i 的边，归入第i 类；  其次， 同一类中，各边按x值递增的顺序排成行( x 值相等时，按deltax 的值)；  最后， 水平边不加入分类边表中。

上述多边形对应的边表如下：

c. 活动边链表（AEL）的定义、存储

    --  活动边链表由与当前扫描线相交的边组成

    记录了多边形的边沿扫描线的交点序列

    根据边的连贯性不断刷新交点序列

    --  基本单元是边(与扫描线相交的边)

    --  与分类边表不同

    分类边表记录初始状态

    活化边表随扫描线的移动而动态更新

上述多边形，当扫描线y=8时对应的AEL如下图：

2）算法的实现步骤

    a. 建立ET

    b. 初始化AEL为空

    c.将扫描线纵坐标y的初始值设为ET中非空的最小序号

    d. 重复执行以下步骤，直到AEL和ET均为空

        (a)如果ET中第y类非空，则将其中所有边取出插入到AEL中，并将AEL中所有边重新排序

        (b)对AEL中的边两两配对，对x取整后填充

        (c)当前扫描线y坐标递增1，y=y+1

        (d)将AEL中满足ymax=y的边删掉(遵循下闭上开的原则)

        (e)对AEL中剩下的边的x值做递增deltax

上述多边形对应的扫描过程（AEL的变化过程）如下所示：

3）算法的具体实现