第13章：水平边处理算法
13.1 概述
水平边是 Clipper 算法中需要特殊处理的情况。由于水平边与扫描线平行，不能使用常规的扫描线方法处理。本章将深入分析 Clipper 如何处理水平边。
13.2 水平边的特殊性
13.2.1 定义
internal static bool IsHorizontal(TEdge e)
{
return e.Delta.Y == 0;
}
13.2.2 斜率标记
private void SetDx(TEdge e)
{
e.Delta.X = (e.Top.X - e.Bot.X);
e.Delta.Y = (e.Top.Y - e.Bot.Y);
if (e.Delta.Y == 0)
e.Dx = horizontal; // 特殊标记
else
e.Dx = (double)(e.Delta.X) / (e.Delta.Y);
}
13.2.3 挑战
- 扫描线与水平边重合
- 无法计算常规的扫描线交点
- 需要考虑边的方向性
13.3 SEL（Sorted Edge List）
水平边使用 SEL 进行管理：
13.3.1 AddEdgeToSEL
private void AddEdgeToSEL(TEdge edge)
{
if (m_SortedEdges == null)
{
m_SortedEdges = edge;
edge.PrevInSEL = null;
edge.NextInSEL = null;
}
else
{
edge.NextInSEL = m_SortedEdges;
edge.PrevInSEL = null;
m_SortedEdges.PrevInSEL = edge;
m_SortedEdges = edge;
}
}
13.3.2 PopEdgeFromSEL
private bool PopEdgeFromSEL(out TEdge e)
{
e = m_SortedEdges;
if (e == null) return false;
TEdge oldE = e;
m_SortedEdges = e.NextInSEL;
if (m_SortedEdges != null)
m_SortedEdges.PrevInSEL = null;
oldE.NextInSEL = null;
oldE.PrevInSEL = null;
return true;
}
13.3.3 DeleteFromSEL
private void DeleteFromSEL(TEdge e)
{
TEdge SelPrev = e.PrevInSEL;
TEdge SelNext = e.NextInSEL;
if (SelPrev == null && SelNext == null && (e != m_SortedEdges))
return;
if (SelPrev != null)
SelPrev.NextInSEL = SelNext;
else
m_SortedEdges = SelNext;
if (SelNext != null)
SelNext.PrevInSEL = SelPrev;
e.NextInSEL = null;
e.PrevInSEL = null;
}
13.4 ProcessHorizontals
处理所有待处理的水平边：
private void ProcessHorizontals()
{
TEdge horzEdge;
while (PopEdgeFromSEL(out horzEdge))
ProcessHorizontal(horzEdge);
}
13.5 ProcessHorizontal 详解
private void ProcessHorizontal(TEdge horzEdge)
{
Direction dir;
cInt horzLeft, horzRight;
bool IsOpen = horzEdge.WindDelta == 0;
GetHorzDirection(horzEdge, out dir, out horzLeft, out horzRight);
TEdge eLastHorz = horzEdge, eMaxPair = null;
// 找到连续水平边的最后一条
while (eLastHorz.NextInLML != null && IsHorizontal(eLastHorz.NextInLML))
eLastHorz = eLastHorz.NextInLML;
if (eLastHorz.NextInLML == null)
eMaxPair = GetMaximaPair(eLastHorz);
// 处理 Maxima 列表
Maxima currMax = m_Maxima;
if (currMax != null)
{
// 找到范围内的第一个 maxima
if (dir == Direction.dLeftToRight)
{
while (currMax != null && currMax.X <= horzEdge.Bot.X)
currMax = currMax.Next;
if (currMax != null && currMax.X >= eLastHorz.Top.X)
currMax = null;
}
else
{
while (currMax.Next != null && currMax.Next.X < horzEdge.Bot.X)
currMax = currMax.Next;
if (currMax.X <= eLastHorz.Top.X) currMax = null;
}
}
OutPt op1 = null;
// 主处理循环
for (;;)
{
bool IsLastHorz = (horzEdge == eLastHorz);
TEdge e = GetNextInAEL(horzEdge, dir);
while (e != null)
{
// 在水平边上插入 maxima 点
if (currMax != null)
{
if (dir == Direction.dLeftToRight)
{
while (currMax != null && currMax.X < e.Curr.X)
{
if (horzEdge.OutIdx >= 0 && !IsOpen)
AddOutPt(horzEdge, new IntPoint(currMax.X, horzEdge.Bot.Y));
currMax = currMax.Next;
}
}
else
{
while (currMax != null && currMax.X > e.Curr.X)
{
if (horzEdge.OutIdx >= 0 && !IsOpen)
AddOutPt(horzEdge, new IntPoint(currMax.X, horzEdge.Bot.Y));
currMax = currMax.Prev;
}
}
}
// 检查是否超出水平边范围
if ((dir == Direction.dLeftToRight && e.Curr.X > horzRight) ||
(dir == Direction.dRightToLeft && e.Curr.X < horzLeft))
break;
// 检查是否到达中间水平边的末端
if (e.Curr.X == horzEdge.Top.X && horzEdge.NextInLML != null &&
e.Dx < horzEdge.NextInLML.Dx)
break;
// 处理输出
if (horzEdge.OutIdx >= 0 && !IsOpen)
{
#if use_xyz
if (dir == Direction.dLeftToRight)
SetZ(ref e.Curr, horzEdge, e);
else
SetZ(ref e.Curr, e, horzEdge);
#endif
op1 = AddOutPt(horzEdge, e.Curr);
// 处理与其他水平边的连接
TEdge eNextHorz = m_SortedEdges;
while (eNextHorz != null)
{
if (eNextHorz.OutIdx >= 0 &&
HorzSegmentsOverlap(horzEdge.Bot.X, horzEdge.Top.X,
eNextHorz.Bot.X, eNextHorz.Top.X))
{
OutPt op2 = GetLastOutPt(eNextHorz);
AddJoin(op2, op1, eNextHorz.Top);
}
eNextHorz = eNextHorz.NextInSEL;
}
AddGhostJoin(op1, horzEdge.Bot);
}
// 处理最大配对边
if (e == eMaxPair && IsLastHorz)
{
if (horzEdge.OutIdx >= 0)
AddLocalMaxPoly(horzEdge, eMaxPair, horzEdge.Top);
DeleteFromAEL(horzEdge);
DeleteFromAEL(eMaxPair);
return;
}
// 处理交点
if (dir == Direction.dLeftToRight)
{
IntPoint Pt = new IntPoint(e.Curr.X, horzEdge.Curr.Y);
IntersectEdges(horzEdge, e, Pt);
}
else
{
IntPoint Pt = new IntPoint(e.Curr.X, horzEdge.Curr.Y);
IntersectEdges(e, horzEdge, Pt);
}
TEdge eNext = GetNextInAEL(e, dir);
SwapPositionsInAEL(horzEdge, e);
e = eNext;
}
// 检查是否继续到下一个水平段
if (horzEdge.NextInLML == null || !IsHorizontal(horzEdge.NextInLML))
break;
UpdateEdgeIntoAEL(ref horzEdge);
if (horzEdge.OutIdx >= 0)
AddOutPt(horzEdge, horzEdge.Bot);
GetHorzDirection(horzEdge, out dir, out horzLeft, out horzRight);
}
// 后处理
if (horzEdge.OutIdx >= 0 && op1 == null)
{
op1 = GetLastOutPt(horzEdge);
TEdge eNextHorz = m_SortedEdges;
while (eNextHorz != null)
{
if (eNextHorz.OutIdx >= 0 &&
HorzSegmentsOverlap(horzEdge.Bot.X, horzEdge.Top.X,
eNextHorz.Bot.X, eNextHorz.Top.X))
{
OutPt op2 = GetLastOutPt(eNextHorz);
AddJoin(op2, op1, eNextHorz.Top);
}
eNextHorz = eNextHorz.NextInSEL;
}
AddGhostJoin(op1, horzEdge.Top);
}
// 更新或删除水平边
if (horzEdge.NextInLML != null)
{
if (horzEdge.OutIdx >= 0)
{
op1 = AddOutPt(horzEdge, horzEdge.Top);
UpdateEdgeIntoAEL(ref horzEdge);
if (horzEdge.WindDelta == 0) return;
// 处理连接
TEdge ePrev = horzEdge.PrevInAEL;
TEdge eNext = horzEdge.NextInAEL;
if (ePrev != null && ePrev.Curr.X == horzEdge.Bot.X &&
ePrev.Curr.Y == horzEdge.Bot.Y && ePrev.WindDelta != 0 &&
(ePrev.OutIdx >= 0 && ePrev.Curr.Y > ePrev.Top.Y &&
SlopesEqual(horzEdge, ePrev, m_UseFullRange)))
{
OutPt op2 = AddOutPt(ePrev, horzEdge.Bot);
AddJoin(op1, op2, horzEdge.Top);
}
else if (eNext != null && eNext.Curr.X == horzEdge.Bot.X &&
eNext.Curr.Y == horzEdge.Bot.Y && eNext.WindDelta != 0 &&
eNext.OutIdx >= 0 && eNext.Curr.Y > eNext.Top.Y &&
SlopesEqual(horzEdge, eNext, m_UseFullRange))
{
OutPt op2 = AddOutPt(eNext, horzEdge.Bot);
AddJoin(op1, op2, horzEdge.Top);
}
}
else
UpdateEdgeIntoAEL(ref horzEdge);
}
else
{
if (horzEdge.OutIdx >= 0)
AddOutPt(horzEdge, horzEdge.Top);
DeleteFromAEL(horzEdge);
}
}
13.6 GetHorzDirection
获取水平边的方向：
void GetHorzDirection(TEdge HorzEdge, out Direction Dir, out cInt Left, out cInt Right)
{
if (HorzEdge.Bot.X < HorzEdge.Top.X)
{
Left = HorzEdge.Bot.X;
Right = HorzEdge.Top.X;
Dir = Direction.dLeftToRight;
}
else
{
Left = HorzEdge.Top.X;
Right = HorzEdge.Bot.X;
Dir = Direction.dRightToLeft;
}
}
13.7 GetNextInAEL
获取 AEL 中指定方向的下一条边：
private TEdge GetNextInAEL(TEdge e, Direction Direction)
{
return Direction == Direction.dLeftToRight ? e.NextInAEL : e.PrevInAEL;
}
13.8 水平边处理图解
水平边处理示例：
初始状态：
│ │ │ │
e1 e2 e3 e4
│ │ │ │
────────┼──────┼──────┼──────┼──── horzEdge
│ │ │ │
Left Right
处理过程（从左到右）：
1. 与 e1 交叉 → IntersectEdges(horzEdge, e1)
2. 交换位置 → e1 horzEdge e2 e3 e4
3. 与 e2 交叉 → IntersectEdges(horzEdge, e2)
4. 交换位置 → e1 e2 horzEdge e3 e4
5. 继续直到 Right
最终状态：
│ │ │ │
e1 e2 e3 e4
│ │ │ │
────────┴──────┴──────┴──────┴────
horzEdge 被删除或更新
13.9 HorzSegmentsOverlap
判断两个水平段是否重叠：
private bool HorzSegmentsOverlap(cInt seg1a, cInt seg1b, cInt seg2a, cInt seg2b)
{
if (seg1a > seg1b) Swap(ref seg1a, ref seg1b);
if (seg2a > seg2b) Swap(ref seg2a, ref seg2b);
return (seg1a < seg2b) && (seg2a < seg1b);
}
13.10 GhostJoin
幽灵连接用于标记水平边上可能需要连接的点：
private void AddGhostJoin(OutPt Op, IntPoint OffPt)
{
Join j = new Join();
j.OutPt1 = Op;
j.OffPt = OffPt;
m_GhostJoins.Add(j);
}
用途：
- 记录水平边上的输出点
- 在后续处理中用于连接重叠的水平边
13.11 水平边的方向约定
13.11.1 ReverseHorizontal
private void ReverseHorizontal(TEdge e)
{
// 交换 Bot.X 和 Top.X
Swap(ref e.Bot.X, ref e.Top.X);
#if use_xyz
Swap(ref e.Bot.Z, ref e.Top.Z);
#endif
}
13.11.2 何时需要反转
在 ProcessBound 中处理水平边时，需要确保水平边的方向与边界方向一致：
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);
}
13.12 连续水平边处理
// 找到连续水平边的最后一条
TEdge eLastHorz = horzEdge;
while (eLastHorz.NextInLML != null && IsHorizontal(eLastHorz.NextInLML))
eLastHorz = eLastHorz.NextInLML;
// 处理连续水平边
for (;;)
{
// ... 处理当前水平边 ...
// 检查是否有更多水平边
if (horzEdge.NextInLML == null || !IsHorizontal(horzEdge.NextInLML))
break;
// 更新到下一段
UpdateEdgeIntoAEL(ref horzEdge);
// ... 继续处理 ...
}
13.13 本章小结
本章详细分析了 Clipper 的水平边处理：
- 水平边特殊性：
- 与扫描线平行
- 使用特殊斜率标记
- 需要单独处理
- SEL 管理：
- 存储待处理的水平边
- 与 AEL 配合使用
- ProcessHorizontal：
- 确定处理方向
- 遍历与水平边相交的边
- 处理交点和输出
- 特殊情况：
- 连续水平边
- 水平边重叠
- 幽灵连接
水平边处理是 Clipper 算法中最复杂的部分之一。
| 上一章：交点计算与处理 | 返回目录 | 下一章：输出多边形构建 |