多边形填充算法

多边形是顶点的有序列表，如下图所示。为了用特定的颜色填充多边形，您需要确定落在多边形边界上的像素和落在多边形内部的像素。在本章中，我们将了解如何使用不同的技术填充多边形。

扫描线算法

该算法的工作原理是使扫描线与多边形边相交，并填充交点对之间的多边形。以下步骤描述了该算法的工作原理。

步骤 1 - 找出给定多边形的 Ymin 和 Ymax。

步骤 2 - 扫描线与多边形的每条边从 Ymin 到 Ymax 相交。命名多边形的每个交点。如上图所示，它们被命名为p0、p1、p2、p3。

步骤 3 - 按 X 坐标的升序对交点进行排序，即 (p0, p1)、(p1, p2) 和 (p2, p3)。

步骤 4 - 填充多边形内的所有坐标对并忽略备用对。

洪水填充算法

有时我们会遇到一个对象，我们想要用不同的颜色填充该区域及其边界。我们可以使用指定的内部颜色绘制此类对象，而不是像边界填充算法中那样搜索特定的边界颜色。

它不依赖于对象的边界，而是依赖于填充颜色。换句话说，它用填充颜色替换对象的内部颜色。当不再存在原始内部颜色的像素时，算法完成。

该算法再次依赖于填充像素的四连接或八连接方法。但它不是寻找边界颜色，而是寻找属于内部的所有相邻像素。

边界填充算法

边界填充算法顾名思义。该算法在对象内部选取一个点并开始填充，直到它到达对象的边界。为了使该算法发挥作用，边界的颜色和我们填充的颜色应该不同。

在此算法中，我们假设整个对象的边界颜色相同。边界填充算法可以通过4连接像素或8连接像素来实现。

四连通多边形

在此技术中，使用 4 个连接的像素，如图所示。我们将像素放置在当前像素的上方、下方、右侧和左侧，并且此过程将继续，直到找到具有不同颜色的边界。

算法

步骤 1 - 初始化种子点（seedx、seedy）、fcolor 和 dcol 的值。

步骤 2 - 定义多边形的边界值。

步骤 3 - 检查当前种子点是否为默认颜色，然后重复步骤 4 和 5 直到到达边界像素。

If getpixel(x, y) = dcol then repeat step 4 and 5

步骤 4 - 使用种子点的填充颜色更改默认颜色。

setPixel(seedx, seedy, fcol)

步骤 5 - 递归地遵循四个邻域点的过程。

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)

第 6 步- 退出

这种技术有一个问题。考虑如下所示的情况，我们尝试填充整个区域。此处，图像仅被部分填充。在这种情况下，不能使用4连接像素技术。

8连通多边形

在此技术中，使用 8 个连接的像素，如图所示。我们将像素放置在当前像素的上方、下方、右侧和左侧，就像我们在 4 连接技术中所做的那样。

除此之外，我们还将像素放在对角线上，以便覆盖当前像素的整个区域。这个过程将继续，直到我们找到不同颜色的边界。

算法

步骤 1 - 初始化种子点（seedx、seedy）、fcolor 和 dcol 的值。

步骤 2 - 定义多边形的边界值。

步骤 3 - 检查当前种子点是否为默认颜色，然后重复步骤 4 和 5 直到达到边界像素

If getpixel(x,y) = dcol then repeat step 4 and 5

步骤 4 - 使用种子点的填充颜色更改默认颜色。

setPixel(seedx, seedy, fcol)

步骤 5 - 递归地遵循四个邻域点的过程

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)

第 6 步- 退出

4 连接像素技术无法填充下图标记的区域，而 8 连接技术不会发生这种情况。

内外测试

这种方法也称为计数法。在填充对象时，我们经常需要识别特定点是在对象内部还是外部。有两种方法可以识别特定点是在物体内部还是外部。

奇偶规则
非零绕数规则

奇偶规则

在这种技术中，我们将计算沿线从任意点 (x,y) 到无穷远交叉的边。如果交互次数为奇数，则点(x,y)为内点；如果交互次数为偶数，则点 (x,y) 为外点。以下示例描述了这个概念。

从上图可以看出，从点(x,y)开始，左边的交互点数量为5个，右边的交互点数量为3个。从两端开始，交互点的数量都是奇数，所以该点被视为在对象内。

非零缠绕数规则

此方法也可与简单多边形一起使用来测试给定点是否在内部。借助大头针和橡皮筋就可以简单地理解它。将大头针固定在多边形的一条边上，并将橡皮筋绑在其中，然后沿着多边形的边拉伸橡皮筋。

当多边形的所有边都被橡皮筋覆盖后，检查已固定在待测点处的销钉。如果我们在该点发现至少有一阵风，则认为它在多边形内，否则我们可以说该点不在多边形内。

在另一种替代方法中，给出多边形所有边的方向。从待测点向X方向最左侧画一条扫描线。

将值 1 赋予所有向上方向的边，将所有其他边赋予 -1 作为方向值。
检查扫描线所经过的边缘方向值并将它们相加。
如果该方向值的总和不为零，则该待测点为内点，否则为外点。
上图中，我们将扫描线所经过的方向值相加，则总数为1 – 1 + 1 = 1；这是非零的。所以该点被称为内点。