第12章：交点计算与处理
12.1 概述
在扫描线向上移动过程中，AEL 中相邻的边可能会交叉。正确计算和处理这些交点是 Clipper 算法的关键部分。本章将深入分析交点的计算、排序和处理机制。
12.2 IntersectNode 结构
public class IntersectNode
{
internal TEdge Edge1; // 参与交点的第一条边
internal TEdge Edge2; // 参与交点的第二条边
internal IntPoint Pt; // 交点坐标
}
12.3 ProcessIntersections 主方法
private bool ProcessIntersections(cInt topY)
{
if (m_ActiveEdges == null) return true;
try
{
BuildIntersectList(topY);
if (m_IntersectList.Count == 0) return true;
if (m_IntersectList.Count == 1 || FixupIntersectionOrder())
ProcessIntersectList();
else
return false;
}
catch
{
m_SortedEdges = null;
m_IntersectList.Clear();
throw new ClipperException("ProcessIntersections error");
}
m_SortedEdges = null;
return true;
}
12.3.1 处理流程
ProcessIntersections(topY)
│
▼
BuildIntersectList(topY)
│
▼
交点列表是否为空？
│
是 │ 否
───────┴───────
│ │
▼ ▼
返回true FixupIntersectionOrder()
│
▼
ProcessIntersectList()
│
▼
返回 true
12.4 BuildIntersectList
构建交点列表：
private void BuildIntersectList(cInt topY)
{
if (m_ActiveEdges == null) return;
// 准备排序：复制 AEL 到 SEL
TEdge e = m_ActiveEdges;
m_SortedEdges = e;
while (e != null)
{
e.PrevInSEL = e.PrevInAEL;
e.NextInSEL = e.NextInAEL;
e.Curr.X = TopX(e, topY); // 计算在 topY 处的 X 坐标
e = e.NextInAEL;
}
// 冒泡排序检测交点
bool isModified = true;
while (isModified && m_SortedEdges != null)
{
isModified = false;
e = m_SortedEdges;
while (e.NextInSEL != null)
{
TEdge eNext = e.NextInSEL;
IntPoint pt;
if (e.Curr.X > eNext.Curr.X)
{
// e 和 eNext 在 topY 处交叉了
IntersectPoint(e, eNext, out pt);
// 确保交点在有效范围内
if (pt.Y < topY)
pt = new IntPoint(TopX(e, topY), topY);
// 创建交点节点
IntersectNode newNode = new IntersectNode();
newNode.Edge1 = e;
newNode.Edge2 = eNext;
newNode.Pt = pt;
m_IntersectList.Add(newNode);
// 交换位置
SwapPositionsInSEL(e, eNext);
isModified = true;
}
else
e = eNext;
}
if (e.PrevInSEL != null)
e.PrevInSEL.NextInSEL = null;
else
break;
}
m_SortedEdges = null;
}
12.4.1 冒泡排序检测交点
初始 AEL/SEL（按 botY 的 X 排序）：
e1(X=10) → e2(X=30) → e3(X=50) → e4(X=70)
在 topY 处的 X 坐标：
e1(X=40) → e2(X=20) → e3(X=60) → e4(X=45)
排序过程（冒泡）：
Pass 1: e1 > e2? 40 > 20 → 是，交换并记录交点
e2(X=20) → e1(X=40) → e3(X=60) → e4(X=45)
e1 > e3? 40 > 60 → 否
e3 > e4? 60 > 45 → 是，交换并记录交点
e2(X=20) → e1(X=40) → e4(X=45) → e3(X=60)
Pass 2: e2 > e1? 20 > 40 → 否
e1 > e4? 40 > 45 → 否
完成
交点列表：
- (e1, e2) 交点
- (e3, e4) 交点
12.5 IntersectPoint
计算两条边的交点：
private void IntersectPoint(TEdge edge1, TEdge edge2, out IntPoint ip)
{
ip = new IntPoint();
double b1, b2;
// 斜率相同的边（平行或重合）
if (edge1.Dx == edge2.Dx)
{
ip.Y = edge1.Curr.Y;
ip.X = TopX(edge1, ip.Y);
return;
}
// edge1 垂直
if (edge1.Delta.X == 0)
{
ip.X = edge1.Bot.X;
if (IsHorizontal(edge2))
{
ip.Y = edge2.Bot.Y;
}
else
{
b2 = edge2.Bot.Y - (edge2.Bot.X / edge2.Dx);
ip.Y = Round(ip.X / edge2.Dx + b2);
}
}
// edge2 垂直
else if (edge2.Delta.X == 0)
{
ip.X = edge2.Bot.X;
if (IsHorizontal(edge1))
{
ip.Y = edge1.Bot.Y;
}
else
{
b1 = edge1.Bot.Y - (edge1.Bot.X / edge1.Dx);
ip.Y = Round(ip.X / edge1.Dx + b1);
}
}
// 一般情况
else
{
b1 = edge1.Bot.X - edge1.Bot.Y * edge1.Dx;
b2 = edge2.Bot.X - edge2.Bot.Y * edge2.Dx;
double q = (b2 - b1) / (edge1.Dx - edge2.Dx);
ip.Y = Round(q);
if (Math.Abs(edge1.Dx) < Math.Abs(edge2.Dx))
ip.X = Round(edge1.Dx * q + b1);
else
ip.X = Round(edge2.Dx * q + b2);
}
// 确保交点在两条边的有效范围内
if (ip.Y < edge1.Top.Y || ip.Y < edge2.Top.Y)
{
if (edge1.Top.Y > edge2.Top.Y)
ip.Y = edge1.Top.Y;
else
ip.Y = edge2.Top.Y;
if (Math.Abs(edge1.Dx) < Math.Abs(edge2.Dx))
ip.X = TopX(edge1, ip.Y);
else
ip.X = TopX(edge2, ip.Y);
}
// 确保交点不低于当前扫描线
if (ip.Y > edge1.Curr.Y)
{
ip.Y = edge1.Curr.Y;
if (Math.Abs(edge1.Dx) > Math.Abs(edge2.Dx))
ip.X = TopX(edge2, ip.Y);
else
ip.X = TopX(edge1, ip.Y);
}
}
12.5.1 数学原理
两条非平行直线的交点计算：
线1: y = (x - b1) / Dx1 → x = Dx1 * y + b1
线2: y = (x - b2) / Dx2 → x = Dx2 * y + b2
交点:
Dx1 * y + b1 = Dx2 * y + b2
(Dx1 - Dx2) * y = b2 - b1
y = (b2 - b1) / (Dx1 - Dx2)
其中 b = Bot.X - Bot.Y * Dx
12.6 FixupIntersectionOrder
修正交点顺序以确保边是相邻的：
private bool FixupIntersectionOrder()
{
// 前提：交点按 Y 降序排列（最底部的在前）
m_IntersectList.Sort(m_IntersectNodeComparer);
CopyAELToSEL();
int cnt = m_IntersectList.Count;
for (int i = 0; i < cnt; i++)
{
if (!EdgesAdjacent(m_IntersectList[i]))
{
// 交点的边不相邻，需要调整顺序
int j = i + 1;
while (j < cnt && !EdgesAdjacent(m_IntersectList[j]))
j++;
if (j == cnt) return false;
// 交换位置
IntersectNode tmp = m_IntersectList[i];
m_IntersectList[i] = m_IntersectList[j];
m_IntersectList[j] = tmp;
}
SwapPositionsInSEL(m_IntersectList[i].Edge1, m_IntersectList[i].Edge2);
}
return true;
}
12.6.1 EdgesAdjacent
private bool EdgesAdjacent(IntersectNode inode)
{
return (inode.Edge1.NextInSEL == inode.Edge2) ||
(inode.Edge1.PrevInSEL == inode.Edge2);
}
12.6.2 IntersectNodeSort
private static int IntersectNodeSort(IntersectNode node1, IntersectNode node2)
{
// 按 Y 降序排列（先处理较低的交点）
return (int)(node2.Pt.Y - node1.Pt.Y);
}
12.7 ProcessIntersectList
处理所有交点：
private void ProcessIntersectList()
{
for (int i = 0; i < m_IntersectList.Count; i++)
{
IntersectNode iNode = m_IntersectList[i];
{
IntersectEdges(iNode.Edge1, iNode.Edge2, iNode.Pt);
SwapPositionsInAEL(iNode.Edge1, iNode.Edge2);
}
}
m_IntersectList.Clear();
}
12.7.1 处理单个交点
Before:
扫描线 ─────────────────────────
│ │
e1 e2
\ /
\ /
\ /
\ /
× ← 交点
After:
│ │
e2 e1 ← AEL 中交换了位置
/ \
/ \
12.8 IntersectEdges
处理两条边的交点（核心方法）：
private void IntersectEdges(TEdge e1, TEdge e2, IntPoint pt)
{
bool e1Contributing = (e1.OutIdx >= 0);
bool e2Contributing = (e2.OutIdx >= 0);
#if use_xyz
SetZ(ref pt, e1, e2);
#endif
#if use_lines
// 开放路径的交点处理
if (e1.WindDelta == 0 || e2.WindDelta == 0)
{
// ... 开放路径处理逻辑 ...
return;
}
#endif
// 更新缠绕数
if (e1.PolyTyp == e2.PolyTyp)
{
// 同类型多边形的边交叉
if (IsEvenOddFillType(e1))
{
int oldE1WindCnt = e1.WindCnt;
e1.WindCnt = e2.WindCnt;
e2.WindCnt = oldE1WindCnt;
}
else
{
if (e1.WindCnt + e2.WindDelta == 0)
e1.WindCnt = -e1.WindCnt;
else
e1.WindCnt += e2.WindDelta;
if (e2.WindCnt - e1.WindDelta == 0)
e2.WindCnt = -e2.WindCnt;
else
e2.WindCnt -= e1.WindDelta;
}
}
else
{
// 不同类型多边形的边交叉
if (!IsEvenOddFillType(e2))
e1.WindCnt2 += e2.WindDelta;
else
e1.WindCnt2 = (e1.WindCnt2 == 0) ? 1 : 0;
if (!IsEvenOddFillType(e1))
e2.WindCnt2 -= e1.WindDelta;
else
e2.WindCnt2 = (e2.WindCnt2 == 0) ? 1 : 0;
}
// 确定填充类型
PolyFillType e1FillType, e2FillType, e1FillType2, e2FillType2;
// ... 设置填充类型 ...
// 计算有效的缠绕计数
int e1Wc, e2Wc;
switch (e1FillType)
{
case PolyFillType.pftPositive: e1Wc = e1.WindCnt; break;
case PolyFillType.pftNegative: e1Wc = -e1.WindCnt; break;
default: e1Wc = Math.Abs(e1.WindCnt); break;
}
switch (e2FillType)
{
case PolyFillType.pftPositive: e2Wc = e2.WindCnt; break;
case PolyFillType.pftNegative: e2Wc = -e2.WindCnt; break;
default: e2Wc = Math.Abs(e2.WindCnt); break;
}
// 处理输出多边形
if (e1Contributing && e2Contributing)
{
if ((e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) ||
(e1.PolyTyp != e2.PolyTyp && m_ClipType != ClipType.ctXor))
{
AddLocalMaxPoly(e1, e2, pt);
}
else
{
AddOutPt(e1, pt);
AddOutPt(e2, pt);
SwapSides(e1, e2);
SwapPolyIndexes(e1, e2);
}
}
else if (e1Contributing)
{
if (e2Wc == 0 || e2Wc == 1)
{
AddOutPt(e1, pt);
SwapSides(e1, e2);
SwapPolyIndexes(e1, e2);
}
}
else if (e2Contributing)
{
if (e1Wc == 0 || e1Wc == 1)
{
AddOutPt(e2, pt);
SwapSides(e1, e2);
SwapPolyIndexes(e1, e2);
}
}
else if ((e1Wc == 0 || e1Wc == 1) && (e2Wc == 0 || e2Wc == 1))
{
// 两条边都不在贡献中，可能开始新的输出
cInt e1Wc2, e2Wc2;
// ... 计算 WindCnt2 ...
if (e1.PolyTyp != e2.PolyTyp)
{
AddLocalMinPoly(e1, e2, pt);
}
else if (e1Wc == 1 && e2Wc == 1)
{
switch (m_ClipType)
{
case ClipType.ctIntersection:
if (e1Wc2 > 0 && e2Wc2 > 0)
AddLocalMinPoly(e1, e2, pt);
break;
case ClipType.ctUnion:
if (e1Wc2 <= 0 && e2Wc2 <= 0)
AddLocalMinPoly(e1, e2, pt);
break;
case ClipType.ctDifference:
if (((e1.PolyTyp == PolyType.ptClip) && (e1Wc2 > 0) && (e2Wc2 > 0)) ||
((e1.PolyTyp == PolyType.ptSubject) && (e1Wc2 <= 0) && (e2Wc2 <= 0)))
AddLocalMinPoly(e1, e2, pt);
break;
case ClipType.ctXor:
AddLocalMinPoly(e1, e2, pt);
break;
}
}
else
SwapSides(e1, e2);
}
}
12.9 交点处理的四种情况
12.9.1 两边都在贡献
情况1: 形成局部极大值
╲ ╱
╲ ╱
╲╱ ← 交点（结束输出）
╱╲
╱ ╲
情况2: 边交换继续贡献
╲ ╱
╲ ╱
× ← 交点（交换边，继续）
╱ ╲
╱ ╲
12.9.2 一边在贡献
╲ │
╲ │
× ← 交点（输出点添加到贡献边）
╱ │
╱ │
12.9.3 两边都不在贡献
│ │
│ │
× ← 交点（可能开始新输出）
│ │
│ │
12.10 SwapSides 和 SwapPolyIndexes
private static void SwapSides(TEdge edge1, TEdge edge2)
{
EdgeSide side = edge1.Side;
edge1.Side = edge2.Side;
edge2.Side = side;
}
private static void SwapPolyIndexes(TEdge edge1, TEdge edge2)
{
int outIdx = edge1.OutIdx;
edge1.OutIdx = edge2.OutIdx;
edge2.OutIdx = outIdx;
}
12.11 本章小结
本章详细分析了 Clipper 的交点处理机制：
- 交点检测：
- BuildIntersectList 使用冒泡排序检测
- 比较边在 topY 处的 X 坐标
- 交点计算：
- IntersectPoint 处理各种边的情况
- 处理垂直边、水平边、一般情况
- 交点排序：
- 按 Y 坐标降序
- FixupIntersectionOrder 确保边相邻
- 交点处理：
- IntersectEdges 更新缠绕数
- 根据贡献状态处理输出
- 四种情况：
- 两边贡献：极大值或交换
- 一边贡献：添加输出点
- 两边不贡献：可能开始新输出
| 上一章：活动边表管理 | 返回目录 | 下一章：水平边处理 |