计算机图形学 - 多边形填充算法
多边形是由顶点的有序列表组成，如下图所示。为了用特定的颜色填充多边形，需要确定落在多边形边界上的像素以及落在多边形内部的像素。在本章中，我们将了解如何使用不同的技术填充多边形。
扫描线算法
该算法通过将扫描线与多边形边相交来工作，并填充相交对之间的多边形。以下步骤描述了该算法的工作方式。
步骤1 - 从给定的多边形中找出Ymin和Ymax。
步骤2 - 扫描线与从Ymin到Ymax的多边形的每条边相交。命名多边形的每个交点。根据上图所示，它们被命名为p0、p1、p2、p3。
步骤3 - 按X坐标递增顺序对交点进行排序，即(p0, p1)、(p1, p2)和(p2, p3)。
步骤4 - 填充所有位于多边形内部的坐标对，并忽略交替的坐标对。
泛洪填充算法
有时我们会遇到一个对象，我们希望用不同的颜色填充其区域及其边界。我们可以用指定的内部颜色绘制此类对象，而不是像边界填充算法那样搜索特定的边界颜色。
它不依赖于对象的边界，而是依赖于填充颜色。换句话说，它用填充颜色替换对象的内部颜色。当不再存在原始内部颜色的像素时，算法完成。
同样，该算法依赖于四连通或八连通方法来填充像素。但它不是寻找边界颜色，而是寻找所有属于内部的相邻像素。
边界填充算法
边界填充算法顾名思义。该算法选择对象内部的一个点，并开始填充，直到到达对象的边界。为了使该算法有效，边界颜色和我们填充的颜色应该不同。
在这个算法中，我们假设整个对象的边界颜色相同。边界填充算法可以通过4连通像素或8连通像素来实现。
4连通多边形
在这种技术中，使用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；这是一个非零值。因此，该点被称为内部点。