从像素到多边形：深入理解填充算法

计算机图形学中，多边形填充是一个至关重要的环节，它决定了图像的视觉效果和渲染效率。在这个过程中，算法的选择和应用是关键。下面我们将介绍三种常见的多边形填充算法：边界填充算法、种子填充算法和扫描线填充算法。

一、边界填充算法

边界填充算法是最基础的多边形填充算法，其基本思想是检查每个像素是否在多边形内，如果是则进行填充。这个过程可以通过递归或迭代的方式实现。递归方式通常利用深度优先搜索，从多边形的任意一个像素开始，逐个检查相邻的像素。迭代方式则通常使用广度优先搜索，从多边形的边界开始，逐层向外检查像素。

以下是使用Python实现的简单边界填充算法示例代码：

def boundary_fill(image, x, y, new_value):
    old_value = image[x][y]
    if old_value != new_value:
        image[x][y] = new_value
        neighbors = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
        for nx, ny in neighbors:
            if 0 <= nx < width and 0 <= ny < height:
                boundary_fill(image, nx, ny, new_value)

二、种子填充算法

种子填充算法是从一个种子点开始，逐步向外填充像素，直到遇到多边形的边界为止。这个算法通常用于处理不规则形状的填充，如地图绘制、图像处理等。在实现上，种子填充算法通常采用递归或分治策略。递归方式类似于边界填充算法，只不过是从一个种子点开始。分治策略则是将多边形分成四个象限，分别处理后再合并结果。

以下是使用Python实现的简单种子填充算法示例代码：

def flood_fill(image, x, y, new_value):
    old_value = image[x][y]
    if old_value == new_value:
        return
    image[x][y] = new_value
    stack = [(x, y)]
    while stack:
        x, y = stack.pop()
        neighbors = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
        for nx, ny in neighbors:
            if 0 <= nx < width and 0 <= ny < height and image[nx][ny] == old_value:
                stack.append((nx, ny))
                image[nx][ny] = new_value

三、扫描线填充算法

扫描线填充算法是一种高效的多边形填充算法，它利用扫描线从上到下、从左到右依次扫描像素，遇到多边形的边界时进行填充。该算法的关键在于处理边界交点的判断和像素状态的更新。为了提高效率，扫描线填充算法通常采用双缓冲区技术，将待处理的像素点存储在一个缓冲区中，逐个进行处理。

以下是使用Python实现的简单扫描线填充算法示例代码：
```python}