第8章：局部极小值与扫描线机制
8.1 概述
Vatti 裁剪算法的核心思想是使用自底向上的扫描线来处理多边形。本章将深入分析 Clipper 如何识别局部极小值、管理扫描线，以及这些机制如何驱动整个裁剪过程。
8.2 局部极小值的定义
8.2.1 几何定义
局部极小值（Local Minimum）：多边形轮廓上的一个顶点，其 Y 坐标小于相邻两个顶点的 Y 坐标（在 Y 轴向上的坐标系中，这是局部最低点）。
● ●/ \ / \/ \ / \/ \ / \/ ●─● \/ 极小值点 \● ●极小值点 极小值点
8.2.2 LocalMinima 结构
internal class LocalMinima
{internal cInt Y; // 极小值点的 Y 坐标internal TEdge LeftBound; // 左边界（向左上方延伸的边）internal TEdge RightBound; // 右边界（向右上方延伸的边）internal LocalMinima Next; // 下一个局部极小值（链表）
}
8.2.3 左右边界的确定
// 在 AddPath 中确定左右边界
if (E.Dx < E.Prev.Dx)
{locMin.LeftBound = E.Prev;locMin.RightBound = E;leftBoundIsForward = false;
}
else
{locMin.LeftBound = E;locMin.RightBound = E.Prev;leftBoundIsForward = true;
}
判断规则：比较两条边的斜率（Dx），斜率较小的边作为右边界。
情况1: E.Dx < E.Prev.DxPrev (左边界)╲╲ E (右边界，斜率更小)╲ ╱● 极小值点情况2: E.Dx >= E.Prev.DxE (左边界)╱╱ Prev (右边界)╱ ╲● 极小值点
8.3 FindNextLocMin 方法
查找下一个局部极小值：
private TEdge FindNextLocMin(TEdge E)
{TEdge E2;for (;;){// 找到一个下降后上升的转折点while (E.Bot != E.Prev.Bot || E.Curr == E.Top) E = E.Next;// 处理水平边if (E.Dx != horizontal && E.Prev.Dx != horizontal) break;while (E.Prev.Dx == horizontal) E = E.Prev;E2 = E;while (E.Dx == horizontal) E = E.Next;// 检查是否是中间水平段if (E.Top.Y == E.Prev.Bot.Y) continue;// 选择正确的起始点if (E2.Prev.Bot.X < E.Bot.X) E = E2;break;}return E;
}
8.3.1 算法图解
步骤1: 跳过上升的边●╱╱ ← 跳过╱
●步骤2: 识别下降转上升的转折●╱ ╲╱ ╲● ● ← 找到转折点╲ ╱●─●步骤3: 处理水平边的特殊情况● ●╲ ╱●─────● ← 水平段极小值区域
8.4 ProcessBound 方法
处理从局部极小值延伸的边界：
private TEdge ProcessBound(TEdge E, bool LeftBoundIsForward)
{TEdge EStart, Result = E;TEdge Horz;// 处理标记为 Skip 的边if (Result.OutIdx == Skip){// ... 创建额外的局部极小值 ...}// 处理水平边if (E.Dx == horizontal){// 确定水平边的方向if (LeftBoundIsForward) EStart = E.Prev;else EStart = E.Next;if (EStart.Dx == horizontal){// 可能需要反转水平边if (EStart.Bot.X != E.Bot.X && EStart.Top.X != E.Bot.X)ReverseHorizontal(E);}else if (EStart.Bot.X != E.Bot.X)ReverseHorizontal(E);}// 向上遍历边界EStart = E;if (LeftBoundIsForward){// 向上沿 Next 方向while (Result.Top.Y == Result.Next.Bot.Y && Result.Next.OutIdx != Skip)Result = Result.Next;// 处理水平连接if (Result.Dx == horizontal && Result.Next.OutIdx != Skip){// ... 处理顶部水平边 ...}// 设置 NextInLML 链接while (E != Result){E.NextInLML = E.Next;if (E.Dx == horizontal && E != EStart && E.Bot.X != E.Prev.Top.X) ReverseHorizontal(E);E = E.Next;}Result = Result.Next;}else{// 向上沿 Prev 方向（逻辑类似）// ...}return Result;
}
8.4.1 NextInLML 的构建
从局部极小值向上遍历，构建 NextInLML 链：局部极小值 LM├── LeftBound: e1 → e2 → e3 (NextInLML 链)└── RightBound: e4 → e5 → e6 (NextInLML 链)e3 e6│ │e2 e5╲ ╱e1-e4LM
8.5 InsertLocalMinima 方法
将局部极小值插入到有序链表：
private void InsertLocalMinima(LocalMinima newLm)
{if (m_MinimaList == null){m_MinimaList = newLm;}else if (newLm.Y >= m_MinimaList.Y){// 插入到头部newLm.Next = m_MinimaList;m_MinimaList = newLm;} else{// 找到正确位置插入LocalMinima tmpLm = m_MinimaList;while (tmpLm.Next != null && (newLm.Y < tmpLm.Next.Y))tmpLm = tmpLm.Next;newLm.Next = tmpLm.Next;tmpLm.Next = newLm;}
}
排序规则：按 Y 坐标降序（Y 最大的在前）。
链表结构（按 Y 降序）：
m_MinimaList → LM(Y=100) → LM(Y=50) → LM(Y=0) → null这样扫描从 Y=0 开始向上时，
可以按顺序遇到 LM(Y=0) → LM(Y=50) → LM(Y=100)
8.6 扫描线管理
8.6.1 Scanbeam 结构
internal class Scanbeam
{internal cInt Y; // 扫描线 Y 坐标internal Scanbeam Next; // 下一个扫描线
}
8.6.2 InsertScanbeam
internal void InsertScanbeam(cInt Y)
{if (m_Scanbeam == null){m_Scanbeam = new Scanbeam();m_Scanbeam.Next = null;m_Scanbeam.Y = Y;}else if (Y > m_Scanbeam.Y){// 插入到头部Scanbeam newSb = new Scanbeam();newSb.Y = Y;newSb.Next = m_Scanbeam;m_Scanbeam = newSb;}else{// 找位置插入，忽略重复Scanbeam sb2 = m_Scanbeam;while (sb2.Next != null && (Y <= sb2.Next.Y)) sb2 = sb2.Next;if (Y == sb2.Y) return; // 忽略重复Scanbeam newSb = new Scanbeam();newSb.Y = Y;newSb.Next = sb2.Next;sb2.Next = newSb;}
}
8.6.3 PopScanbeam
internal Boolean PopScanbeam(out cInt Y)
{if (m_Scanbeam == null){Y = 0;return false;}Y = m_Scanbeam.Y;m_Scanbeam = m_Scanbeam.Next;return true;
}
8.6.4 扫描线事件
扫描线 Y 坐标来自以下事件：
- 局部极小值：边开始参与
- 局部极大值：边结束
- 边的转折点：边的 Top 到达
- 交点：（在处理过程中动态添加）
Y
↑
80 ─────── 局部极大值
70 ─────── 交点
60 ─────── 边转折点
40 ─────── 交点
20 ─────── 局部极小值
0 ─────── 局部极小值
8.7 扫描线处理循环
主处理循环在 ExecuteInternal 中：
private bool ExecuteInternal()
{Reset();m_SortedEdges = null;m_Maxima = null;cInt botY, topY;if (!PopScanbeam(out botY)) return false;// 插入初始局部极小值InsertLocalMinimaIntoAEL(botY);// 主循环while (PopScanbeam(out topY) || LocalMinimaPending()){// 处理水平边ProcessHorizontals();m_GhostJoins.Clear();// 处理交点if (!ProcessIntersections(topY)) return false;// 处理扫描线顶部的边ProcessEdgesAtTopOfScanbeam(topY);botY = topY;// 插入新的局部极小值InsertLocalMinimaIntoAEL(botY);}// 后处理：方向修正、连接处理等// ...return true;
}
8.7.1 处理流程图
开始│▼
PopScanbeam(botY)│▼
InsertLocalMinimaIntoAEL(botY)│▼
┌─────────────────────────────────┐
│ while (PopScanbeam || Pending) │
│ │ │
│ ├─► ProcessHorizontals() │
│ │ │
│ ├─► ProcessIntersections() │
│ │ │
│ ├─► ProcessEdgesAtTopOfScanbeam│
│ │ │
│ └─► InsertLocalMinimaIntoAEL │
│ │
└─────────────────────────────────┘│▼
后处理│▼
完成
8.8 InsertLocalMinimaIntoAEL
将当前扫描线上的局部极小值的边插入活动边表：
private void InsertLocalMinimaIntoAEL(cInt botY)
{LocalMinima lm;while (PopLocalMinima(botY, out lm)){TEdge lb = lm.LeftBound;TEdge rb = lm.RightBound;OutPt Op1 = null;if (lb == null){// 只有右边界InsertEdgeIntoAEL(rb, null);SetWindingCount(rb);if (IsContributing(rb))Op1 = AddOutPt(rb, rb.Bot);}else if (rb == null){// 只有左边界InsertEdgeIntoAEL(lb, null);SetWindingCount(lb);if (IsContributing(lb))Op1 = AddOutPt(lb, lb.Bot);InsertScanbeam(lb.Top.Y);}else{// 两个边界都存在InsertEdgeIntoAEL(lb, null);InsertEdgeIntoAEL(rb, lb);SetWindingCount(lb);rb.WindCnt = lb.WindCnt;rb.WindCnt2 = lb.WindCnt2;if (IsContributing(lb))Op1 = AddLocalMinPoly(lb, rb, lb.Bot);InsertScanbeam(lb.Top.Y);}// 处理右边界if (rb != null){if (IsHorizontal(rb)){if (rb.NextInLML != null)InsertScanbeam(rb.NextInLML.Top.Y);AddEdgeToSEL(rb);}elseInsertScanbeam(rb.Top.Y);}// 处理边之间的交叉if (lb == null || rb == null) continue;// ... 处理连接点 ...}
}
8.9 局部极小值的类型
8.9.1 V 形极小值
╱╲╱ ╲╱ ╲● ●LeftBound RightBound
两个边界都存在，形成 V 形。
8.9.2 单边极小值（开放路径）
│││●单边界（开放路径的端点）
只有一个边界，另一个为 null。
8.9.3 水平极小值
╲ ╱╲ ╱●──●水平段
极小值点连接一个或多个水平边。
8.10 LocalMinimaPending
internal Boolean LocalMinimaPending()
{return (m_CurrentLM != null);
}
检查是否还有未处理的局部极小值。
8.11 本章小结
本章深入分析了 Clipper 的局部极小值和扫描线机制：
-
局部极小值：
- 多边形轮廓上的最低点
- 作为边进入活动边表的入口
- LocalMinima 结构包含左右边界
-
边界处理：
- ProcessBound 构建 NextInLML 链
- 正确处理水平边
- 确定左右边界
-
扫描线管理：
- InsertScanbeam 维护有序扫描线列表
- PopScanbeam 获取下一个扫描位置
- 扫描线来自多种事件
-
主循环：
- 从底部向上扫描
- 在每个扫描线处理边的插入、交点、移除
- InsertLocalMinimaIntoAEL 将边加入活动边表
理解这些机制是理解 Clipper 裁剪算法的关键基础。
上一章：TEdge边缘结构 | 返回目录 | 下一章：Clipper类结构