第14章：输出多边形构建

14.1 概述

在 Clipper 处理过程中，输出多边形通过 OutRec 和 OutPt 数据结构逐步构建。本章将详细分析这些结构及其相关方法。

14.2 OutRec 结构

internal class OutRec
{
    internal int Idx;              // 在 m_PolyOuts 中的索引
    internal bool IsHole;          // 是否为孔洞
    internal bool IsOpen;          // 是否为开放路径
    internal OutRec FirstLeft;     // 第一个左侧轮廓（父轮廓）
    internal OutPt Pts;            // 输出点链表头
    internal OutPt BottomPt;       // 最底部的点
    internal PolyNode PolyNode;    // 对应的 PolyNode（用于 PolyTree）
}

14.3 OutPt 结构

internal class OutPt
{
    internal int Idx;      // 所属 OutRec 的索引
    internal IntPoint Pt;  // 点坐标
    internal OutPt Next;   // 下一个点
    internal OutPt Prev;   // 上一个点
}

14.3.1 OutPt 链表结构

环形双向链表：

     ┌──────────────────────────┐
     │                          │
     ▼                          │
  OutPt1 ←──→ OutPt2 ←──→ OutPt3 ─┘
     ▲           │
     └───────────┘
         Pts（入口点）

14.4 CreateOutRec

创建新的输出记录：

internal OutRec CreateOutRec()
{
    OutRec result = new OutRec();
    result.Idx = Unassigned;
    result.IsHole = false;
    result.IsOpen = false;
    result.FirstLeft = null;
    result.Pts = null;
    result.BottomPt = null;
    result.PolyNode = null;
    m_PolyOuts.Add(result);
    result.Idx = m_PolyOuts.Count - 1;
    return result;
}

14.5 AddOutPt

向输出多边形添加点：

internal OutPt AddOutPt(TEdge e, IntPoint pt)
{
    if (e.OutIdx < 0)
    {
        // 创建新的输出记录
        OutRec outRec = CreateOutRec();
        outRec.IsOpen = (e.WindDelta == 0);
        OutPt newOp = new OutPt();
        outRec.Pts = newOp;
        newOp.Idx = outRec.Idx;
        newOp.Pt = pt;
        newOp.Next = newOp;
        newOp.Prev = newOp;
        if (!outRec.IsOpen)
            SetHoleState(e, outRec);
        e.OutIdx = outRec.Idx;
        return newOp;
    }
    else
    {
        // 添加到已有输出记录
        OutRec outRec = m_PolyOuts[e.OutIdx];
        OutPt op = outRec.Pts;
        
        bool ToFront = (e.Side == EdgeSide.esLeft);
        
        if (ToFront && pt == op.Pt) 
            return op;
        else if (!ToFront && pt == op.Prev.Pt) 
            return op.Prev;

        OutPt newOp = new OutPt();
        newOp.Idx = outRec.Idx;
        newOp.Pt = pt;
        newOp.Next = op;
        newOp.Prev = op.Prev;
        newOp.Prev.Next = newOp;
        op.Prev = newOp;
        if (ToFront) outRec.Pts = newOp;
        return newOp;
    }
}

14.5.1 添加点的两种情况

情况1: 新建输出记录
  边 e 没有关联的 OutRec
  → 创建新 OutRec
  → 创建第一个 OutPt
  → 形成单点的循环链表

情况2: 添加到已有记录
  边 e 已有关联的 OutRec
  → 根据边的 Side 决定添加到头部还是尾部
  → 插入新 OutPt 到链表

14.5.2 ToFront 判断

Side == esLeft  → 添加到前面（Pts）
Side == esRight → 添加到后面（Pts.Prev）

      Pts
       │
       ▼
  ●───►●───►●───►●
  │                 │
  └────◄────◄────◄─┘
              ▲
              │
          Pts.Prev

14.6 AddLocalMinPoly

在局部极小值处创建新的输出多边形：

private OutPt AddLocalMinPoly(TEdge e1, TEdge e2, IntPoint pt)
{
    OutPt result;
    TEdge e, prevE;
    
    if (IsHorizontal(e2) || (e1.Dx > e2.Dx))
    {
        result = AddOutPt(e1, pt);
        e2.OutIdx = e1.OutIdx;
        e1.Side = EdgeSide.esLeft;
        e2.Side = EdgeSide.esRight;
        e = e1;
        if (e.PrevInAEL == e2)
            prevE = e2.PrevInAEL; 
        else
            prevE = e.PrevInAEL;
    }
    else
    {
        result = AddOutPt(e2, pt);
        e1.OutIdx = e2.OutIdx;
        e1.Side = EdgeSide.esRight;
        e2.Side = EdgeSide.esLeft;
        e = e2;
        if (e.PrevInAEL == e1)
            prevE = e1.PrevInAEL;
        else
            prevE = e.PrevInAEL;
    }

    if (prevE != null && prevE.OutIdx >= 0 && prevE.Top.Y < pt.Y && e.Top.Y < pt.Y)
    {
        cInt xPrev = TopX(prevE, pt.Y);
        cInt xE = TopX(e, pt.Y);
        if ((xPrev == xE) && (e.WindDelta != 0) && (prevE.WindDelta != 0) &&
            SlopesEqual(new IntPoint(xPrev, pt.Y), prevE.Top, 
                       new IntPoint(xE, pt.Y), e.Top, m_UseFullRange))
        {
            OutPt outPt = AddOutPt(prevE, pt);
            AddJoin(result, outPt, e.Top);
        }
    }
    return result;
}

14.6.1 局部极小值图解

          ╲        ╱
           ╲  pt  ╱
            ╲    ╱
         e1  ╲  ╱ e2
              ╲╱
              极小值点

创建 OutRec:
- e1 设为左边界（Side = esLeft）
- e2 设为右边界（Side = esRight）
- 两边共享同一个 OutIdx

14.7 AddLocalMaxPoly

在局部极大值处关闭输出多边形：

private void AddLocalMaxPoly(TEdge e1, TEdge e2, IntPoint pt)
{
    AddOutPt(e1, pt);
    
    if (e2.WindDelta == 0) 
        AddOutPt(e2, pt);
    
    if (e1.OutIdx == e2.OutIdx)
    {
        e1.OutIdx = Unassigned;
        e2.OutIdx = Unassigned;
    }
    else if (e1.OutIdx < e2.OutIdx) 
        AppendPolygon(e1, e2);
    else 
        AppendPolygon(e2, e1);
}

14.7.1 局部极大值图解

              ╱╲
             ╱  ╲
        e1  ╱    ╲ e2
           ╱  pt  ╲
          ╱        ╲
         极大值点

处理:
- 添加点 pt 到输出
- 如果两边属于同一输出，关闭多边形
- 如果属于不同输出，合并它们

14.8 AppendPolygon

合并两个输出多边形：

private void AppendPolygon(TEdge e1, TEdge e2)
{
    OutRec outRec1 = m_PolyOuts[e1.OutIdx];
    OutRec outRec2 = m_PolyOuts[e2.OutIdx];

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

    // 获取两个输出的点
    OutPt p1_lft = outRec1.Pts;
    OutPt p1_rt = p1_lft.Prev;
    OutPt p2_lft = outRec2.Pts;
    OutPt p2_rt = p2_lft.Prev;

    // 根据边的 Side 连接
    if (e1.Side == EdgeSide.esLeft)
    {
        if (e2.Side == EdgeSide.esLeft)
        {
            // 反转 p2 并连接
            ReversePolyPtLinks(p2_lft);
            p2_lft.Next = p1_lft;
            p1_lft.Prev = p2_lft;
            p1_rt.Next = p2_rt;
            p2_rt.Prev = p1_rt;
            outRec1.Pts = p2_rt;
        }
        else
        {
            // 直接连接
            p2_rt.Next = p1_lft;
            p1_lft.Prev = p2_rt;
            p2_lft.Prev = p1_rt;
            p1_rt.Next = p2_lft;
            outRec1.Pts = p2_lft;
        }
    }
    else
    {
        if (e2.Side == EdgeSide.esRight)
        {
            ReversePolyPtLinks(p2_lft);
            p1_rt.Next = p2_rt;
            p2_rt.Prev = p1_rt;
            p2_lft.Next = p1_lft;
            p1_lft.Prev = p2_lft;
        }
        else
        {
            p1_rt.Next = p2_lft;
            p2_lft.Prev = p1_rt;
            p1_lft.Prev = p2_rt;
            p2_rt.Next = p1_lft;
        }
    }

    outRec1.BottomPt = null;
    
    // 更新孔洞状态
    if (holeStateRec == outRec2)
    {
        if (outRec2.FirstLeft != outRec1)
            outRec1.FirstLeft = outRec2.FirstLeft;
        outRec1.IsHole = outRec2.IsHole;
    }
    
    // 清理 outRec2
    outRec2.Pts = null;
    outRec2.BottomPt = null;
    outRec2.FirstLeft = outRec1;

    int OKIdx = e1.OutIdx;
    int ObsoleteIdx = e2.OutIdx;

    e1.OutIdx = Unassigned;
    e2.OutIdx = Unassigned;

    // 更新所有引用 ObsoleteIdx 的边
    TEdge e = m_ActiveEdges;
    while (e != null)
    {
        if (e.OutIdx == ObsoleteIdx)
        {
            e.OutIdx = OKIdx;
            e.Side = e1.Side;
        }
        e = e.NextInAEL;
    }
    
    outRec2.Idx = outRec1.Idx;
}

14.9 ReversePolyPtLinks

反转点链表的方向：

private void ReversePolyPtLinks(OutPt pp)
{
    if (pp == null) return;
    OutPt pp1;
    OutPt pp2;
    pp1 = pp;
    do
    {
        pp2 = pp1.Next;
        pp1.Next = pp1.Prev;
        pp1.Prev = pp2;
        pp1 = pp2;
    } while (pp1 != pp);
}

14.10 FixupOutPolygon

清理输出多边形（移除重复点和共线边）：

private void FixupOutPolygon(OutRec outRec)
{
    OutPt lastOK = null;
    outRec.BottomPt = null;
    OutPt pp = outRec.Pts;
    bool preserveCol = PreserveCollinear || StrictlySimple;
    
    for (;;)
    {
        if (pp.Prev == pp || pp.Prev == pp.Next)
        {
            outRec.Pts = null;
            return;
        }
        
        // 检查重复点和共线边
        if ((pp.Pt == pp.Next.Pt) || (pp.Pt == pp.Prev.Pt) ||
            (SlopesEqual(pp.Prev.Pt, pp.Pt, pp.Next.Pt, m_UseFullRange) &&
            (!preserveCol || !Pt2IsBetweenPt1AndPt3(pp.Prev.Pt, pp.Pt, pp.Next.Pt))))
        {
            lastOK = null;
            // 移除当前点
            pp.Prev.Next = pp.Next;
            pp.Next.Prev = pp.Prev;
            pp = pp.Prev;
        }
        else if (pp == lastOK) 
            break;
        else
        {
            if (lastOK == null) lastOK = pp;
            pp = pp.Next;
        }
    }
    outRec.Pts = pp;
}

14.11 GetOutRec

获取最终的输出记录（处理合并情况）：

private OutRec GetOutRec(int idx)
{
    OutRec outrec = m_PolyOuts[idx];
    while (outrec != m_PolyOuts[outrec.Idx])
        outrec = m_PolyOuts[outrec.Idx];
    return outrec;
}

14.12 UpdateOutPtIdxs

更新输出点的索引：

private void UpdateOutPtIdxs(OutRec outrec)
{  
    OutPt op = outrec.Pts;
    do
    {
        op.Idx = outrec.Idx;
        op = op.Prev;
    }
    while (op != outrec.Pts);
}

14.13 PointCount

计算输出多边形的点数：

private int PointCount(OutPt pts)
{
    if (pts == null) return 0;
    int result = 0;
    OutPt p = pts;
    do
    {
        result++;
        p = p.Next;
    }
    while (p != pts);
    return result;
}

14.14 输出构建流程

1. 局部极小值 → AddLocalMinPoly
   创建新的 OutRec 和初始点

2. 边处理 → AddOutPt
   逐步添加点到输出多边形

3. 局部极大值 → AddLocalMaxPoly
   关闭多边形或合并多边形

4. 后处理 → FixupOutPolygon
   清理重复点和共线边

5. 构建结果 → BuildResult/BuildResult2
   转换为最终的 Paths 或 PolyTree

14.15 本章小结

本章详细分析了 Clipper 的输出多边形构建：

数据结构：
- OutRec：输出记录
- OutPt：输出点链表
核心方法：
- AddOutPt：添加点
- AddLocalMinPoly：极小值创建
- AddLocalMaxPoly：极大值关闭
- AppendPolygon：合并多边形
后处理：
- FixupOutPolygon：清理输出
- BuildResult：构建最终结果

理解输出构建对于理解 Clipper 的完整工作流程至关重要。

上一章：水平边处理

返回目录

下一章：孔洞检测与处理