Python图形填充算法入门指南：闭合区域处理与常用填充算法详解

---

Python图形填充算法入门指南：闭合区域处理原理及常用算法详解

---

引言

在计算机图形学中，填充算法是核心基础技术之一。无论是图像编辑软件中的“油漆桶工具”，还是游戏引擎中的地形渲染，甚至是医学影像分析，填充算法都扮演着关键角色。本文将带初学者系统学习填充算法的概念、分类及Python实现，助你快速掌握闭合区域处理的核心技能！

---

一、填充算法基础概念

1.1 什么是填充算法？

填充算法（Filling Algorithm）用于在图形中识别并填充闭合区域。其核心任务是：判断哪些像素/区域属于目标闭合区域，并用指定颜色或模式覆盖。

1.2 为什么需要填充算法？

图像编辑：如Photoshop中的魔棒工具、油漆桶工具。

游戏开发：2D/3D场景渲染（如地形、纹理填充）。

工业设计：CAD图纸的剖面填充。

医学影像：器官轮廓分割与标记。

---

二、填充算法分类与原理

---

2.1. 洪水填充算法（Flood Fill Algorithm）

核心原理

目标：从种子点开始扩散，填充所有连通的同色区域。

步骤：

1. 选择种子点：指定起始坐标和填充颜色。
2. 扩散填充：递归或迭代检查相邻像素（四邻域或八邻域），若颜色与种子点相同则填充。
3. 边界限制：遇到边界颜色（或不同颜色）时停止扩散。

典型应用场景

图像编辑工具（如油漆桶工具）。

迷宫生成与求解中的区域标记。

Python 代码示例

递归实现（注意栈溢出风险）：

def flood_fill_recursive(image, x, y, target_color, fill_color):
    if x < 0 or x >= len(image[0]) or y < 0 or y >= len(image):
        return
    if image[y][x] != target_color or image[y][x] == fill_color:
        return
    image[y][x] = fill_color
    # 四邻域扩散
    flood_fill_recursive(image, x+1, y, target_color, fill_color)
    flood_fill_recursive(image, x-1, y, target_color, fill_color)
    flood_fill_recursive(image, x, y+1, target_color, fill_color)
    flood_fill_recursive(image, x, y-1, target_color, fill_color)

# 示例：填充一个4x4图像的内部
image = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 0]
]
flood_fill_recursive(image, 1, 1, 1, 2)
# 结果：中心2x2区域被填充为2

迭代实现（队列优化，避免栈溢出）：

from collections import deque

def flood_fill_iterative(image, x, y, target_color, fill_color):
    queue = deque([(x, y)])
    visited = set()
    while queue:
        x, y = queue.popleft()
        if (x, y) in visited:
            continue
        if image[y][x] != target_color:
            continue
        image[y][x] = fill_color
        visited.add((x, y))
        # 八邻域扩散
        for dx in [-1, 0, 1]:
            for dy in [-1, 0, 1]:
                nx, ny = x+dx, y+dy
                if 0 <= nx < len(image[0]) and 0 <= ny < len(image):
                    queue.append((nx, ny))

# 示例：填充8邻域区域
flood_fill_iterative(image, 2, 2, 0, 3)  # 填充右下角

关键细节

邻域选择：四邻域（上下左右）或八邻域（包含对角线）。

性能陷阱：递归实现可能导致栈溢出，需改用队列（BFS）或栈（DFS）迭代。

---

好的！我们先从第一种算法开始，每次讲解两种，结合具体案例和代码实现。每次讲解完会提示你继续，你可以随时提问。

---

2.2. 扫描线填充算法（Scanline Fill Algorithm）

核心原理

目标：填充闭合路径的内部区域。

步骤：

1. 扫描线移动：从图形顶部到底部，逐行（水平线）扫描。
2. 交点计算：记录每条扫描线与路径边界的交点。
3. 填充规则：根据奇偶规则（交点数量为奇数时开始填充，偶数时停止）确定填充区间。
4. 颜色填充：在交点之间的像素填充颜色。

典型应用场景

位图填充（如绘制多边形、游戏中的2D地形生成）。

Python 代码示例

以下是一个简化的手动实现（不依赖图形库）：

def scanline_fill(polygon, height, width):
    # 初始化空白画布（0表示未填充，1表示填充）
    canvas = [[0 for _ in range(width)] for _ in range(height)]
    
    # 遍历每一行（扫描线）
    for y in range(height):
        intersections = []
        # 遍历多边形的每一条边
        for i in range(len(polygon)):
            x1, y1 = polygon[i]
            x2, y2 = polygon[(i+1) % len(polygon)]
            # 判断边是否与扫描线相交
            if (y1 <= y < y2) or (y2 <= y < y1):
                # 计算交点的x坐标（线性插值）
                if y1 != y2:
                    x_intersect = x1 + (x2 - x1) * (y - y1) / (y2 - y1)
                    intersections.append(x_intersect)
        # 对交点排序并按奇偶规则填充
        intersections.sort()
        for i in range(0, len(intersections), 2):
            start = int(intersections[i])
            end = int(intersections[i+1]) if i+1 < len(intersections) else width
            for x in range(start, end):
                if 0 <= x < width:
                    canvas[y][x] = 1
    return canvas

# 示例：填充一个三角形
polygon = [(50, 20), (10, 80), (90, 80)]
canvas = scanline_fill(polygon, height=100, width=100)

# 可视化（需安装Pillow库）
from PIL import Image
img = Image.new('1', (100, 100))
for y in range(100):
    for x in range(100):
        img.putpixel((x, y), canvas[y][x])
img.show()

关键细节

交点处理：需要排序并按奇偶规则配对。

性能优化：实际库（如Pillow）会使用更高效的交点计算方式（如活性边表）。

---

2.3. 射线法（Ray Casting Algorithm）

核心原理

目标：判断某点是否在闭合区域内。

步骤：

1. 发射射线：从待测点向右水平发射一条射线。
2. 统计交点：计算射线与路径边界的交点数量。
3. 奇偶规则：奇数交点在内部，偶数交点在外部。

典型应用场景

地理围栏判断（如用户是否在某个区域内）。

SVG/矢量图形中的点击检测。

Python 代码示例

使用 shapely 库简化实现：

from shapely.geometry import Point, Polygon

def ray_casting(point, polygon):
    # 创建几何对象
    p = Point(point)
    poly = Polygon(polygon)
    # 直接调用库方法（底层原理即射线法）
    return p.within(poly)

# 示例：判断点(50,50)是否在四边形内
polygon = [(30, 30), (70, 30), (70, 70), (30, 70)]
point = (50, 50)
print(ray_casting(point, polygon))  # 输出 True

# 手动实现射线法（简化版）
def manual_ray_casting(point, polygon):
    x, y = point
    n = len(polygon)
    inside = False
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i+1) % n]
        # 检查点是否在边的y范围内
        if ((y1 > y) != (y2 > y)):
            # 计算射线与边的交点的x坐标
            x_intersect = (y - y1) * (x2 - x1) / (y2 - y1) + x1
            if x < x_intersect:
                inside = not inside
    return inside

print(manual_ray_casting((50, 50), polygon))  # 同样输出 True

关键细节

水平射线方向：通常选择向右，避免与顶点重合时的复杂处理。

精度问题：手动实现时需处理浮点数误差（如使用 epsilon 容差）。

---

好的！接下来我们继续讲解两种算法：平面扫描算法（Bentley-Ottmann） 和 边缘跟踪（Edge Tracking）。这两种算法分别适用于不同场景，且对理解复杂闭合区域检测非常有帮助。

---

2.4. 平面扫描算法（Bentley-Ottmann Algorithm）

核心原理

目标：高效检测线段之间的交点，辅助分割路径并识别闭合区域。

步骤：

1. 事件队列：将所有线段的端点作为初始事件点，按坐标排序。
2. 扫描线移动：垂直线从左到右扫描平面，维护当前与扫描线相交的线段集合（状态结构）。
3. 交点检测：当扫描线遇到线段端点或交点时，检查相邻线段是否相交，并将新交点加入事件队列。
4. 动态更新：持续处理事件队列直到所有交点和端点处理完毕。

典型应用场景

处理复杂交叉路径（如迷宫、电路布线图）。

分割闭合区域时的高效交点计算。

Python 代码示例

这里提供一个简化版实现（仅处理线段交点检测）：

from sympy import Segment, Point

def bentley_ottmann_intersections(segments):
    # 使用sympy的Segment类处理线段交点
    intersections = set()
    for i in range(len(segments)):
        seg1 = Segment(*segments[i])
        for j in range(i+1, len(segments)):
            seg2 = Segment(*segments[j])
            intersect = seg1.intersection(seg2)
            if intersect:
                intersections.add((float(intersect[0].x), float(intersect[0].y)))
    return intersections

# 示例：检测两条线段的交点
segments = [
    (Point(0, 0), Point(5, 5)),   # 线段1
    (Point(0, 5), Point(5, 0))    # 线段2
]
print(bentley_ottmann_intersections(segments))  # 输出 {(2.5, 2.5)}

关键细节

复杂度：实际完整实现需使用平衡树维护状态结构，复杂度为 O((n+k) log n)（k为交点数）。

库依赖：实际项目中建议使用现有库（如CGAL或sympy）避免手动实现复杂逻辑。

---

2.5. 边缘跟踪（Edge Tracking）

核心原理

目标：从栅格图像中提取闭合轮廓。

步骤：

1. 扫描起点：逐行扫描像素，找到未标记的边缘起点。
2. 轮廓追踪：从起点出发，按顺时针或逆时针方向沿边缘移动，记录路径点。
3. 闭合判断：当回到起点时，判定为闭合轮廓；否则标记为开放路径。
4. 重复扫描：继续扫描直到处理完所有像素。

典型应用场景

图像处理中的轮廓提取（如医学图像分析、OCR）。

二值化图像中的形状识别。

Python 代码示例

手动实现边缘跟踪（模拟OpenCV的findContours）：

def edge_tracking(binary_image):
    height, width = len(binary_image), len(binary_image[0])
    visited = [[False for _ in range(width)] for _ in range(height)]
    contours = []

    # 8邻域方向定义（顺时针从左上开始）
    directions = [(-1, -1), (-1, 0), (-1, 1),
                  (0, 1),  (1, 1),  (1, 0),
                  (1, -1), (0, -1), (-1, -1)]

    for y in range(height):
        for x in range(width):
            if binary_image[y][x] == 1 and not visited[y][x]:
                contour = []
                # 从当前点开始追踪
                current = (x, y)
                start = current
                dir_idx = 0  # 初始搜索方向

                while True:
                    contour.append(current)
                    visited[current[1]][current[0]] = True
                    found = False
                    # 尝试8个方向寻找下一个边缘点
                    for i in range(8):
                        dx, dy = directions[(dir_idx + i) % 8]
                        nx, ny = current[0] + dx, current[1] + dy
                        if 0 <= nx < width and 0 <= ny < height:
                            if binary_image[ny][nx] == 1 and not visited[ny][nx]:
                                current = (nx, ny)
                                dir_idx = (dir_idx + i - 2) % 8  # 更新方向
                                found = True
                                break
                    if not found:
                        break
                    # 检查是否回到起点
                    if current == start and len(contour) > 2:
                        contours.append(contour)
                        break
    return contours

# 示例：检测二值图像中的闭合轮廓
binary_image = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
contours = edge_tracking(binary_image)
print("检测到轮廓数量:", len(contours))  # 输出 1（一个闭合方框）

关键细节

方向策略：通常使用“右手法则”（始终优先右转）确保完整追踪。

OpenCV 优化：实际中应使用库函数（如cv2.findContours）以提高性能和准确性。

---

好的！接下来继续讲解 图论环检测（Cycle Detection） 和 非零环绕数规则（Non-Zero Winding Number），结合代码和实例说明它们的原理和应用。

---

2.6. 图论环检测（Cycle Detection in Graph Theory）

核心原理

目标：检测由线段组成的路径是否存在闭合环路。

步骤：

1. 构建图结构：将路径的端点视为节点，线段视为边。
2. 遍历图：使用深度优先搜索（DFS）或并查集（Union-Find）检查环路。
3. 环路判断：若遍历中发现已访问过的节点且非父节点，则存在环路。

典型应用场景

SVG路径闭合性检查。

地图路线是否形成闭环（如自动驾驶中的路径规划）。

Python 代码示例

手动实现DFS检测环路：

def has_cycle(graph):
    visited = set()
    
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True  # 发现环
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node, None):
                return True
    return False

# 示例：检测一个四边形的闭合性
# 图的邻接表表示，节点为路径端点
graph = {
    (0, 0): [(0, 5), (5, 0)],
    (0, 5): [(0, 0), (5, 5)],
    (5, 0): [(0, 0), (5, 5)],
    (5, 5): [(0, 5), (5, 0)]
}
print("是否存在环？", has_cycle(graph))  # 输出 True（闭合四边形）

# 示例：未闭合的路径
graph_open = {
    (0, 0): [(5, 0)],
    (5, 0): [(5, 5)],
    (5, 5): [(0, 5)],
    (0, 5): []  # 最后一个点未连接回起点
}
print("是否存在环？", has_cycle(graph_open))  # 输出 False

关键细节

并查集优化：处理大规模数据时，可用并查集（Union-Find）快速检测环。

节点标识：需确保坐标相同的端点被识别为同一节点（例如使用浮点数哈希或坐标近似匹配）。

---

2.7. 非零环绕数规则（Non-Zero Winding Number）

核心原理

目标：判断点是否在闭合区域内，考虑路径的“缠绕方向”。

步骤：

1. 计算环绕数：从点向任意方向（通常向右）发射射线，统计路径绕该点的次数。
2. 方向权重：路径顺时针穿过射线时计数+1，逆时针时-1。
3. 结果判断：若总环绕数非零，则点在内部。

典型应用场景

矢量图形填充（如SVG中复杂重叠路径的填充）。

判断点是否在由螺旋路径组成的闭合区域内。

Python 代码示例

手动实现环绕数计算：

def winding_number(point, polygon):
    x, y = point
    wn = 0  # 环绕数
    n = len(polygon)
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i+1) % n]
        # 检查边是否在点的垂直范围内
        if y1 <= y < y2 or y2 <= y < y1:
            # 计算边与水平射线的交点x坐标
            x_intersect = (y - y1) * (x2 - x1) / (y2 - y1) + x1
            # 判断交点是否在射线右侧，并确定方向
            if x_intersect > x:
                wn += 1 if (y2 - y1) > 0 else -1
    return wn != 0  # 非零则点在内部

# 示例：判断点是否在星形内部
star_polygon = [
    (50, 0), (61, 38), (100, 38), (68, 61),
    (79, 100), (50, 75), (21, 100), (32, 61),
    (0, 38), (39, 38)
]
point = (50, 50)
print("点是否在内部？", winding_number(point, star_polygon))  # 输出 True

# 对比奇偶规则（可能结果不同！）
def even_odd_rule(point, polygon):
    # 类似之前的射线法实现
    crosses = 0
    x, y = point
    n = len(polygon)
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i+1) % n]
        if ((y1 > y) != (y2 > y)):
            x_intersect = (y - y1) * (x2 - x1) / (y2 - y1) + x1
            if x < x_intersect:
                crosses += 1
    return crosses % 2 == 1

print("奇偶规则结果：", even_odd_rule(point, star_polygon))  # 可能输出 False（差异在此体现）

关键细节

方向敏感性：路径绘制方向（顺时针/逆时针）会影响结果。

与奇偶规则对比：非零环绕数更适用于复杂重叠路径（如五角星中心孔洞的填充）。

---

2.8. 数学形态学（Mathematical Morphology）

核心原理

目标：通过形态学操作（如膨胀、腐蚀、闭运算）修复不闭合的路径。

核心操作：

膨胀（Dilation）：用结构元素扩展图像中的亮区域（填充小孔或连接断裂）。

腐蚀（Erosion）：用结构元素缩小图像中的亮区域（去除细小噪声）。

闭运算（Closing）：先膨胀后腐蚀，用于闭合路径的间隙。

典型应用场景

修复手绘路径中的断裂（如签名扫描后的笔画连接）。

二值图像中的孔洞填充（如医学图像中的器官轮廓修复）。

Python 代码示例

使用 OpenCV 实现闭运算修复断裂路径：

import cv2
import numpy as np

# 生成一个带断裂的圆形路径（0为背景，255为路径）
height, width = 200, 200
image = np.zeros((height, width), dtype=np.uint8)
cv2.circle(image, (100, 100), 80, 255, 1)  # 绘制空心圆（线宽1，故意制造断裂）

# 闭运算：用圆形结构元素闭合间隙
kernel = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (5, 5))
closed_image = cv2.morphologyEx(image, cv2.MORPH_CLOSE, kernel)

# 可视化对比
cv2.imshow("Original", image)
cv2.imshow("After Closing", closed_image)
cv2.waitKey(0)

关键细节

结构元素选择：圆形适合修复任意方向的断裂，矩形适合水平/垂直断裂。

操作顺序：闭运算 = 膨胀 + 腐蚀，开运算 = 腐蚀 + 膨胀（用途相反）。

---

2.9. 包围盒分层检测（Bounding Volume Hierarchy, BVH）

核心原理

目标：通过空间划分（如四叉树）快速排除无关区域，缩小闭合区域检测范围。

步骤：

1. 构建包围盒：将整个空间划分为多个矩形区域（如四叉树递归分割）。
2. 层级检测：
3. 若点不在当前包围盒内，跳过其所有子区域。
4. 若在包围盒内，递归检测子区域。
5. 最终判断：只在最底层包围盒内精确检测闭合性。

典型应用场景

大规模图形数据中的快速碰撞检测（如游戏引擎）。

地图应用中区域查询（如“某城市内所有湖泊”）。

Python 代码示例

手动实现四叉树空间划分：

class QuadTree:
    def __init__(self, boundary, capacity=4):
        self.boundary = boundary  # 格式：(x, y, width, height)
        self.capacity = capacity  # 节点最大容量
        self.points = []          # 存储当前节点的点
        self.divided = False      # 是否已分割
        self.children = []        # 四个子节点

    def subdivide(self):
        x, y, w, h = self.boundary
        half_w, half_h = w/2, h/2
        # 创建四个子区域（NW, NE, SW, SE）
        self.children = [
            QuadTree((x, y, half_w, half_h), self.capacity),
            QuadTree((x + half_w, y, half_w, half_h), self.capacity),
            QuadTree((x, y + half_h, half_w, half_h), self.capacity),
            QuadTree((x + half_w, y + half_h, half_w, half_h), self.capacity)
        ]
        self.divided = True

    def insert(self, point):
        # 如果点不在当前包围盒内，直接返回
        if not self.in_boundary(point):
            return False
        # 若未超容量且未分割，直接添加
        if len(self.points) < self.capacity and not self.divided:
            self.points.append(point)
            return True
        # 超容量时分割并插入到子节点
        if not self.divided:
            self.subdivide()
        for child in self.children:
            if child.insert(point):
                return True
        return False

    def in_boundary(self, point):
        px, py = point
        x, y, w, h = self.boundary
        return (x <= px <= x + w) and (y <= py <= y + h)

# 示例：插入点并查询区域
qt = QuadTree((0, 0, 100, 100), capacity=4)
points = [(10, 10), (60, 60), (70, 30), (20, 80), (90, 90)]
for p in points:
    qt.insert(p)

关键细节

分割策略：通常根据点密度或包围盒大小决定是否继续分割。

性能对比：四叉树可将检测复杂度从 O(n) 降低到 O(log n)。

---

2.10. 行进方块算法（Marching Squares）

核心原理

目标：从二维标量场（如高度图、温度场）提取闭合等值线。

步骤：

1. 网格划分：将图像划分为均匀的方块（如每个方块为2×2像素）。
2. 顶点标记：根据阈值判断方块顶点的状态（高于阈值为1，否则为0）。
3. 查找模式：根据顶点状态组合（共16种），确定等值线在方块内的走向。
4. 插值连接：通过线性插值确定等值线交点，连接成闭合轮廓。

典型应用场景

等高线生成（地理信息系统、游戏地形）。

医学图像中的器官轮廓提取（如MRI数据）。

Python 代码示例

手动实现基础等值线提取：

import numpy as np
import matplotlib.pyplot as plt

def marching_squares(data, threshold):
    contours = []
    rows, cols = data.shape
    # 遍历每个2x2方块
    for i in range(rows-1):
        for j in range(cols-1):
            # 获取当前方块四个顶点的状态（0或1）
            v1 = data[i, j] >= threshold
            v2 = data[i, j+1] >= threshold
            v3 = data[i+1, j+1] >= threshold
            v4 = data[i+1, j] >= threshold
            state = (v1 << 3) | (v2 << 2) | (v3 << 1) | v4

            # 根据状态确定等值线交点（简化版，仅处理部分情况）
            if state in [1, 14]:
                # 底部和右侧交点
                x0 = j + (threshold - data[i, j]) / (data[i, j+1] - data[i, j])
                y0 = i + 0.5
                x1 = j + 0.5
                y1 = i + (threshold - data[i, j]) / (data[i+1, j] - data[i, j])
                contours.append([(x0, y0), (x1, y1)])
    return contours

# 示例：生成正弦波的等值线
x = np.linspace(0, 4*np.pi, 100)
y = np.linspace(0, 4*np.pi, 100)
X, Y = np.meshgrid(x, y)
data = np.sin(X) + np.cos(Y)
threshold = 0.0

contours = marching_squares(data, threshold)

# 可视化
plt.contour(X, Y, data, levels=[threshold], colors='red')
plt.title("Ground Truth (Matplotlib)")
plt.show()

# 绘制手动实现的等值线
fig, ax = plt.subplots()
for line in contours:
    ax.plot([line[0][0], line[1][0]], [line[0][1], line[1][1]], 'b-')
ax.set_title("Manual Marching Squares")
plt.show()

关键细节

模式表优化：完整的实现需预定义16种顶点状态对应的连接方式（可查表优化）。

插值精度：线性插值可能导致锯齿，实际应用中可结合平滑处理。

---

2.11. 主动轮廓模型（Active Contour Model）

核心原理

目标：动态调整曲线使其贴合图像中的目标边界。

能量最小化：

内部能量：控制曲线的平滑度（避免过度弯曲）。

外部能量：吸引曲线向图像梯度大的区域（边缘）移动。

迭代优化：通过梯度下降或其他优化方法更新曲线顶点。

典型应用场景

图像分割（如肿瘤检测、人脸识别）。

视频中的运动目标跟踪。

Python 代码示例

使用 scikit-image 库实现主动轮廓：

import numpy as np
import matplotlib.pyplot as plt
from skimage import color, draw
from skimage.segmentation import active_contour

# 生成测试图像（圆形）
image = np.zeros((200, 200))
rr, cc = draw.circle_perimeter(100, 100, 80)
image[rr, cc] = 1

# 初始轮廓（偏离目标的矩形）
s = np.linspace(0, 2*np.pi, 100)
init = 50 * np.array([np.sin(s), np.cos(s)]).T + 100  # 中心(100,100)

# 运行主动轮廓模型
snake = active_contour(image, init, alpha=0.1, beta=1.0, gamma=0.1)

# 可视化
fig, ax = plt.subplots()
ax.imshow(image, cmap=plt.cm.gray)
ax.plot(init[:, 1], init[:, 0], '--r', lw=2)
ax.plot(snake[:, 1], snake[:, 0], '-b', lw=2)
ax.set_title("Active Contour Result")
plt.show()

关键细节

参数调节：

alpha：控制轮廓的弹性（越大越抗拒拉伸）。

beta：控制轮廓的刚性（越大越抗拒弯曲）。

gamma：控制迭代步长（需平衡速度和稳定性）。

梯度计算：实际中需结合图像梯度（如高斯滤波后的边缘）。

---

三、Python库的填充算法

3.1 常用库与函数

库名	功能	关键函数/方法
Pillow	图像处理基础	ImageDraw.floodfill()
OpenCV	高效图像处理与计算机视觉	cv2.floodFill(), cv2.findContours()
Shapely	矢量图形操作	Polygon.contains()
scikit-image	高级图像分割	skimage.segmentation.flood()

3.2 案例：OpenCV自动填充闭合区域

import cv2
import numpy as np

# 读取图像并二值化
img = cv2.imread('shape.png', 0)
_, bin_img = cv2.threshold(img, 127, 255, cv2.THRESH_BINARY)

# 查找轮廓并填充
contours, _ = cv2.findContours(bin_img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
filled = cv2.drawContours(np.zeros_like(img), contours, -1, 255, cv2.FILLED)

cv2.imshow('Filled', filled)
cv2.waitKey(0)

---

四、填充算法选择建议

场景需求	推荐算法	理由
简单图像交互填充	洪水填充（递归/迭代）	实现简单，适合小规模数据
复杂多边形渲染	扫描线填充 + 活性边表	高效处理复杂边界的奇偶规则填充
动态图像分割	主动轮廓模型	自适应贴合目标边缘，支持交互调整
大规模性能优化	扫描线种子填充 + 四叉树加速	减少重复计算，空间剪枝提升性能

---

1. 基础填充：扫描线填充、种子填充。
2. 闭合检测：射线法、首尾相连检测、图论环检测。
3. 复杂路径处理：平面扫描算法、非零环绕数规则。
4. 图像修复与加速：数学形态学、包围盒分层检测。
5. 高级应用：行进方块算法、主动轮廓模型。

根据具体需求（如实时性、精度、输入类型）选择合适的算法组合。例如：

实时游戏地形生成：行进方块算法 + 扫描线填充。

医学图像分割：主动轮廓模型 + 数学形态学后处理。

五、总结

填充算法是图形处理的核心工具，从基础的洪水填充到高级的主动轮廓模型，不同场景需灵活选择。通过Python库（如OpenCV、Pillow）的封装，开发者能快速实现复杂功能。希望本文帮助初学者建立系统认知，在实践中逐步掌握这一关键技术！

---

六、各种闭合区域算法思维导图

作者：灏瀚星空