znlgis 博客

GIS开发与技术分享

第10章：布尔运算执行流程

10.1 概述

本章将详细分析 Clipper 执行布尔运算的完整流程，从输入数据的准备到最终结果的构建，深入理解 Vatti 算法在 Clipper 中的实现。

10.2 执行流程概览

用户调用 Execute()
        │
        ▼
┌─────────────────────────┐
│   ExecuteInternal()     │
│         │               │
│         ▼               │
│      Reset()            │← 重置状态
│         │               │
│         ▼               │
│   PopScanbeam(botY)     │← 获取最低扫描线
│         │               │
│         ▼               │
│ InsertLocalMinimaIntoAEL│← 插入初始边
│         │               │
│         ▼               │
│ ┌───────────────────┐   │
│ │   主处理循环      │   │
│ │       │           │   │
│ │ ProcessHorizontals│   │
│ │       │           │   │
│ │ ProcessIntersections│  │
│ │       │           │   │
│ │ ProcessEdgesAtTop │   │
│ │       │           │   │
│ │ InsertLocalMinima │   │
│ └───────────────────┘   │
│         │               │
│         ▼               │
│    后处理阶段           │
└─────────────────────────┘
        │
        ▼
  BuildResult/BuildResult2
        │
        ▼
    返回结果

10.3 Reset 方法

internal virtual void Reset()
{
    m_CurrentLM = m_MinimaList;
    if (m_CurrentLM == null) return;

    m_Scanbeam = null;
    
    LocalMinima lm = m_MinimaList;
    while (lm != null)
    {
        // 添加局部极小值的 Y 坐标到扫描线
        InsertScanbeam(lm.Y);
        
        // 重置左边界
        TEdge e = lm.LeftBound;
        if (e != null)
        {
            e.Curr = e.Bot;
            e.OutIdx = Unassigned;
        }
        
        // 重置右边界
        e = lm.RightBound;
        if (e != null)
        {
            e.Curr = e.Bot;
            e.OutIdx = Unassigned;
        }
        
        lm = lm.Next;
    }
    
    m_ActiveEdges = null;
}

功能：

  1. 设置当前局部极小值指针
  2. 初始化扫描线列表
  3. 重置所有边的状态
  4. 清空活动边表

10.4 主处理循环

while (PopScanbeam(out topY) || LocalMinimaPending())
{
    ProcessHorizontals();
    m_GhostJoins.Clear();
    
    if (!ProcessIntersections(topY)) return false;
    
    ProcessEdgesAtTopOfScanbeam(topY);
    botY = topY;
    InsertLocalMinimaIntoAEL(botY);
}

10.4.1 循环条件

  • PopScanbeam(out topY)：获取下一个扫描线 Y 坐标
  • LocalMinimaPending()：检查是否还有未处理的局部极小值

10.4.2 每次迭代的操作

  1. ProcessHorizontals：处理当前扫描线上的水平边
  2. ProcessIntersections：计算并处理边交点
  3. ProcessEdgesAtTopOfScanbeam：处理到达顶部的边
  4. InsertLocalMinimaIntoAEL：插入新到达的局部极小值

10.5 IsContributing 判断

判断边是否对输出多边形有贡献：

private bool IsContributing(TEdge edge)
{
    PolyFillType pft, pft2;
    
    // 根据边的类型获取填充规则
    if (edge.PolyTyp == PolyType.ptSubject)
    {
        pft = m_SubjFillType;
        pft2 = m_ClipFillType;
    }
    else
    {
        pft = m_ClipFillType;
        pft2 = m_SubjFillType;
    }

    // 根据填充规则检查边的缠绕数
    switch (pft)
    {
        case PolyFillType.pftEvenOdd:
            if (edge.WindDelta == 0 && edge.WindCnt != 1) 
                return false;
            break;
        case PolyFillType.pftNonZero:
            if (Math.Abs(edge.WindCnt) != 1) 
                return false;
            break;
        case PolyFillType.pftPositive:
            if (edge.WindCnt != 1) 
                return false;
            break;
        default: // pftNegative
            if (edge.WindCnt != -1) 
                return false; 
            break;
    }

    // 根据裁剪类型和另一类多边形的缠绕数判断
    switch (m_ClipType)
    {
        case ClipType.ctIntersection:
            switch (pft2)
            {
                case PolyFillType.pftEvenOdd:
                case PolyFillType.pftNonZero:
                    return (edge.WindCnt2 != 0);
                case PolyFillType.pftPositive:
                    return (edge.WindCnt2 > 0);
                default:
                    return (edge.WindCnt2 < 0);
            }
            
        case ClipType.ctUnion:
            switch (pft2)
            {
                case PolyFillType.pftEvenOdd:
                case PolyFillType.pftNonZero:
                    return (edge.WindCnt2 == 0);
                case PolyFillType.pftPositive:
                    return (edge.WindCnt2 <= 0);
                default:
                    return (edge.WindCnt2 >= 0);
            }
            
        case ClipType.ctDifference:
            if (edge.PolyTyp == PolyType.ptSubject)
                // Subject 边：必须在 Clip 外部
                switch (pft2)
                {
                    case PolyFillType.pftEvenOdd:
                    case PolyFillType.pftNonZero:
                        return (edge.WindCnt2 == 0);
                    case PolyFillType.pftPositive:
                        return (edge.WindCnt2 <= 0);
                    default:
                        return (edge.WindCnt2 >= 0);
                }
            else
                // Clip 边：必须在 Subject 内部
                switch (pft2)
                {
                    case PolyFillType.pftEvenOdd:
                    case PolyFillType.pftNonZero:
                        return (edge.WindCnt2 != 0);
                    case PolyFillType.pftPositive:
                        return (edge.WindCnt2 > 0);
                    default:
                        return (edge.WindCnt2 < 0);
                }
                
        case ClipType.ctXor:
            if (edge.WindDelta == 0)
                // 开放路径
                switch (pft2)
                {
                    case PolyFillType.pftEvenOdd:
                    case PolyFillType.pftNonZero:
                        return (edge.WindCnt2 == 0);
                    case PolyFillType.pftPositive:
                        return (edge.WindCnt2 <= 0);
                    default:
                        return (edge.WindCnt2 >= 0);
                }
            else
                return true;
    }
    return true;
}

10.5.1 判断逻辑图解

Intersection（交集）：
  Subject ∩ Clip
  边有贡献 ⟺ 边在自己类型的多边形内 AND 在对方类型的多边形内

Union（并集）：
  Subject ∪ Clip
  边有贡献 ⟺ 边在自己类型的多边形边界上 AND 不在对方类型的多边形内

Difference（差集）：
  Subject - Clip
  Subject边有贡献 ⟺ 边在Subject内 AND 不在Clip内
  Clip边有贡献 ⟺ 边在Clip边界上 AND 在Subject内

Xor（异或）：
  Subject ⊕ Clip
  边有贡献 ⟺ 边在任一多边形边界上

10.6 SetWindingCount 方法

计算边的缠绕数：

private void SetWindingCount(TEdge edge)
{
    TEdge e = edge.PrevInAEL;
    
    // 找到同类型的前一条边
    while (e != null && ((e.PolyTyp != edge.PolyTyp) || (e.WindDelta == 0))) 
        e = e.PrevInAEL;
    
    if (e == null)
    {
        // 没有同类型的边在前面
        PolyFillType pft;
        pft = (edge.PolyTyp == PolyType.ptSubject ? m_SubjFillType : m_ClipFillType);
        
        if (edge.WindDelta == 0) 
            edge.WindCnt = (pft == PolyFillType.pftNegative ? -1 : 1);
        else 
            edge.WindCnt = edge.WindDelta;
        
        edge.WindCnt2 = 0;
        e = m_ActiveEdges;  // 从头计算 WindCnt2
    }
    else if (edge.WindDelta == 0 && m_ClipType != ClipType.ctUnion)
    {
        edge.WindCnt = 1;
        edge.WindCnt2 = e.WindCnt2;
        e = e.NextInAEL;
    }
    else if (IsEvenOddFillType(edge))
    {
        // 奇偶填充规则
        if (edge.WindDelta == 0)
        {
            bool Inside = true;
            TEdge e2 = e.PrevInAEL;
            while (e2 != null)
            {
                if (e2.PolyTyp == e.PolyTyp && e2.WindDelta != 0)
                    Inside = !Inside;
                e2 = e2.PrevInAEL;
            }
            edge.WindCnt = (Inside ? 0 : 1);
        }
        else
        {
            edge.WindCnt = edge.WindDelta;
        }
        edge.WindCnt2 = e.WindCnt2;
        e = e.NextInAEL;
    }
    else
    {
        // 非零/正向/负向填充规则
        if (e.WindCnt * e.WindDelta < 0)
        {
            // 前一条边正在减少缠绕数
            if (Math.Abs(e.WindCnt) > 1)
            {
                if (e.WindDelta * edge.WindDelta < 0) 
                    edge.WindCnt = e.WindCnt;
                else 
                    edge.WindCnt = e.WindCnt + edge.WindDelta;
            }
            else
                edge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);
        }
        else
        {
            // 前一条边正在增加缠绕数
            if (edge.WindDelta == 0)
                edge.WindCnt = (e.WindCnt < 0 ? e.WindCnt - 1 : e.WindCnt + 1);
            else if (e.WindDelta * edge.WindDelta < 0)
                edge.WindCnt = e.WindCnt;
            else 
                edge.WindCnt = e.WindCnt + edge.WindDelta;
        }
        edge.WindCnt2 = e.WindCnt2;
        e = e.NextInAEL;
    }

    // 计算 WindCnt2（另一类多边形的缠绕数）
    if (IsEvenOddAltFillType(edge))
    {
        while (e != edge)
        {
            if (e.WindDelta != 0)
                edge.WindCnt2 = (edge.WindCnt2 == 0 ? 1 : 0);
            e = e.NextInAEL;
        }
    }
    else
    {
        while (e != edge)
        {
            edge.WindCnt2 += e.WindDelta;
            e = e.NextInAEL;
        }
    }
}

10.6.1 缠绕数计算示例

         AEL 顺序 →
扫描线 ─────e1─────e2─────e3─────e4─────
           │      │      │      │
           ↓      ↓      ↓      ↓
Subject:  +1     +1      -1     -1
WindCnt:   1      2       1      0

e1: WindCnt = WindDelta = 1
e2: WindCnt = e1.WindCnt + WindDelta = 1 + 1 = 2
e3: WindCnt = e2.WindCnt + WindDelta = 2 + (-1) = 1
e4: WindCnt = e3.WindCnt + WindDelta = 1 + (-1) = 0

10.7 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;
    }

    // 根据贡献状态处理输出
    // ... 详细的输出处理逻辑 ...
}

10.8 后处理阶段

10.8.1 方向修正

foreach (OutRec outRec in m_PolyOuts)
{
    if (outRec.Pts == null || outRec.IsOpen) continue;
    if ((outRec.IsHole ^ ReverseSolution) == (Area(outRec) > 0))
        ReversePolyPtLinks(outRec.Pts);
}

确保输出多边形具有正确的方向：

  • 外轮廓：正面积（逆时针）
  • 孔洞：负面积（顺时针）

10.8.2 JoinCommonEdges

处理共边的多边形：

private void JoinCommonEdges()
{
    for (int i = 0; i < m_Joins.Count; i++)
    {
        Join join = m_Joins[i];
        
        OutRec outRec1 = GetOutRec(join.OutPt1.Idx);
        OutRec outRec2 = GetOutRec(join.OutPt2.Idx);
        
        if (outRec1.Pts == null || outRec2.Pts == null) continue;
        if (outRec1.IsOpen || outRec2.IsOpen) continue;

        OutRec holeStateRec;
        if (outRec1 == outRec2) 
            holeStateRec = outRec1;
        else if (OutRec1RightOfOutRec2(outRec1, outRec2)) 
            holeStateRec = outRec2;
        else if (OutRec1RightOfOutRec2(outRec2, outRec1)) 
            holeStateRec = outRec1;
        else 
            holeStateRec = GetLowermostRec(outRec1, outRec2);

        if (!JoinPoints(join, outRec1, outRec2)) continue;

        // 处理连接结果
        if (outRec1 == outRec2)
        {
            // 分割多边形
            outRec1.Pts = join.OutPt1;
            outRec1.BottomPt = null;
            outRec2 = CreateOutRec();
            outRec2.Pts = join.OutPt2;
            // ... 更新孔洞状态 ...
        }
        else
        {
            // 合并多边形
            outRec2.Pts = null;
            outRec2.BottomPt = null;
            outRec2.Idx = outRec1.Idx;
            // ...
        }
    }
}

10.8.3 输出清理

foreach (OutRec outRec in m_PolyOuts)
{
    if (outRec.Pts == null) continue;
    else if (outRec.IsOpen)
        FixupOutPolyline(outRec);  // 清理开放路径
    else
        FixupOutPolygon(outRec);   // 清理闭合多边形
}

FixupOutPolygon：移除重复点和共线边。

10.8.4 DoSimplePolygons（可选）

if (StrictlySimple) DoSimplePolygons();

处理自相交的多边形，将其分割为简单多边形。

10.9 BuildResult 方法

构建最终的 Paths 结果：

private void BuildResult(Paths polyg)
{
    polyg.Clear();
    polyg.Capacity = m_PolyOuts.Count;
    
    for (int i = 0; i < m_PolyOuts.Count; i++)
    {
        OutRec outRec = m_PolyOuts[i];
        if (outRec.Pts == null) continue;
        
        OutPt p = outRec.Pts.Prev;
        int cnt = PointCount(p);
        if (cnt < 2) continue;
        
        Path pg = new Path(cnt);
        for (int j = 0; j < cnt; j++)
        {
            pg.Add(p.Pt);
            p = p.Prev;
        }
        polyg.Add(pg);
    }
}

10.10 本章小结

本章详细分析了 Clipper 布尔运算的执行流程：

  1. 初始化：Reset 准备所有数据结构

  2. 主循环：
    • 处理水平边
    • 计算和处理交点
    • 处理扫描线顶部的边
    • 插入新的局部极小值
  3. 核心判断：
    • IsContributing：判断边是否贡献输出
    • SetWindingCount：计算缠绕数
    • IntersectEdges：处理边交点
  4. 后处理：
    • 方向修正
    • 连接处理
    • 输出清理
    • 简单多边形处理
  5. 结果构建：
    • BuildResult：构建 Paths
    • BuildResult2：构建 PolyTree
上一章：Clipper类结构 返回目录 下一章：活动边表管理
↑