当前位置：首页 > news >正文

第11章：活动边表 AEL 管理

news 2026/6/2 15:35:58

第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.TopAfter (扫描线到达 e.Top):e → e.NextInLMLAEL 中 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_xyzSetZ(ref ip, ePrev, e);
#endifOutPt 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_lineselse 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);} 
#endifelse throw new ClipperException("DoMaxima error");
}

11.9 AEL 状态可视化

扫描过程示例：Y=0:─────────────────────────────────AEL: [e1, e2]╱╲╱  ╲╱    ╲e1    e2Y=50:─────────────────────────────────AEL: [e1, e3, e4, e2]╱╲╱  ╲──╱────╲──e1 e3 e4 e2Y=100:─────────────────────────────────AEL: [e1, e2]╱╲───╱──╲───e1  e2