第8章：局部极小值与扫描线机制

8.1 概述

Vatti 裁剪算法的核心思想是使用自底向上的扫描线来处理多边形。本章将深入分析 Clipper 如何识别局部极小值、管理扫描线，以及这些机制如何驱动整个裁剪过程。

8.2 局部极小值的定义

8.2.1 几何定义

局部极小值（Local Minimum）：多边形轮廓上的一个顶点，其 Y 坐标小于相邻两个顶点的 Y 坐标（在 Y 轴向上的坐标系中，这是局部最低点）。

        ●         ●
       / \       / \
      /   \     /   \
     /     \   /     \
    /       ●─●       \
   /    极小值点       \
  ●                     ●
 极小值点             极小值点

8.2.2 LocalMinima 结构

internal class LocalMinima
{
    internal cInt Y;              // 极小值点的 Y 坐标
    internal TEdge LeftBound;     // 左边界（向左上方延伸的边）
    internal TEdge RightBound;    // 右边界（向右上方延伸的边）
    internal LocalMinima Next;    // 下一个局部极小值（链表）
}

8.2.3 左右边界的确定

// 在 AddPath 中确定左右边界
if (E.Dx < E.Prev.Dx) 
{
    locMin.LeftBound = E.Prev;
    locMin.RightBound = E;
    leftBoundIsForward = false;
} 
else
{
    locMin.LeftBound = E;
    locMin.RightBound = E.Prev;
    leftBoundIsForward = true;
}

判断规则：比较两条边的斜率（Dx），斜率较小的边作为右边界。

情况1: E.Dx < E.Prev.Dx
       Prev (左边界)
           ╲
            ╲   E (右边界，斜率更小)
             ╲ ╱
              ●  极小值点

情况2: E.Dx >= E.Prev.Dx
       E (左边界)
           ╱
          ╱   Prev (右边界)
         ╱ ╲
        ●    极小值点

8.3 FindNextLocMin 方法

查找下一个局部极小值：

private TEdge FindNextLocMin(TEdge E)
{
    TEdge E2;
    for (;;)
    {
        // 找到一个下降后上升的转折点
        while (E.Bot != E.Prev.Bot || E.Curr == E.Top) 
            E = E.Next;
        
        // 处理水平边
        if (E.Dx != horizontal && E.Prev.Dx != horizontal) 
            break;
        
        while (E.Prev.Dx == horizontal) 
            E = E.Prev;
        E2 = E;
        while (E.Dx == horizontal) 
            E = E.Next;
        
        // 检查是否是中间水平段
        if (E.Top.Y == E.Prev.Bot.Y) 
            continue;
        
        // 选择正确的起始点
        if (E2.Prev.Bot.X < E.Bot.X) 
            E = E2;
        break;
    }
    return E;
}

8.3.1 算法图解

步骤1: 跳过上升的边
    ●
   ╱
  ╱   ← 跳过
 ╱
●

步骤2: 识别下降转上升的转折
      ●
     ╱ ╲
    ╱   ╲
   ●     ● ← 找到转折点
    ╲   ╱
     ●─●

步骤3: 处理水平边的特殊情况
   ●         ●
    ╲       ╱
     ●─────●  ← 水平段
      极小值区域

8.4 ProcessBound 方法

处理从局部极小值延伸的边界：

private TEdge ProcessBound(TEdge E, bool LeftBoundIsForward)
{
    TEdge EStart, Result = E;
    TEdge Horz;

    // 处理标记为 Skip 的边
    if (Result.OutIdx == Skip)
    {
        // ... 创建额外的局部极小值 ...
    }

    // 处理水平边
    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);
    }

    // 向上遍历边界
    EStart = E;
    if (LeftBoundIsForward)
    {
        // 向上沿 Next 方向
        while (Result.Top.Y == Result.Next.Bot.Y && Result.Next.OutIdx != Skip)
            Result = Result.Next;
        
        // 处理水平连接
        if (Result.Dx == horizontal && Result.Next.OutIdx != Skip)
        {
            // ... 处理顶部水平边 ...
        }
        
        // 设置 NextInLML 链接
        while (E != Result)
        {
            E.NextInLML = E.Next;
            if (E.Dx == horizontal && E != EStart && E.Bot.X != E.Prev.Top.X) 
                ReverseHorizontal(E);
            E = E.Next;
        }
        Result = Result.Next;
    }
    else
    {
        // 向上沿 Prev 方向（逻辑类似）
        // ...
    }
    return Result;
}

8.4.1 NextInLML 的构建

从局部极小值向上遍历，构建 NextInLML 链：

局部极小值 LM
    ├── LeftBound: e1 → e2 → e3 (NextInLML 链)
    └── RightBound: e4 → e5 → e6 (NextInLML 链)

        e3      e6
        │       │
        e2      e5
         ╲     ╱
          e1-e4
            LM

8.5 InsertLocalMinima 方法

将局部极小值插入到有序链表：

private void InsertLocalMinima(LocalMinima newLm)
{
    if (m_MinimaList == null)
    {
        m_MinimaList = newLm;
    }
    else if (newLm.Y >= m_MinimaList.Y)
    {
        // 插入到头部
        newLm.Next = m_MinimaList;
        m_MinimaList = newLm;
    } 
    else
    {
        // 找到正确位置插入
        LocalMinima tmpLm = m_MinimaList;
        while (tmpLm.Next != null && (newLm.Y < tmpLm.Next.Y))
            tmpLm = tmpLm.Next;
        newLm.Next = tmpLm.Next;
        tmpLm.Next = newLm;
    }
}

排序规则：按 Y 坐标降序（Y 最大的在前）。

链表结构（按 Y 降序）：
m_MinimaList → LM(Y=100) → LM(Y=50) → LM(Y=0) → null

这样扫描从 Y=0 开始向上时，
可以按顺序遇到 LM(Y=0) → LM(Y=50) → LM(Y=100)

8.6 扫描线管理

8.6.1 Scanbeam 结构

internal class Scanbeam
{
    internal cInt Y;          // 扫描线 Y 坐标
    internal Scanbeam Next;   // 下一个扫描线
}

8.6.2 InsertScanbeam

internal void InsertScanbeam(cInt Y)
{
    if (m_Scanbeam == null)
    {
        m_Scanbeam = new Scanbeam();
        m_Scanbeam.Next = null;
        m_Scanbeam.Y = Y;
    }
    else if (Y > m_Scanbeam.Y)
    {
        // 插入到头部
        Scanbeam newSb = new Scanbeam();
        newSb.Y = Y;
        newSb.Next = m_Scanbeam;
        m_Scanbeam = newSb;
    }
    else
    {
        // 找位置插入，忽略重复
        Scanbeam sb2 = m_Scanbeam;
        while (sb2.Next != null && (Y <= sb2.Next.Y)) 
            sb2 = sb2.Next;
        if (Y == sb2.Y) return;  // 忽略重复
        Scanbeam newSb = new Scanbeam();
        newSb.Y = Y;
        newSb.Next = sb2.Next;
        sb2.Next = newSb;
    }
}

8.6.3 PopScanbeam

internal Boolean PopScanbeam(out cInt Y)
{
    if (m_Scanbeam == null)
    {
        Y = 0;
        return false;
    }
    Y = m_Scanbeam.Y;
    m_Scanbeam = m_Scanbeam.Next;
    return true;
}

8.6.4 扫描线事件

扫描线 Y 坐标来自以下事件：

1. 局部极小值：边开始参与
2. 局部极大值：边结束
3. 边的转折点：边的 Top 到达
4. 交点：（在处理过程中动态添加）

Y
↑
80 ─────── 局部极大值
70 ─────── 交点
60 ─────── 边转折点
40 ─────── 交点
20 ─────── 局部极小值
0  ─────── 局部极小值

8.7 扫描线处理循环

主处理循环在 ExecuteInternal 中：

private bool ExecuteInternal()
{
    Reset();
    m_SortedEdges = null;
    m_Maxima = null;

    cInt botY, topY;
    if (!PopScanbeam(out botY)) return false;
    
    // 插入初始局部极小值
    InsertLocalMinimaIntoAEL(botY);
    
    // 主循环
    while (PopScanbeam(out topY) || LocalMinimaPending())
    {
        // 处理水平边
        ProcessHorizontals();
        m_GhostJoins.Clear();
        
        // 处理交点
        if (!ProcessIntersections(topY)) 
            return false;
        
        // 处理扫描线顶部的边
        ProcessEdgesAtTopOfScanbeam(topY);
        
        botY = topY;
        // 插入新的局部极小值
        InsertLocalMinimaIntoAEL(botY);
    }
    
    // 后处理：方向修正、连接处理等
    // ...
    
    return true;
}

8.7.1 处理流程图

开始
  │
  ▼
PopScanbeam(botY)
  │
  ▼
InsertLocalMinimaIntoAEL(botY)
  │
  ▼
┌─────────────────────────────────┐
│ while (PopScanbeam || Pending) │
│  │                              │
│  ├─► ProcessHorizontals()      │
│  │                              │
│  ├─► ProcessIntersections()    │
│  │                              │
│  ├─► ProcessEdgesAtTopOfScanbeam│
│  │                              │
│  └─► InsertLocalMinimaIntoAEL  │
│                                 │
└─────────────────────────────────┘
  │
  ▼
后处理
  │
  ▼
完成

8.8 InsertLocalMinimaIntoAEL

将当前扫描线上的局部极小值的边插入活动边表：

private void InsertLocalMinimaIntoAEL(cInt botY)
{
    LocalMinima lm;
    while (PopLocalMinima(botY, out lm))
    {
        TEdge lb = lm.LeftBound;
        TEdge rb = lm.RightBound;

        OutPt Op1 = null;
        if (lb == null)
        {
            // 只有右边界
            InsertEdgeIntoAEL(rb, null);
            SetWindingCount(rb);
            if (IsContributing(rb))
                Op1 = AddOutPt(rb, rb.Bot);
        }
        else if (rb == null)
        {
            // 只有左边界
            InsertEdgeIntoAEL(lb, null);
            SetWindingCount(lb);
            if (IsContributing(lb))
                Op1 = AddOutPt(lb, lb.Bot);
            InsertScanbeam(lb.Top.Y);
        }
        else
        {
            // 两个边界都存在
            InsertEdgeIntoAEL(lb, null);
            InsertEdgeIntoAEL(rb, lb);
            SetWindingCount(lb);
            rb.WindCnt = lb.WindCnt;
            rb.WindCnt2 = lb.WindCnt2;
            if (IsContributing(lb))
                Op1 = AddLocalMinPoly(lb, rb, lb.Bot);
            InsertScanbeam(lb.Top.Y);
        }

        // 处理右边界
        if (rb != null)
        {
            if (IsHorizontal(rb))
            {
                if (rb.NextInLML != null)
                    InsertScanbeam(rb.NextInLML.Top.Y);
                AddEdgeToSEL(rb);
            }
            else
                InsertScanbeam(rb.Top.Y);
        }

        // 处理边之间的交叉
        if (lb == null || rb == null) continue;
        
        // ... 处理连接点 ...
    }
}

8.9 局部极小值的类型

8.9.1 V 形极小值

    ╱╲
   ╱  ╲
  ╱    ╲
 ●      ●
  LeftBound  RightBound

两个边界都存在，形成 V 形。

8.9.2 单边极小值（开放路径）

    │
    │
    │
    ●
  单边界（开放路径的端点）

只有一个边界，另一个为 null。

8.9.3 水平极小值

  ╲      ╱
   ╲    ╱
    ●──●
   水平段

极小值点连接一个或多个水平边。

8.10 LocalMinimaPending

internal Boolean LocalMinimaPending()
{
    return (m_CurrentLM != null);
}

检查是否还有未处理的局部极小值。

8.11 本章小结

本章深入分析了 Clipper 的局部极小值和扫描线机制：

1. 局部极小值：

   • 多边形轮廓上的最低点
   • 作为边进入活动边表的入口
   • LocalMinima 结构包含左右边界

2. 边界处理：

   • ProcessBound 构建 NextInLML 链
   • 正确处理水平边
   • 确定左右边界

3. 扫描线管理：

   • InsertScanbeam 维护有序扫描线列表
   • PopScanbeam 获取下一个扫描位置
   • 扫描线来自多种事件

4. 主循环：

   • 从底部向上扫描
   • 在每个扫描线处理边的插入、交点、移除
   • InsertLocalMinimaIntoAEL 将边加入活动边表

理解这些机制是理解 Clipper 裁剪算法的关键基础。

上一章：TEdge边缘结构 | 返回目录 | 下一章：Clipper类结构