第3章：路径与多边形表示 - Path、Paths、PolyNode、PolyTree

3.1 概述

Clipper1 提供了两种表示多边形结果的方式：

1. 扁平表示：使用 Paths（路径列表），简单但不包含层次信息
2. 树形表示：使用 PolyTree（多边形树），包含完整的父子关系和孔洞信息

本章将深入分析这两种表示方式的源码实现。

3.2 PolyNode 类

PolyNode 是多边形树的基本节点，代表一个多边形轮廓。

3.2.1 类定义

public class PolyNode 
{
    internal PolyNode m_Parent;
    internal Path m_polygon = new Path();
    internal int m_Index;
    internal JoinType m_jointype;
    internal EndType m_endtype;
    internal List<PolyNode> m_Childs = new List<PolyNode>();
    
    // ... 方法定义 ...
}

3.2.2 成员变量详解

成员	类型	可见性	说明
m_Parent	PolyNode	internal	父节点引用
m_polygon	Path	internal	多边形顶点列表
m_Index	int	internal	在父节点子列表中的索引
m_jointype	JoinType	internal	连接类型（用于偏移）
m_endtype	EndType	internal	端点类型（用于偏移）
m_Childs	List<PolyNode>	internal	子节点列表

3.2.3 IsHole 属性

判断当前节点是否为孔洞：

private bool IsHoleNode()
{
    bool result = true;
    PolyNode node = m_Parent;
    while (node != null)
    {
        result = !result;
        node = node.m_Parent;
    }
    return result;
}

public bool IsHole
{
    get { return IsHoleNode(); }
}

算法原理：

树中的层次决定了多边形的性质：

• 偶数层（0, 2, 4...）：外轮廓（非孔洞）
• 奇数层（1, 3, 5...）：孔洞

PolyTree（根，层0）
├── 外轮廓A（层1）→ IsHole = false（根的子节点从层1开始）
│   └── 孔洞A1（层2）→ IsHole = true
│       └── 岛屿A1a（层3）→ IsHole = false
└── 外轮廓B（层1）→ IsHole = false

注意：从代码逻辑看，算法从当前节点开始向上遍历，每遍历一层就翻转结果。初始值为 true，到达根节点（Parent=null）时停止。这意味着根节点的直接子节点（第1层）会经历一次翻转，结果为 false（非孔洞）。

3.2.4 公共属性

public int ChildCount
{
    get { return m_Childs.Count; }
}

public Path Contour
{
    get { return m_polygon; }
}

public List<PolyNode> Childs
{
    get { return m_Childs; }
}

public PolyNode Parent
{
    get { return m_Parent; }
}

public bool IsOpen { get; set; }

属性	说明
ChildCount	子节点数量
Contour	多边形轮廓（顶点列表）
Childs	子节点列表
Parent	父节点
IsOpen	是否为开放路径（线段）

3.2.5 AddChild 方法

internal void AddChild(PolyNode Child)
{
    int cnt = m_Childs.Count;
    m_Childs.Add(Child);
    Child.m_Parent = this;
    Child.m_Index = cnt;
}

功能：

1. 将子节点添加到子列表
2. 设置子节点的父引用
3. 记录子节点在列表中的索引

3.2.6 树遍历方法

public PolyNode GetNext()
{
    if (m_Childs.Count > 0) 
        return m_Childs[0]; 
    else
        return GetNextSiblingUp();        
}

internal PolyNode GetNextSiblingUp()
{
    if (m_Parent == null)
        return null;
    else if (m_Index == m_Parent.m_Childs.Count - 1)
        return m_Parent.GetNextSiblingUp();
    else
        return m_Parent.m_Childs[m_Index + 1];
}

遍历算法：深度优先遍历

1. GetNext()：

   • 如果有子节点，返回第一个子节点
   • 否则，查找下一个兄弟节点或回溯到祖先

2. GetNextSiblingUp()：

   • 如果没有父节点，返回 null（遍历结束）
   • 如果是父节点的最后一个子节点，递归向上查找
   • 否则，返回下一个兄弟节点

遍历示例：

// 遍历整个树
PolyNode node = polyTree.GetFirst();
while (node != null)
{
    Console.WriteLine($"轮廓顶点数: {node.Contour.Count}, IsHole: {node.IsHole}");
    node = node.GetNext();
}

3.3 PolyTree 类

PolyTree 继承自 PolyNode，作为多边形树的根节点。

3.3.1 类定义

public class PolyTree : PolyNode
{
    internal List<PolyNode> m_AllPolys = new List<PolyNode>();

    public void Clear() 
    {
        for (int i = 0; i < m_AllPolys.Count; i++)
            m_AllPolys[i] = null;
        m_AllPolys.Clear(); 
        m_Childs.Clear(); 
    }
    
    public PolyNode GetFirst()
    {
        if (m_Childs.Count > 0)
            return m_Childs[0];
        else
            return null;
    }

    public int Total
    {
        get 
        { 
            int result = m_AllPolys.Count;
            //with negative offsets, ignore the hidden outer polygon ...
            if (result > 0 && m_Childs[0] != m_AllPolys[0]) result--;
            return result;
        }
    }
}

3.3.2 m_AllPolys 列表

m_AllPolys 存储树中所有 PolyNode 的扁平列表，便于快速访问：

// 在 BuildResult2 方法中填充
polytree.m_AllPolys.Capacity = m_PolyOuts.Count;
for (int i = 0; i < m_PolyOuts.Count; i++)
{
    // ... 创建 PolyNode ...
    PolyNode pn = new PolyNode();
    polytree.m_AllPolys.Add(pn);
    // ...
}

3.3.3 Clear 方法

public void Clear() 
{
    for (int i = 0; i < m_AllPolys.Count; i++)
        m_AllPolys[i] = null;  // 帮助垃圾回收
    m_AllPolys.Clear(); 
    m_Childs.Clear(); 
}

设计考虑：显式将引用设为 null 可以帮助垃圾回收器更快回收内存。

3.3.4 GetFirst 方法

public PolyNode GetFirst()
{
    if (m_Childs.Count > 0)
        return m_Childs[0];
    else
        return null;
}

返回第一个顶级多边形（外轮廓），用于开始遍历。

3.3.5 Total 属性

public int Total
{
    get 
    { 
        int result = m_AllPolys.Count;
        //with negative offsets, ignore the hidden outer polygon ...
        if (result > 0 && m_Childs[0] != m_AllPolys[0]) result--;
        return result;
    }
}

特殊处理：负偏移可能会产生一个隐藏的外部多边形，需要从计数中排除。

3.4 Path 和 Paths 类型别名

3.4.1 定义

using Path = List<IntPoint>;
using Paths = List<List<IntPoint>>;

3.4.2 Path 的使用模式

// 创建正方形
Path CreateSquare(int size)
{
    Path square = new Path(4);  // 预分配容量
    square.Add(new IntPoint(0, 0));
    square.Add(new IntPoint(size, 0));
    square.Add(new IntPoint(size, size));
    square.Add(new IntPoint(0, size));
    return square;
}

// 创建圆形近似
Path CreateCircle(int centerX, int centerY, int radius, int segments = 36)
{
    Path circle = new Path(segments);
    double angleStep = 2 * Math.PI / segments;
    for (int i = 0; i < segments; i++)
    {
        double angle = i * angleStep;
        circle.Add(new IntPoint(
            centerX + (int)(radius * Math.Cos(angle)),
            centerY + (int)(radius * Math.Sin(angle))
        ));
    }
    return circle;
}

3.4.3 Paths 的使用模式

// 创建带孔的矩形
Paths CreateRectWithHole()
{
    Paths result = new Paths(2);  // 预分配：1个外轮廓 + 1个孔
    
    // 外轮廓（逆时针）
    Path outer = new Path();
    outer.Add(new IntPoint(0, 0));
    outer.Add(new IntPoint(200, 0));
    outer.Add(new IntPoint(200, 200));
    outer.Add(new IntPoint(0, 200));
    result.Add(outer);
    
    // 孔洞（顺时针）
    Path hole = new Path();
    hole.Add(new IntPoint(50, 50));
    hole.Add(new IntPoint(50, 150));
    hole.Add(new IntPoint(150, 150));
    hole.Add(new IntPoint(150, 50));
    result.Add(hole);
    
    return result;
}

3.5 PolyTree 与 Paths 的转换

Clipper 提供了在两种表示之间转换的静态方法：

3.5.1 PolyTreeToPaths

public static Paths PolyTreeToPaths(PolyTree polytree)
{
    Paths result = new Paths();
    result.Capacity = polytree.Total;
    AddPolyNodeToPaths(polytree, NodeType.ntAny, result);
    return result;
}

internal static void AddPolyNodeToPaths(PolyNode polynode, NodeType nt, Paths paths)
{
    bool match = true;
    switch (nt)
    {
        case NodeType.ntOpen: return;  // 跳过开放路径
        case NodeType.ntClosed: match = !polynode.IsOpen; break;
        default: break;  // ntAny 匹配所有
    }

    if (polynode.m_polygon.Count > 0 && match)
        paths.Add(polynode.m_polygon);
    
    foreach (PolyNode pn in polynode.Childs)
        AddPolyNodeToPaths(pn, nt, paths);
}

NodeType 枚举：

internal enum NodeType { ntAny, ntOpen, ntClosed };

3.5.2 OpenPathsFromPolyTree

提取所有开放路径：

public static Paths OpenPathsFromPolyTree(PolyTree polytree)
{
    Paths result = new Paths();
    result.Capacity = polytree.ChildCount;
    for (int i = 0; i < polytree.ChildCount; i++)
        if (polytree.Childs[i].IsOpen)
            result.Add(polytree.Childs[i].m_polygon);
    return result;
}

3.5.3 ClosedPathsFromPolyTree

提取所有闭合路径：

public static Paths ClosedPathsFromPolyTree(PolyTree polytree)
{
    Paths result = new Paths();
    result.Capacity = polytree.Total;
    AddPolyNodeToPaths(polytree, NodeType.ntClosed, result);
    return result;
}

3.6 树形结构的优势

3.6.1 层次关系保留

PolyTree 保留了多边形之间的包含关系：

原始多边形：
┌────────────────────┐
│  外轮廓 A          │
│  ┌──────────────┐  │
│  │  孔洞 A1     │  │
│  │  ┌────────┐  │  │
│  │  │岛屿A1a │  │  │
│  │  └────────┘  │  │
│  └──────────────┘  │
└────────────────────┘

PolyTree 结构：
Root
└── A (IsHole=false)
    └── A1 (IsHole=true)
        └── A1a (IsHole=false)

3.6.2 使用场景

场景	推荐格式	原因
简单裁剪	Paths	足够且高效
需要孔洞信息	PolyTree	保留层次关系
渲染带孔多边形	PolyTree	需要区分外轮廓和孔
进一步布尔运算	Paths	可直接作为输入
SVG 导出	PolyTree	便于生成正确的路径结构

3.6.3 遍历示例

void PrintPolyTree(PolyTree tree)
{
    PrintNode(tree, 0);
}

void PrintNode(PolyNode node, int depth)
{
    string indent = new string(' ', depth * 2);
    
    if (node.Contour.Count > 0)
    {
        string type = node.IsHole ? "孔洞" : "外轮廓";
        string open = node.IsOpen ? " (开放)" : "";
        Console.WriteLine($"{indent}{type}: {node.Contour.Count}个顶点{open}");
    }
    
    foreach (var child in node.Childs)
    {
        PrintNode(child, depth + 1);
    }
}

// 使用
Clipper clipper = new Clipper();
clipper.AddPaths(subjects, PolyType.ptSubject, true);
clipper.AddPaths(clips, PolyType.ptClip, true);

PolyTree result = new PolyTree();
clipper.Execute(ClipType.ctIntersection, result);

PrintPolyTree(result);

3.7 BuildResult 与 BuildResult2

Clipper 内部使用两个方法构建结果：

3.7.1 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);
    }
}

流程：

1. 清空并预分配结果容器
2. 遍历所有输出记录（OutRec）
3. 跳过空记录和少于2个点的记录
4. 将环形链表转换为 Path 列表

3.7.2 BuildResult2（构建 PolyTree）

private void BuildResult2(PolyTree polytree)
{
    polytree.Clear();

    // 添加每个输出多边形到 polytree
    polytree.m_AllPolys.Capacity = m_PolyOuts.Count;
    for (int i = 0; i < m_PolyOuts.Count; i++)
    {
        OutRec outRec = m_PolyOuts[i];
        int cnt = PointCount(outRec.Pts);
        if ((outRec.IsOpen && cnt < 2) || (!outRec.IsOpen && cnt < 3)) 
            continue;
        
        FixHoleLinkage(outRec);
        PolyNode pn = new PolyNode();
        polytree.m_AllPolys.Add(pn);
        outRec.PolyNode = pn;
        pn.m_polygon.Capacity = cnt;
        
        OutPt op = outRec.Pts.Prev;
        for (int j = 0; j < cnt; j++)
        {
            pn.m_polygon.Add(op.Pt);
            op = op.Prev;
        }
    }

    // 修复 PolyNode 链接
    polytree.m_Childs.Capacity = m_PolyOuts.Count;
    for (int i = 0; i < m_PolyOuts.Count; i++)
    {
        OutRec outRec = m_PolyOuts[i];
        if (outRec.PolyNode == null) continue;
        else if (outRec.IsOpen)
        {
            outRec.PolyNode.IsOpen = true;
            polytree.AddChild(outRec.PolyNode);
        }
        else if (outRec.FirstLeft != null && 
            outRec.FirstLeft.PolyNode != null)
            outRec.FirstLeft.PolyNode.AddChild(outRec.PolyNode);
        else
            polytree.AddChild(outRec.PolyNode);
    }
}

流程：

1. 第一遍：创建所有 PolyNode 并填充顶点
2. 第二遍：建立父子关系
   • 开放路径直接添加到根
   • 有 FirstLeft 的添加到其父节点
   • 其他添加到根节点

3.8 面积和方向计算

3.8.1 Area 方法

public static double Area(Path poly)
{
    int cnt = (int)poly.Count;
    if (cnt < 3) return 0;
    double a = 0;
    for (int i = 0, j = cnt - 1; i < cnt; ++i)
    {
        a += ((double)poly[j].X + poly[i].X) * 
             ((double)poly[j].Y - poly[i].Y);
        j = i;
    }
    return -a * 0.5;
}

算法：使用鞋带公式（Shoelace formula）计算有符号面积。

数学公式：

A = (1/2) * |Σ(x[i] * y[i+1] - x[i+1] * y[i])|

简化形式（代码使用）：

A = -(1/2) * Σ((x[j] + x[i]) * (y[j] - y[i]))

3.8.2 Orientation 方法

public static bool Orientation(Path poly)
{
    return Area(poly) >= 0;
}

返回值：

• true：逆时针方向（正面积）
• false：顺时针方向（负面积）

3.8.3 ReversePaths 方法

public static void ReversePaths(Paths polys)
{
    foreach (var poly in polys) 
    { 
        poly.Reverse(); 
    }
}

反转所有路径的方向。

3.9 本章小结

本章详细分析了 Clipper1 的多边形表示系统：

1. PolyNode：

   • 多边形树的基本节点
   • 通过层级判断是否为孔洞
   • 支持深度优先遍历

2. PolyTree：

   • 继承自 PolyNode 的根节点
   • 维护所有节点的扁平列表
   • 提供遍历起点和节点计数

3. Path 和 Paths：

   • 简单的列表类型别名
   • 适用于不需要层次信息的场景

4. 转换方法：

   • PolyTreeToPaths：树形转扁平
   • OpenPathsFromPolyTree：提取开放路径
   • ClosedPathsFromPolyTree：提取闭合路径

5. 面积和方向：

   • Area：使用鞋带公式计算有符号面积
   • Orientation：判断路径方向
   • ReversePaths：反转路径方向

理解这些数据结构对于正确使用 Clipper 的结果至关重要，特别是在需要处理复杂多边形（带孔洞或多层嵌套）的场景中。

---

上一章：核心数据结构 | 返回目录 | 下一章：枚举类型与常量