🎨 扫描线填充算法

Scan-Line Filling Algorithm - 逐行扫描填充多边形

多边形边界

当前扫描线

交点标记

填充区域

🎮 控制面板

📍 状态：等待绘制多边形
点击画布添加顶点，右键或双击完成多边形

步骤: 0 / 0

显示网格显示交点显示边表信息

多边形顶点：
暂无顶点

📊 算法执行信息

等待开始...

💡 扫描线填充算法原理

                🔑 核心思想：

                从多边形的最低点到最高点，用水平扫描线逐行扫描，找到扫描线与多边形边的交点，交点之间两两配对填充。

算法步骤：

建立边表（ET - Edge Table）：
- 将多边形的所有边按其较低端点的y坐标分类
- 水平边不加入边表（y不变，无交点）
- 每条边记录：y_max（上端点y）、x（下端点x）、1/k（斜率倒数）
初始化活动边表（AET - Active Edge Table）：
- AET存储当前扫描线相交的边
- 初始为空
从下到上扫描：
- y = y_min 开始，每次递增1
- 将ET中y = 当前扫描线的边加入AET
- 从AET删除y_max = 当前y的边
- 对AET中的边按x坐标排序
- 交点两两配对，填充区间
- 更新AET中每条边的x值：x = x + 1/k

为什么使用边表？

效率：避免每次扫描都计算所有边的交点
增量计算：利用 x_new = x_old + 1/k，只需加法
动态维护：AET只包含当前相关的边，减少计算量

关键概念：

1/k（斜率倒数）：当y增加1时，x的增量 = Δx/Δy
奇偶规则：从左到右，奇数交点到偶数交点之间需要填充
特殊情况：顶点处理（共享顶点只算一个交点）

                ⚡ 算法优势：

                ✓ 适用于任意复杂多边形（凸、凹、有孔）

                ✓ 增量计算，效率高

                ✓ 只需整数或定点运算

                ✓ 硬件实现简单

🎓 使用说明

创建多边形：在画布上点击鼠标左键添加顶点（至少3个点）
完成多边形：右键点击或双击完成多边形绘制
填充选项：
- 开始填充：显示最终填充结果
- 动画演示：逐行演示扫描线填充过程
- 瞬间填充：快速填充整个多边形
测试案例：
- 凸多边形：三角形、矩形、五边形
- 凹多边形：L形、星形
- 复杂多边形：不规则形状