2.3 区域填充算法

2.3 区域填充算法

2.3.1 基础知识

区域填充即给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色，本节中我们就以此为例讨论区域填充算法。

多边形填色即给出一个多边形的边界，要求对多边形边界范围的所有象素单元赋予指定的色代码。要完成这个任务，一个首要的问题，是判断一个象素是在多边形内还是外。数学上提供的方法是“扫描交点的奇偶数判断”法：

1、将多边形画在纸上。

2、用一根水平扫描线自左而右通过多边形而与多边形之边界相交。扫描线与边界相交奇次数后进入该多边形，相交偶次数后走出该多边形。图2.3.1示出这类情况：扫描线与多边形相交四点。相交a点之后入多边形；交b点（第2交点）之后出多边形；交c点（第3交点）之后又入多边形；交d点（第4交点）之后又出多边形。

上述方法似乎能完满地解决问题，但事实并非如此，因为直线在光栅化后变成了占有单位空间的离散点。图2.3.1中的A点处和B、C处，在光栅化后变成图2.3.2所示的情况。此时，使用上述判断法则，在A、B、C处发现错判现象。在A处，扫描线通过一点后以为入多边形，其实此时已出多边形。结果是在A点之后的扫描线段上全都错误地填上色。在B和C处，因为光栅化后，使得扫描线通过交点的个数发生变化而同样导致填色错误。因此，原始的奇偶判断方法需要加以周密地改善，才能成为计算机中实用的填色算法。电脑爱好者网B W6W1~^TlL8_a

                            图2.3.1                                                                            图2.3.2

填色算法分为两大类：电脑爱好者网z:kB,xO

1、扫描线填色（Scan-Line Filling）算法。这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色。电脑爱好者网2N4c/Q4sM-E5[{/\xl)s

2、种子填色（Seed Filling）算法。这类算法建立在多边形边边界的图象形式数据之上，并还需提供多边形界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。