znlgis 博客

GIS开发与技术分享

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

14.1 概述

本章将详细分析 Clipper2 执行布尔运算的完整流程，从输入多边形到输出结果的每个步骤。理解这个流程对于调试问题和优化性能至关重要。

14.2 执行流程总览

┌─────────────────────────────────────────────────────┐
│                    Execute()                         │
├─────────────────────────────────────────────────────┤
│ 1. 预处理阶段                                        │
│    ├── 构建顶点列表                                  │
│    ├── 识别局部极值                                  │
│    └── 排序局部极小值                                │
├─────────────────────────────────────────────────────┤
│ 2. 扫描线处理阶段                                    │
│    ├── 插入局部极小值到 AEL                          │
│    ├── 处理水平边                                    │
│    ├── 计算并处理交点                                │
│    └── 处理扫描带顶部                                │
├─────────────────────────────────────────────────────┤
│ 3. 后处理阶段                                        │
│    ├── 处理连接                                      │
│    ├── 清理共线点                                    │
│    └── 构建输出路径                                  │
└─────────────────────────────────────────────────────┘

14.3 预处理阶段

14.3.1 AddPath 处理

public void AddPaths(Paths64 paths, PathType pathtype, bool isOpen = false)
{
    // 标记是否有开放路径
    if (isOpen) _hasOpenPaths = true;
    
    // 标记需要重新排序
    _isSortedMinimaList = false;
    
    foreach (Path64 path in paths)
    {
        // 跳过无效路径
        if (path.Count < 2) continue;
        if (!isOpen && path.Count < 3) continue;
        
        // 构建顶点链表
        AddPathToVertexList(path, pathtype, isOpen);
    }
}

14.3.2 构建顶点链表

private void AddPathToVertexList(Path64 path, PathType pathtype, bool isOpen)
{
    // 创建顶点
    Vertex? firstVert = null;
    Vertex? prevVert = null;
    
    foreach (Point64 pt in path)
    {
        // 跳过重复点
        if (prevVert != null && pt == prevVert.pt) continue;
        
        Vertex v = new Vertex { pt = pt };
        
        if (firstVert == null)
            firstVert = v;
        else
        {
            prevVert!.next = v;
            v.prev = prevVert;
        }
        prevVert = v;
    }
    
    // 闭合路径
    if (!isOpen && firstVert != null && prevVert != null)
    {
        prevVert.next = firstVert;
        firstVert.prev = prevVert;
    }
    
    // 标记并添加局部极值
    if (firstVert != null)
        FindAndMarkLocalMinMax(firstVert, pathtype, isOpen);
}

14.3.3 识别局部极值

private void FindAndMarkLocalMinMax(Vertex firstVertex, 
    PathType pathtype, bool isOpen)
{
    Vertex v = firstVertex;
    
    do
    {
        // 跳过水平段
        if (v.pt.Y == v.next!.pt.Y) 
        {
            v = v.next;
            continue;
        }
        
        // 检查局部极小值
        if (IsLocalMin(v))
        {
            v.flags |= VertexFlags.LocalMin;
            AddLocMin(v, pathtype, isOpen);
        }
        // 检查局部最大值
        else if (IsLocalMax(v))
        {
            v.flags |= VertexFlags.LocalMax;
        }
        
        v = v.next;
    } while (v != firstVertex);
}

private bool IsLocalMin(Vertex v)
{
    Vertex prev = v.prev!;
    Vertex next = v.next!;
    
    // 向上找第一个非水平点
    while (prev.pt.Y == v.pt.Y) prev = prev.prev!;
    while (next.pt.Y == v.pt.Y) next = next.next!;
    
    return prev.pt.Y > v.pt.Y && next.pt.Y >= v.pt.Y;
}

14.3.4 排序局部极小值

private void SortMinimaList()
{
    if (!_isSortedMinimaList)
    {
        // 按 Y 坐标降序排序（从大到小）
        _minimaList.Sort((a, b) => b.vertex.pt.Y.CompareTo(a.vertex.pt.Y));
        
        _isSortedMinimaList = true;
        
        // 初始化扫描线列表
        _scanlineList.Clear();
        foreach (var lm in _minimaList)
            _scanlineList.Add(lm.vertex.pt.Y);
    }
}

14.4 扫描线处理主循环

14.4.1 ExecuteInternal 主循环

private void ExecuteInternal(ClipType ct, FillRule fillrule)
{
    if (ct == ClipType.NoClip) return;
    
    _fillrule = fillrule;
    _cliptype = ct;
    
    Reset();
    
    if (!PopScanline(out long y)) return;
    
    while (true)
    {
        // 步骤1：插入当前 Y 的局部极小值
        InsertLocalMinimaIntoAEL(y);
        
        // 步骤2：处理所有水平边
        while (PopHorz(out Active? horz))
        {
            DoHorizontal(horz!);
        }
        
        // 步骤3：获取下一个扫描线
        if (!PopScanline(out long topY)) break;
        
        // 步骤4：处理当前扫描带的交点
        DoIntersections(y, topY);
        
        // 步骤5：处理扫描带顶部事件
        DoTopOfScanbeam(topY);
        
        // 步骤6：更新水平边
        while (PopHorz(out Active? horz))
        {
            DoHorizontal(horz!);
        }
        
        y = topY;
    }
}

14.4.2 扫描带概念

Y = 100  ───────────────────  扫描线 (当前 y)
          ╲                ╱
           ╲   扫描带     ╱
            ╲            ╱
Y = 80   ───────────────────  扫描线 (topY)
              ╲        ╱
               ╲      ╱
                ╲    ╱
Y = 60   ───────────────────  下一个扫描线

14.5 步骤1：插入局部极小值

14.5.1 InsertLocalMinimaIntoAEL

private void InsertLocalMinimaIntoAEL(long botY)
{
    while (PopLocalMinima(botY, out LocalMinima locMin))
    {
        Vertex vert = locMin.vertex;
        
        // 创建左边（向 next 方向）
        Active leftBound = new Active
        {
            bot = vert.pt,
            top = vert.next!.pt,
            curX = vert.pt.X,
            dx = GetDx(vert.pt, vert.next.pt),
            windDx = 1,
            vertexTop = vert.next,
            localMin = locMin,
            isLeftBound = true
        };
        
        // 创建右边（向 prev 方向）
        Active rightBound = new Active
        {
            bot = vert.pt,
            top = vert.prev!.pt,
            curX = vert.pt.X,
            dx = GetDx(vert.pt, vert.prev.pt),
            windDx = -1,
            vertexTop = vert.prev,
            localMin = locMin,
            isLeftBound = false
        };
        
        // 插入到 AEL
        InsertLeftEdge(leftBound);
        
        // 设置缠绕计数
        SetWindCountForClosedPathEdge(leftBound);
        
        // 检查是否贡献输出
        if (IsContributingClosed(leftBound))
        {
            Active ae2 = rightBound;
            SetOutRecReference(leftBound, ae2);
        }
        
        InsertRightEdge(rightBound, leftBound);
        SetWindCountForClosedPathEdge(rightBound);
        
        // 添加局部最小值输出点
        if (leftBound.outrec != null)
        {
            AddLocalMinPoly(leftBound, rightBound, leftBound.bot);
        }
        
        // 添加下一个扫描线
        if (leftBound.top.Y < botY)
            AddScanline(leftBound.top.Y);
        if (rightBound.top.Y < botY)
            AddScanline(rightBound.top.Y);
    }
}

14.5.2 AEL 排序插入

private void InsertLeftEdge(Active ae)
{
    if (_actives == null)
    {
        ae.prevInAEL = null;
        ae.nextInAEL = null;
        _actives = ae;
    }
    else if (!IsValidAelOrder(_actives, ae))
    {
        ae.prevInAEL = null;
        ae.nextInAEL = _actives;
        _actives.prevInAEL = ae;
        _actives = ae;
    }
    else
    {
        Active ae2 = _actives;
        while (ae2.nextInAEL != null && IsValidAelOrder(ae2.nextInAEL, ae))
            ae2 = ae2.nextInAEL;
        
        ae.nextInAEL = ae2.nextInAEL;
        if (ae2.nextInAEL != null)
            ae2.nextInAEL.prevInAEL = ae;
        ae.prevInAEL = ae2;
        ae2.nextInAEL = ae;
    }
}

14.6 步骤2：处理水平边

14.6.1 DoHorizontal

private void DoHorizontal(Active horz)
{
    // 确定水平边方向
    bool leftToRight;
    long horzLeft, horzRight;
    
    if (horz.bot.X < horz.top.X)
    {
        leftToRight = true;
        horzLeft = horz.bot.X;
        horzRight = horz.top.X;
    }
    else
    {
        leftToRight = false;
        horzLeft = horz.top.X;
        horzRight = horz.bot.X;
    }
    
    // 处理与其他边的交点
    Active? ae = leftToRight ? horz.nextInAEL : horz.prevInAEL;
    
    while (ae != null)
    {
        // 检查是否在水平边范围内
        if ((leftToRight && ae.curX > horzRight) ||
            (!leftToRight && ae.curX < horzLeft))
            break;
        
        // 计算交点
        Point64 pt = new Point64(ae.curX, horz.bot.Y);
        
        // 处理交点
        if (ae.curX >= horzLeft && ae.curX <= horzRight)
        {
            IntersectEdges(horz, ae, pt);
            SwapPositionsInAEL(horz, ae);
        }
        
        ae = leftToRight ? ae.nextInAEL : ae.prevInAEL;
    }
    
    // 更新或删除水平边
    UpdateEdgeIntoAEL(ref horz);
}

14.7 步骤3-4：处理交点

14.7.1 BuildIntersectList

private bool BuildIntersectList(long topY)
{
    if (_actives == null || _actives.nextInAEL == null) 
        return false;
    
    // 使用简单冒泡找出需要交换的边对
    bool result = false;
    
    Active? ae = _actives;
    while (ae.nextInAEL != null)
    {
        Active ae2 = ae.nextInAEL;
        
        // 计算两边在 topY 的 X 坐标
        long x1 = TopX(ae, topY);
        long x2 = TopX(ae2, topY);
        
        // 检查是否需要交换（X 顺序改变）
        if (x1 > x2)
        {
            // 计算交点
            if (GetIntersection(ae, ae2, out Point64 pt))
            {
                // 限制在扫描带内
                if (pt.Y > _currentBotY) pt.Y = _currentBotY;
                if (pt.Y < topY) pt.Y = topY;
                
                AddIntersectNode(ae, ae2, pt);
                result = true;
            }
        }
        
        ae = ae2;
    }
    
    // 排序交点（按 Y 降序，Y 相同时按 X 升序）
    if (_intersectList.Count > 1)
    {
        _intersectList.Sort((a, b) => {
            if (a.pt.Y != b.pt.Y)
                return b.pt.Y.CompareTo(a.pt.Y);
            return a.pt.X.CompareTo(b.pt.X);
        });
    }
    
    return result;
}

14.7.2 ProcessIntersectList

private void ProcessIntersectList()
{
    foreach (IntersectNode node in _intersectList)
    {
        // 处理交点
        IntersectEdges(node.edge1, node.edge2, node.pt);
        
        // 交换边在 AEL 中的位置
        SwapPositionsInAEL(node.edge1, node.edge2);
    }
    
    _intersectList.Clear();
}

14.7.3 IntersectEdges

private void IntersectEdges(Active ae1, Active ae2, Point64 pt)
{
    // 保存当前状态
    bool ae1Contributing = ae1.outrec != null;
    bool ae2Contributing = ae2.outrec != null;
    
    // 更新缠绕计数
    if (GetPolyType(ae1) == GetPolyType(ae2))
    {
        // 同类型
        if (_fillrule == FillRule.EvenOdd)
        {
            int tmp = ae1.windCnt;
            ae1.windCnt = ae2.windCnt;
            ae2.windCnt = tmp;
        }
        else
        {
            ae1.windCnt += ae2.windDx;
            ae2.windCnt -= ae1.windDx;
        }
    }
    else
    {
        // 不同类型
        ae1.windCnt2 += ae2.windDx;
        ae2.windCnt2 -= ae1.windDx;
    }
    
    // 检查新的贡献状态
    bool ae1ContributingNew = IsContributing(ae1);
    bool ae2ContributingNew = IsContributing(ae2);
    
    // 根据状态变化处理
    if (ae1Contributing && ae2Contributing)
    {
        if (ae1ContributingNew && ae2ContributingNew)
        {
            // 两边继续贡献
            AddOutPt(ae1, pt);
            AddOutPt(ae2, pt);
            SwapOutrecs(ae1, ae2);
        }
        else if (ae1ContributingNew)
        {
            // 只有 ae1 继续
            AddOutPt(ae1, pt);
            SwapOutrecs(ae1, ae2);
        }
        else if (ae2ContributingNew)
        {
            // 只有 ae2 继续
            AddOutPt(ae2, pt);
            SwapOutrecs(ae1, ae2);
        }
        else
        {
            // 两边都停止 -> 局部最大值
            AddLocalMaxPoly(ae1, ae2, pt);
        }
    }
    else if (ae1Contributing)
    {
        AddOutPt(ae1, pt);
        SwapOutrecs(ae1, ae2);
    }
    else if (ae2Contributing)
    {
        AddOutPt(ae2, pt);
        SwapOutrecs(ae1, ae2);
    }
    else if (!ae1ContributingNew && !ae2ContributingNew)
    {
        // 开始新的局部最小值
        AddLocalMinPoly(ae1, ae2, pt, true);
    }
}

14.8 步骤5：处理扫描带顶部

14.8.1 DoTopOfScanbeam

private void DoTopOfScanbeam(long y)
{
    _sel = null;
    Active? ae = _actives;
    
    while (ae != null)
    {
        // 更新当前 X 坐标
        ae.curX = TopX(ae, y);
        
        // 检查是否到达顶点
        if (ae.top.Y == y)
        {
            // 到达顶点
            ae = DoMaxima(ae, y);
        }
        else
        {
            // 继续向上
            // 检查是否有新的水平边
            if (IsHorizontal(ae.vertexTop!))
            {
                PushHorz(ae);
            }
            ae = ae.nextInAEL;
        }
    }
}

14.8.2 DoMaxima

private Active? DoMaxima(Active ae, long y)
{
    Active? prevE = ae.prevInAEL;
    Active? nextE = ae.nextInAEL;
    
    // 检查是否是局部最大值
    if (IsLocalMaxima(ae))
    {
        // 查找配对边
        Active? maxPair = GetMaximaPair(ae);
        
        if (maxPair == null)
        {
            // 开放路径端点
            if (ae.outrec != null)
                AddOutPt(ae, ae.top);
            DeleteFromAEL(ae);
            return nextE;
        }
        
        // 添加局部最大值
        if (ae.outrec != null || maxPair.outrec != null)
            AddLocalMaxPoly(ae, maxPair, ae.top);
        
        DeleteFromAEL(ae);
        DeleteFromAEL(maxPair);
        
        return prevE != null ? prevE.nextInAEL : _actives;
    }
    
    // 更新到下一段边
    UpdateEdgeIntoAEL(ref ae);
    return ae.nextInAEL;
}

14.9 后处理阶段

14.9.1 BuildPaths

private void BuildPaths(Paths64 closedPaths, Paths64 openPaths)
{
    foreach (OutRec outrec in _outrecList)
    {
        if (outrec.pts == null) continue;
        
        // 清理共线点
        CleanCollinear(outrec);
        
        if (outrec.pts == null) continue;
        
        // 构建路径
        Path64? path = BuildPath(outrec.pts, 
            ReverseSolution != IsPositive(outrec),
            outrec.isOpen);
        
        if (path == null || path.Count < 2) continue;
        
        if (outrec.isOpen)
            openPaths.Add(path);
        else if (path.Count > 2)
            closedPaths.Add(path);
    }
}

14.9.2 CleanCollinear

private void CleanCollinear(OutRec outrec)
{
    if (!PreserveCollinear)
    {
        OutPt? op = outrec.pts;
        if (op == null) return;
        
        OutPt startOp = op;
        
        do
        {
            // 检查是否共线
            if (InternalClipper.IsCollinear(op.prev!.pt, op.pt, op.next!.pt))
            {
                if (op == outrec.pts)
                    outrec.pts = op.prev;
                
                DisposeOutPt(op);
                op = op.prev!;
                
                if (op == outrec.pts)
                    startOp = op;
            }
            else
            {
                op = op.next;
            }
        } while (op != startOp && outrec.pts != null);
    }
}

14.10 完整流程示例

14.10.1 两个正方形求交

// 输入
Path64 subject = new Path64 { 
    (0,0), (100,0), (100,100), (0,100) 
};
Path64 clip = new Path64 { 
    (50,50), (150,50), (150,150), (50,150) 
};

// 1. 预处理
// Subject: 局部极小值在 Y=100 (顶点 (0,100) 和 (100,100))
// Clip: 局部极小值在 Y=150 (顶点 (50,150) 和 (150,150))

// 2. 扫描开始 Y=150
// 插入 Clip 的两条边

// 3. Y=100
// 插入 Subject 的两条边
// 检测交点

// 4. 交点处理
// (50,100), (100,50) 处产生交点

// 5. 构建输出
// 结果: (50,50), (100,50), (100,100), (50,100)

14.11 本章小结

布尔运算执行流程包含三个主要阶段：

  1. 预处理阶段：
    • 构建顶点链表
    • 识别局部极值
    • 排序局部极小值
  2. 扫描线处理：
    • 插入局部极小值
    • 处理水平边
    • 计算交点
    • 处理扫描带顶部
  3. 后处理阶段：
    • 清理共线点
    • 构建输出路径

理解这个流程有助于调试和优化 Clipper2 的使用。

上一章：ClipperD浮点裁剪类 返回目录 下一章：填充规则详解
↑