第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 的交点处理机制：

1. 交点检测：

   • BuildIntersectList 使用冒泡排序检测
   • 比较边在 topY 处的 X 坐标

2. 交点计算：

   • IntersectPoint 处理各种边的情况
   • 处理垂直边、水平边、一般情况

3. 交点排序：

   • 按 Y 坐标降序
   • FixupIntersectionOrder 确保边相邻

4. 交点处理：

   • IntersectEdges 更新缠绕数
   • 根据贡献状态处理输出

5. 四种情况：

   • 两边贡献：极大值或交换
   • 一边贡献：添加输出点
   • 两边不贡献：可能开始新输出

上一章：活动边表管理 | 返回目录 | 下一章：水平边处理