首页 / 软件开发 / 数据结构与算法 / 算法系列（十二） 多边形区域填充算法：几种边标志填充算法

算法系列（十二） 多边形区域填充算法：几种边标志填充算法2014-04-30 csdn博客 吹泡泡的小猫四、边界标志填充算法

在光栅显示平面上，多边形是封闭的，它是用某一边界色围成的一 个闭合区域，填充是逐行进行的，即用扫描线逐行对多边形求交，在交点对之间填充。边界标志填充 算法就是在逐行处理时，利用边界或边界颜色作为标志来进行填充的。准确地说，边界标志填充算法 不是指某种具体的填充算法，而是一类利用扫描线连贯性思想的填充算法的总称。这类算法有很多种 ，本篇就介绍几种。

首先介绍一种以边为中心的边缘填充算法，这种边界标志算法的基本思想 是：对于每一条扫描线和每一条多边形边的交点（xi，yi），将该扫描线上交点右方的所有象素取补， 依次对多边形的每条边作此处理，直到最终完成填充。这里要介绍一下取补的定义，假设某点的颜色 是M，则对该点的颜色取补得到M’ = A – M，A是一个很大的数字，至少要比所有合法的颜色值大。 根据取补的定义，如果对光栅位图某区域已经标记为M的颜色值做偶数次取补运算，该区域颜色不变； 而做奇数次取补运算，则该区域颜色变为值为M’的颜色。算法可以简单描述为两个步骤：

1、 将绘图窗口的背景色置为M’颜色；

2、对多边形的每一条非水平边，从该边上的每个象素开始 向右求余；

算法的处理过程如图（12）所示，左边是多边形的形状，右边分别是对每条边处理 完成后填充区域的颜色情况，初始背景颜色是M’，经过处理后，需要填充的区域是奇数次取补，最终 的颜色是要填充的正确值M，非填充区域经过偶数次取补，仍然是背景色M’：

图（12）边缘填充算法的处理过程

算法的实现非常简单，对于光栅位图的展示，我们仍然 采用前文所用的方法，用数字矩阵表示一块光栅位图区域，矩阵的每个位置表示一个像素点，用0－9 表示颜色值。本算法示例用9表示最大值A，0表示无效的区域，合法的颜色值就是1－8。

87 void EdgeCenterMarkFill（const Polygon& py, int color）88 {89 std::vector<EDGE3> et;90 91 InitScanLineEdgesTable（et, py）;//初始化边表92 93 FillBackground（A - color）; //对整个填充区域背景颜色取补94 for_each（et.begin（）, et.end（）, EdgeScanMarkColor）;//依次处理每一条边95 }76 void EdgeScanMarkColor（EDGE3& e）77 {78 for（int y = e.ymax; y >= e.ymin; y--）79 {80 int x = ROUND_INT（e.xi）;81 ComplementScanLineColor（x, MAX_X_CORD, y）;82 83 e.xi -= e.dx;84 }85 }