第11章：活动边表 AEL 管理
11.1 概述
活动边表（Active Edge List, AEL）是 Vatti 裁剪算法的核心数据结构。它存储当前扫描线穿过的所有边，并按 X 坐标排序。本章将深入分析 AEL 的管理机制。
11.2 AEL 的结构
AEL 是一个双向链表，通过 TEdge 的 NextInAEL 和 PrevInAEL 指针连接：
m_ActiveEdges
│
▼
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│ e1 │◄──►│ e2 │◄──►│ e3 │◄──►│ e4 │
└─────┘ └─────┘ └─────┘ └─────┘
X=10 X=30 X=50 X=80
按 X 坐标升序排列
11.3 InsertEdgeIntoAEL
将边插入 AEL 并保持 X 坐标排序：
private void InsertEdgeIntoAEL(TEdge edge, TEdge startEdge)
{
if (m_ActiveEdges == null)
{
// AEL 为空，直接设为头
edge.PrevInAEL = null;
edge.NextInAEL = null;
m_ActiveEdges = edge;
}
else if (startEdge == null && E2InsertsBeforeE1(m_ActiveEdges, edge))
{
// 插入到 AEL 头部
edge.PrevInAEL = null;
edge.NextInAEL = m_ActiveEdges;
m_ActiveEdges.PrevInAEL = edge;
m_ActiveEdges = edge;
}
else
{
// 找到正确位置插入
if (startEdge == null) startEdge = m_ActiveEdges;
while (startEdge.NextInAEL != null &&
!E2InsertsBeforeE1(startEdge.NextInAEL, edge))
startEdge = startEdge.NextInAEL;
edge.NextInAEL = startEdge.NextInAEL;
if (startEdge.NextInAEL != null)
startEdge.NextInAEL.PrevInAEL = edge;
edge.PrevInAEL = startEdge;
startEdge.NextInAEL = edge;
}
}
11.3.1 E2InsertsBeforeE1
判断 e2 是否应该插入到 e1 之前：
private bool E2InsertsBeforeE1(TEdge e1, TEdge e2)
{
if (e2.Curr.X == e1.Curr.X)
{
// X 相同时比较斜率
if (e2.Top.Y > e1.Top.Y)
return e2.Top.X < TopX(e1, e2.Top.Y);
else
return e1.Top.X > TopX(e2, e1.Top.Y);
}
else
return e2.Curr.X < e1.Curr.X;
}
排序规则：
- 首先按当前 X 坐标排序
- X 相同时，比较在某个高度上谁更靠左
11.4 DeleteFromAEL
从 AEL 中删除边：
internal void DeleteFromAEL(TEdge e)
{
TEdge AelPrev = e.PrevInAEL;
TEdge AelNext = e.NextInAEL;
// 检查是否已删除
if (AelPrev == null && AelNext == null && (e != m_ActiveEdges))
return;
// 更新前驱节点
if (AelPrev != null)
AelPrev.NextInAEL = AelNext;
else
m_ActiveEdges = AelNext; // e 是头节点
// 更新后继节点
if (AelNext != null)
AelNext.PrevInAEL = AelPrev;
// 清理 e 的指针
e.NextInAEL = null;
e.PrevInAEL = null;
}
11.5 SwapPositionsInAEL
交换 AEL 中两条边的位置：
internal void SwapPositionsInAEL(TEdge edge1, TEdge edge2)
{
// 检查边是否有效
if (edge1.NextInAEL == edge1.PrevInAEL ||
edge2.NextInAEL == edge2.PrevInAEL) return;
if (edge1.NextInAEL == edge2)
{
// edge1 紧跟在 edge2 前面
// ... → edge1 → edge2 → ...
// 变为
// ... → edge2 → edge1 → ...
TEdge next = edge2.NextInAEL;
if (next != null) next.PrevInAEL = edge1;
TEdge prev = edge1.PrevInAEL;
if (prev != null) prev.NextInAEL = edge2;
edge2.PrevInAEL = prev;
edge2.NextInAEL = edge1;
edge1.PrevInAEL = edge2;
edge1.NextInAEL = next;
}
else if (edge2.NextInAEL == edge1)
{
// edge2 紧跟在 edge1 前面（对称情况）
TEdge next = edge1.NextInAEL;
if (next != null) next.PrevInAEL = edge2;
TEdge prev = edge2.PrevInAEL;
if (prev != null) prev.NextInAEL = edge1;
edge1.PrevInAEL = prev;
edge1.NextInAEL = edge2;
edge2.PrevInAEL = edge1;
edge2.NextInAEL = next;
}
else
{
// 两条边不相邻
TEdge next = edge1.NextInAEL;
TEdge prev = edge1.PrevInAEL;
edge1.NextInAEL = edge2.NextInAEL;
if (edge1.NextInAEL != null)
edge1.NextInAEL.PrevInAEL = edge1;
edge1.PrevInAEL = edge2.PrevInAEL;
if (edge1.PrevInAEL != null)
edge1.PrevInAEL.NextInAEL = edge1;
edge2.NextInAEL = next;
if (edge2.NextInAEL != null)
edge2.NextInAEL.PrevInAEL = edge2;
edge2.PrevInAEL = prev;
if (edge2.PrevInAEL != null)
edge2.PrevInAEL.NextInAEL = edge2;
}
// 更新头指针
if (edge1.PrevInAEL == null) m_ActiveEdges = edge1;
else if (edge2.PrevInAEL == null) m_ActiveEdges = edge2;
}
11.5.1 交换图解
相邻交换：
Before: ... ← A → B → ...
After: ... ← B → A → ...
非相邻交换：
Before: ... ← A → ... ← B → ...
After: ... ← B → ... ← A → ...
11.6 边的更新
11.6.1 UpdateEdgeIntoAEL
当边到达转折点时更新到下一段：
internal void UpdateEdgeIntoAEL(ref TEdge e)
{
if (e.NextInLML == null)
throw new ClipperException("UpdateEdgeIntoAEL: invalid call");
TEdge AelPrev = e.PrevInAEL;
TEdge AelNext = e.NextInAEL;
// 复制状态到下一段
e.NextInLML.OutIdx = e.OutIdx;
// 更新 AEL 指针
if (AelPrev != null)
AelPrev.NextInAEL = e.NextInLML;
else
m_ActiveEdges = e.NextInLML;
if (AelNext != null)
AelNext.PrevInAEL = e.NextInLML;
// 复制更多状态
e.NextInLML.Side = e.Side;
e.NextInLML.WindDelta = e.WindDelta;
e.NextInLML.WindCnt = e.WindCnt;
e.NextInLML.WindCnt2 = e.WindCnt2;
// 切换到下一段
e = e.NextInLML;
e.Curr = e.Bot;
e.PrevInAEL = AelPrev;
e.NextInAEL = AelNext;
// 如果不是水平边，添加新的扫描线
if (!IsHorizontal(e)) InsertScanbeam(e.Top.Y);
}
11.6.2 更新图解
Before:
● e.Top
/
/ e
/
● e.Bot (= e.NextInLML.Bot)
\
\ e.NextInLML
\
● e.NextInLML.Top
After (扫描线到达 e.Top):
e → e.NextInLML
AEL 中 e 被替换为 e.NextInLML
11.7 ProcessEdgesAtTopOfScanbeam
处理到达扫描线顶部的边：
private void ProcessEdgesAtTopOfScanbeam(cInt topY)
{
TEdge e = m_ActiveEdges;
while (e != null)
{
bool IsMaximaEdge = IsMaxima(e, topY);
if (IsMaximaEdge)
{
TEdge eMaxPair = GetMaximaPairEx(e);
IsMaximaEdge = (eMaxPair == null || !IsHorizontal(eMaxPair));
}
if (IsMaximaEdge)
{
// 处理局部极大值
if (StrictlySimple) InsertMaxima(e.Top.X);
TEdge ePrev = e.PrevInAEL;
DoMaxima(e);
if (ePrev == null)
e = m_ActiveEdges;
else
e = ePrev.NextInAEL;
}
else
{
// 更新边的位置
if (IsIntermediate(e, topY) && IsHorizontal(e.NextInLML))
{
UpdateEdgeIntoAEL(ref e);
if (e.OutIdx >= 0)
AddOutPt(e, e.Bot);
AddEdgeToSEL(e);
}
else
{
e.Curr.X = TopX(e, topY);
e.Curr.Y = topY;
#if use_xyz
// 更新 Z 坐标
if (e.Top.Y == topY) e.Curr.Z = e.Top.Z;
else if (e.Bot.Y == topY) e.Curr.Z = e.Bot.Z;
else e.Curr.Z = 0;
#endif
}
// 处理 StrictlySimple 模式下的接触点
if (StrictlySimple)
{
TEdge ePrev = e.PrevInAEL;
if ((e.OutIdx >= 0) && (e.WindDelta != 0) && ePrev != null &&
(ePrev.OutIdx >= 0) && (ePrev.Curr.X == e.Curr.X) &&
(ePrev.WindDelta != 0))
{
IntPoint ip = new IntPoint(e.Curr);
#if use_xyz
SetZ(ref ip, ePrev, e);
#endif
OutPt op = AddOutPt(ePrev, ip);
OutPt op2 = AddOutPt(e, ip);
AddJoin(op, op2, ip);
}
}
e = e.NextInAEL;
}
}
// 处理水平边
ProcessHorizontals();
m_Maxima = null;
// 处理中间顶点
e = m_ActiveEdges;
while (e != null)
{
if (IsIntermediate(e, topY))
{
OutPt op = null;
if (e.OutIdx >= 0)
op = AddOutPt(e, e.Top);
UpdateEdgeIntoAEL(ref e);
// 处理共边连接
TEdge ePrev = e.PrevInAEL;
TEdge eNext = e.NextInAEL;
if (ePrev != null && ePrev.Curr.X == e.Bot.X &&
ePrev.Curr.Y == e.Bot.Y && op != null &&
ePrev.OutIdx >= 0 && ePrev.Curr.Y > ePrev.Top.Y &&
SlopesEqual(e.Curr, e.Top, ePrev.Curr, ePrev.Top, m_UseFullRange) &&
(e.WindDelta != 0) && (ePrev.WindDelta != 0))
{
OutPt op2 = AddOutPt(ePrev, e.Bot);
AddJoin(op, op2, e.Top);
}
else if (eNext != null && eNext.Curr.X == e.Bot.X &&
eNext.Curr.Y == e.Bot.Y && op != null &&
eNext.OutIdx >= 0 && eNext.Curr.Y > eNext.Top.Y &&
SlopesEqual(e.Curr, e.Top, eNext.Curr, eNext.Top, m_UseFullRange) &&
(e.WindDelta != 0) && (eNext.WindDelta != 0))
{
OutPt op2 = AddOutPt(eNext, e.Bot);
AddJoin(op, op2, e.Top);
}
}
e = e.NextInAEL;
}
}
11.7.1 IsMaxima
private bool IsMaxima(TEdge e, double Y)
{
return (e != null && e.Top.Y == Y && e.NextInLML == null);
}
条件：边的顶点在当前扫描线且没有后续段。
11.7.2 IsIntermediate
private bool IsIntermediate(TEdge e, double Y)
{
return (e.Top.Y == Y && e.NextInLML != null);
}
条件：边的顶点在当前扫描线且有后续段。
11.8 DoMaxima
处理局部极大值：
private void DoMaxima(TEdge e)
{
TEdge eMaxPair = GetMaximaPairEx(e);
if (eMaxPair == null)
{
// 没有配对边（开放路径）
if (e.OutIdx >= 0)
AddOutPt(e, e.Top);
DeleteFromAEL(e);
return;
}
TEdge eNext = e.NextInAEL;
// 处理 e 和 eMaxPair 之间的边
while (eNext != null && eNext != eMaxPair)
{
IntersectEdges(e, eNext, e.Top);
SwapPositionsInAEL(e, eNext);
eNext = e.NextInAEL;
}
if (e.OutIdx == Unassigned && eMaxPair.OutIdx == Unassigned)
{
// 两条边都没有输出
DeleteFromAEL(e);
DeleteFromAEL(eMaxPair);
}
else if (e.OutIdx >= 0 && eMaxPair.OutIdx >= 0)
{
// 两条边都有输出
if (e.OutIdx >= 0)
AddLocalMaxPoly(e, eMaxPair, e.Top);
DeleteFromAEL(e);
DeleteFromAEL(eMaxPair);
}
#if use_lines
else if (e.WindDelta == 0)
{
// 开放路径
if (e.OutIdx >= 0)
{
AddOutPt(e, e.Top);
e.OutIdx = Unassigned;
}
DeleteFromAEL(e);
if (eMaxPair.OutIdx >= 0)
{
AddOutPt(eMaxPair, e.Top);
eMaxPair.OutIdx = Unassigned;
}
DeleteFromAEL(eMaxPair);
}
#endif
else
throw new ClipperException("DoMaxima error");
}
11.9 AEL 状态可视化
扫描过程示例：
Y=0:
─────────────────────────────────
AEL: [e1, e2]
╱╲
╱ ╲
╱ ╲
e1 e2
Y=50:
─────────────────────────────────
AEL: [e1, e3, e4, e2]
╱╲
╱ ╲
──╱────╲──
e1 e3 e4 e2
Y=100:
─────────────────────────────────
AEL: [e1, e2]
╱╲
───╱──╲───
e1 e2
11.10 本章小结
本章详细分析了 AEL 的管理机制：
-
数据结构：双向链表，按 X 坐标排序
- 基本操作：
- InsertEdgeIntoAEL：插入边
- DeleteFromAEL：删除边
- SwapPositionsInAEL：交换位置
- 边更新：
- UpdateEdgeIntoAEL：边转折时更新
- ProcessEdgesAtTopOfScanbeam：处理顶部事件
- 极值处理：
- IsMaxima/IsIntermediate：判断边类型
- DoMaxima：处理局部极大值
AEL 是 Clipper 算法的核心，正确维护 AEL 是算法正确性的关键。
| 上一章：布尔运算执行流程 | 返回目录 | 下一章：交点计算与处理 |