下载掌阅APP，畅读海量书库
立即打开
在计算机图形学中，填充是一种重要的技术，用于在二维平面上绘制封闭图形并填充其内部区域。通过对封闭图形的填充，我们可以为图形添加颜色、纹理或其他视觉效果，从而增强图形的表达力和视觉吸引力（参见图2-8）。
图2-8 填充的示意图
填充算法的核心思想是根据给定的边界条件，确定封闭图形的内部区域，并对该内部区域进行遍历和填充。不同的填充算法在填充效率、准确性以及适用场景上有所不同。例如，简单的扫描线填充算法通过逐行扫描并判断像素是否位于图形内部来实现填充；更复杂的区域生长算法则通过设定种子点，并根据一定的生长规则来逐步扩展填充区域。
在本节中，我们将介绍几种常见的填充算法，包括算法基本原理、实现步骤以及优缺点。同时，我们还将探讨这些算法在实际应用中的性能表现，并讨论如何根据具体需求选择合适的填充算法。此外，我们还将关注填充算法的优化策略，以提高填充的效率和质量，为相关领域的研究和应用提供有益的参考。
扫描线填充算法是一种用于填充多边形内部区域的算法。它的基本思想是利用一组水平或垂直的扫描线，按照一定的顺序（通常是从上到下或从下到上）扫描多边形，并确定扫描线与多边形边界的交点。一旦这些交点被确定，算法就会在这些交点之间绘制线段，以填充多边形内部区域。通过这种方式，算法就能够逐步填充整个多边形区域。
扫描线填充算法充分利用了相邻像素之间的连贯性，避免了对像素的逐点判断和求交运算，从而提高了算法效率。这里的连贯性包括区域连贯性、扫描线连贯性及边的连贯性。区域连贯性指多边形定义的区域内部相邻的像素具有相同的性质（比如，具有相同的颜色等）。扫描线连贯性是区域连贯性在一条扫描线上的反映。边的连贯性则是直线的线性性质在光栅上的表现。
扫描线填充算法的实现步骤如下：
1） 初始化 ：确定扫描线的起始位置和方向（水平或垂直）。同时，初始化一个空的活动边表（Active Edge Table，AET），用于存储与当前扫描线相交的边。
2） 求交 ：计算当前扫描线与多边形各边的交点。这通常涉及线段与扫描线的位置关系判断以及交点坐标的计算。
3） 交点排序 ：将计算出的交点按照它们在扫描线上的 x 坐标进行排序。排序的目的是确保在填充时能够按照正确的顺序连接交点。
4） 颜色填充 ：根据排序后的交点，将相邻的交点两两配对，并在两点之间绘制线段。线段的颜色即为要填充的颜色。这个过程会填充扫描线与多边形边界之间的区域。
5） 更新活动边表 ：根据当前扫描线与多边形的交点情况，更新活动边表。将不再与下一条扫描线相交的边从活动边表中移除，同时加入新的相交边。
6） 判断处理是否完成 ：检查所有的扫描线是否都已处理完毕。如果是，则算法结束；否则，移动扫描线到下一个位置，并返回步骤2继续处理。
扫描线填充算法的关键在于有效地管理和更新活动边表，以及快速、准确地计算扫描线与多边形边的交点。通过优化这些步骤，可以提高算法的效率和稳定性。此外，算法还需要考虑一些特殊情况，如交点恰好是多边形顶点的情况，以确保填充结果的正确性和美观性。
扫描线填充算法充分利用了多边形的区域连贯性、扫描线连贯性和边的连贯性，避免了大量的求交运算，提高了填充效率。然而，该算法的数据结构和程序结构复杂，对各种表进行维护和排序的开销很大，不适合硬件实现。
种子填充算法又称为边界填充算法，该算法的基本思想是从多边形区域的一个内部点（种子点）开始，由内向外逐步扩展，用指定的颜色填充像素，直到遇到边界为止。在填充过程中，算法会根据当前像素的颜色或属性，以及与相邻像素的关系，来确定是否继续填充。通过这种方式，算法能够确保只填充多边形的内部区域，而不填充边界外的部分。
种子填充算法的实现步骤如下：
1） 选择种子像素 ：在多边形区域内选择一个点作为种子像素。这个种子像素通常是多边形内部的一个点，可以手动选择，也可以使用自动化方法确定。
2） 初始化 ：将所有像素标记为未填充状态，并将种子像素标记为已填充状态。同时，设置填充颜色为指定颜色。
3） 检查相邻像素 ：从种子像素开始，检查其相邻像素（通常是上、下、左、右四个方向，也可以扩展到八个方向）。如果相邻像素未被填充且满足填充条件（如颜色与边界不同），则将相邻像素标记为已填充状态，并加入待处理像素列表中。
4） 递归填充 ：从待处理像素列表中取出一个像素，重复步骤3，检查其相邻像素并进行填充，直到待处理像素列表为空。
5） 结束条件 ：当待处理像素列表为空时，说明整个多边形内部区域已经填充完毕，算法结束。
种子填充算法又可以分为泛滥填充算法和边界填充算法。前者从种子点开始，将所有四连通或八连通区域内某种指定颜色的像素都替换成填充色，而不强调区域的边界。后者强调边界的存在，只要是边界内部的像素，均要替换为填充色。两种算法的本质相同，都是通过搜索和递归实现区域填充，主要区别在于递归的结束条件不同。
需要注意的是，种子填充算法在实现时需要考虑一些特殊情况，如多边形内部存在空洞或凹陷的情况，以及边界像素的处理。此外，为了提高算法的效率，可以采用一些优化技巧，如并行化处理、多种子分割等。
种子填充算法在计算机图形学、图像处理等领域具有广泛的应用，它能够精确地实现多边形内部填充，并可以与其他算法结合使用，以实现更复杂的图形处理任务。