第3章：路径与多边形表示 - Path64、PathD、Paths64、PathsD

3.1 概述

在 Clipper2 中，路径（Path）是点的有序集合，用于表示多边形轮廓或开放线段。与 Clipper1 使用类型别名不同，Clipper2 定义了独立的类，继承自 List<T>。

3.2 Path64 类

3.2.1 类定义

public class Path64 : List<Point64> 
{
    public Path64() : base() { }
    public Path64(int capacity = 0) : base(capacity) { }
    public Path64(IEnumerable<Point64> path) : base(path) { }
    
    public override string ToString()
    {
        return string.Join(", ", this);
    }
}

3.2.2 设计特点

1. 继承 List：直接获得所有列表操作方法
2. 多个构造函数：支持空构造、预分配容量、从集合初始化
3. 自定义 ToString：方便调试和日志输出

3.2.3 使用示例

// 创建空路径
Path64 path1 = new Path64();

// 预分配容量
Path64 path2 = new Path64(100);

// 从数组创建
Path64 path3 = new Path64(new Point64[] {
    new Point64(0, 0),
    new Point64(100, 0),
    new Point64(100, 100),
    new Point64(0, 100)
});

// 使用集合初始化器
Path64 path4 = new Path64 {
    new Point64(0, 0),
    new Point64(100, 0),
    new Point64(100, 100)
};

// 输出: "0,0 , 100,0 , 100,100 , 0,100 "
Console.WriteLine(path3);

3.2.4 与 Clipper1 的对比

// Clipper1 方式（类型别名）
using Path = List<IntPoint>;
Path path = new Path();

// Clipper2 方式（独立类）
Path64 path = new Path64();

独立类的优势：

• 可以添加自定义方法
• 更清晰的类型语义
• 方便扩展功能

3.3 PathD 类

3.3.1 类定义

public class PathD : List<PointD>
{
    public PathD() : base() { }
    public PathD(int capacity = 0) : base(capacity) { }
    public PathD(IEnumerable<PointD> path) : base(path) { }
    
    public string ToString(int precision = 2)
    {
        return string.Join(", ", ConvertAll(x => x.ToString(precision)));
    }
}

3.3.2 带精度的 ToString

PathD path = new PathD {
    new PointD(0.123, 0.456),
    new PointD(1.234, 5.678)
};

// 默认2位小数: "0.12,0.46, 1.23,5.68"
Console.WriteLine(path.ToString());

// 4位小数: "0.1230,0.4560, 1.2340,5.6780"
Console.WriteLine(path.ToString(4));

3.4 Paths64 和 PathsD 类

3.4.1 Paths64 定义

public class Paths64 : List<Path64>
{
    public Paths64() : base() { }
    public Paths64(int capacity = 0) : base(capacity) { }
    public Paths64(IEnumerable<Path64> paths) : base(paths) { }
    
    public override string ToString()
    {
        return string.Join(Environment.NewLine, this);
    }
}

3.4.2 PathsD 定义

public class PathsD : List<PathD>
{
    public PathsD() : base() { }
    public PathsD(int capacity = 0) : base(capacity) { }
    public PathsD(IEnumerable<PathD> paths) : base(paths) { }
    
    public string ToString(int precision = 2)
    {
        return string.Join(Environment.NewLine, 
            ConvertAll(x => x.ToString(precision)));
    }
}

3.4.3 使用示例

// 创建多边形集合
Paths64 paths = new Paths64 {
    new Path64 {
        new Point64(0, 0),
        new Point64(100, 0),
        new Point64(100, 100),
        new Point64(0, 100)
    },
    new Path64 {
        new Point64(25, 25),
        new Point64(75, 25),
        new Point64(75, 75),
        new Point64(25, 75)
    }
};

// 每个路径一行
Console.WriteLine(paths);

3.5 路径创建工具方法

3.5.1 MakePath 方法

Clipper2 提供了便捷的路径创建方法：

// 从整数数组创建 Path64
public static Path64 MakePath(int[] arr)
{
    int len = arr.Length / 2;
    Path64 p = new Path64(len);
    for (int i = 0; i < len; i++)
        p.Add(new Point64(arr[i * 2], arr[i * 2 + 1]));
    return p;
}

// 从 long 数组创建 Path64
public static Path64 MakePath(long[] arr)
{
    int len = arr.Length / 2;
    Path64 p = new Path64(len);
    for (int i = 0; i < len; i++)
        p.Add(new Point64(arr[i * 2], arr[i * 2 + 1]));
    return p;
}

// 从 double 数组创建 PathD
public static PathD MakePath(double[] arr)
{
    int len = arr.Length / 2;
    PathD p = new PathD(len);
    for (int i = 0; i < len; i++)
        p.Add(new PointD(arr[i * 2], arr[i * 2 + 1]));
    return p;
}

3.5.2 使用示例

// 简洁的路径创建
Path64 square = Clipper.MakePath(new long[] {
    0, 0, 100, 0, 100, 100, 0, 100
});

PathD triangle = Clipper.MakePath(new double[] {
    0.0, 0.0, 50.0, 100.0, 100.0, 0.0
});

3.5.3 带 Z 坐标的 MakePath

#if USINGZ
public static Path64 MakePathZ(long[] arr)
{
    int len = arr.Length / 3;
    Path64 p = new Path64(len);
    for (int i = 0; i < len; i++)
        p.Add(new Point64(arr[i * 3], arr[i * 3 + 1], arr[i * 3 + 2]));
    return p;
}

public static PathD MakePathZ(double[] arr)
{
    int len = arr.Length / 3;
    PathD p = new PathD(len);
    for (int i = 0; i < len; i++)
        p.Add(new PointD(arr[i * 3], arr[i * 3 + 1], (long)arr[i * 3 + 2]));
    return p;
}
#endif

3.6 路径类型转换

3.6.1 Path64 和 PathD 互转

// PathD 转 Path64（无缩放）
public static Path64 Path64(PathD path)
{
    Path64 result = new Path64(path.Count);
    foreach (PointD pt in path)
        result.Add(new Point64(pt));
    return result;
}

// Path64 转 PathD（无缩放）
public static PathD PathD(Path64 path)
{
    PathD result = new PathD(path.Count);
    foreach (Point64 pt in path)
        result.Add(new PointD(pt));
    return result;
}

// Paths64 转 PathsD
public static PathsD PathsD(Paths64 paths)
{
    PathsD result = new PathsD(paths.Count);
    foreach (Path64 path in paths)
        result.Add(PathD(path));
    return result;
}

// PathsD 转 Paths64
public static Paths64 Paths64(PathsD paths)
{
    Paths64 result = new Paths64(paths.Count);
    foreach (PathD path in paths)
        result.Add(Path64(path));
    return result;
}

3.6.2 带缩放的转换

// PathD 转 Path64 并缩放
public static Path64 ScalePath64(PathD path, double scale)
{
    int cnt = path.Count;
    Path64 res = new Path64(cnt);
    foreach (PointD pt in path)
        res.Add(new Point64(pt, scale));
    return res;
}

// Paths64 缩放
public static Paths64 ScalePaths64(PathsD paths, double scale)
{
    int cnt = paths.Count;
    Paths64 res = new Paths64(cnt);
    foreach (PathD path in paths)
        res.Add(ScalePath64(path, scale));
    return res;
}

// Path64 转 PathD 并缩放
public static PathD ScalePathD(Path64 path, double scale)
{
    int cnt = path.Count;
    PathD res = new PathD(cnt);
    foreach (Point64 pt in path)
        res.Add(new PointD(pt, scale));
    return res;
}

// Paths64 转 PathsD 并缩放
public static PathsD ScalePathsD(Paths64 paths, double scale)
{
    int cnt = paths.Count;
    PathsD res = new PathsD(cnt);
    foreach (Path64 path in paths)
        res.Add(ScalePathD(path, scale));
    return res;
}

3.6.3 同类型缩放

// Path64 缩放（返回新路径）
public static Path64 ScalePath(Path64 path, double scale)
{
    if (InternalClipper.IsAlmostZero(scale - 1)) return path;
    Path64 result = new Path64(path.Count);
#if USINGZ
    foreach (Point64 pt in path)
        result.Add(new Point64(pt.X * scale, pt.Y * scale, pt.Z));
#else
    foreach (Point64 pt in path)
        result.Add(new Point64(pt.X * scale, pt.Y * scale));
#endif
    return result;
}

// PathD 缩放
public static PathD ScalePath(PathD path, double scale)
{
    if (InternalClipper.IsAlmostZero(scale - 1)) return path;
    PathD result = new PathD(path.Count);
    foreach (PointD pt in path)
        result.Add(new PointD(pt, scale));
    return result;
}

优化：当缩放因子接近 1 时，直接返回原路径避免不必要的复制。

3.7 路径操作方法

3.7.1 路径平移

// Path64 平移
public static Path64 TranslatePath(Path64 path, long dx, long dy)
{
    Path64 result = new Path64(path.Count);
    foreach (Point64 pt in path)
        result.Add(new Point64(pt.X + dx, pt.Y + dy));
    return result;
}

// 多路径平移
public static Paths64 TranslatePaths(Paths64 paths, long dx, long dy)
{
    Paths64 result = new Paths64(paths.Count);
    foreach (Path64 path in paths)
        result.Add(OffsetPath(path, dx, dy));
    return result;
}

// PathD 平移
public static PathD TranslatePath(PathD path, double dx, double dy)
{
    PathD result = new PathD(path.Count);
    foreach (PointD pt in path)
        result.Add(new PointD(pt.x + dx, pt.y + dy));
    return result;
}

3.7.2 路径反转

// 反转 Path64
public static Path64 ReversePath(Path64 path)
{
    Path64 result = new Path64(path);
    result.Reverse();
    return result;
}

// 反转 PathD
public static PathD ReversePath(PathD path)
{
    PathD result = new PathD(path);
    result.Reverse();
    return result;
}

// 反转多个路径
public static Paths64 ReversePaths(Paths64 paths)
{
    Paths64 result = new Paths64(paths.Count);
    foreach (Path64 t in paths)
        result.Add(ReversePath(t));
    return result;
}

3.7.3 去除重复点

// 去除整数路径中的重复点
public static Path64 StripDuplicates(Path64 path, bool isClosedPath)
{
    int cnt = path.Count;
    Path64 result = new Path64(cnt);
    if (cnt == 0) return result;
    
    Point64 lastPt = path[0];
    result.Add(lastPt);
    for (int i = 1; i < cnt; i++)
        if (lastPt != path[i])
        {
            lastPt = path[i];
            result.Add(lastPt);
        }
    
    // 闭合路径：检查首尾是否重复
    if (isClosedPath && lastPt == result[0])
        result.RemoveAt(result.Count - 1);
    
    return result;
}

// 去除近距离重复点（浮点版本）
public static PathD StripNearDuplicates(PathD path,
    double minEdgeLenSqrd, bool isClosedPath)
{
    int cnt = path.Count;
    PathD result = new PathD(cnt);
    if (cnt == 0) return result;
    
    PointD lastPt = path[0];
    result.Add(lastPt);
    for (int i = 1; i < cnt; i++)
        if (!PointsNearEqual(lastPt, path[i], minEdgeLenSqrd))
        {
            lastPt = path[i];
            result.Add(lastPt);
        }

    if (isClosedPath && PointsNearEqual(lastPt, result[0], minEdgeLenSqrd))
    {
        result.RemoveAt(result.Count - 1);
    }

    return result;
}

3.7.4 去除共线点

public static Path64 TrimCollinear(Path64 path, bool isOpen = false)
{
    int len = path.Count;
    int i = 0;
    
    if (!isOpen)
    {
        // 从路径起点开始查找非共线点
        while (i < len - 1 && 
               InternalClipper.IsCollinear(path[len - 1], path[i], path[i + 1])) 
            i++;
        // 从路径终点开始查找非共线点
        while (i < len - 1 && 
               InternalClipper.IsCollinear(path[len - 2], path[len - 1], path[i])) 
            len--;
    }

    if (len - i < 3)
    {
        if (!isOpen || len < 2 || path[0] == path[1])
            return new Path64();
        return path;
    }

    Path64 result = new Path64(len - i);
    Point64 last = path[i];
    result.Add(last);
    
    for (i++; i < len - 1; i++)
    {
        if (InternalClipper.IsCollinear(last, path[i], path[i + 1])) 
            continue;
        last = path[i];
        result.Add(last);
    }

    if (isOpen)
        result.Add(path[len - 1]);
    else if (!InternalClipper.IsCollinear(last, path[len - 1], result[0]))
        result.Add(path[len - 1]);
    else
    {
        // 继续检查结果路径中的共线点
        while (result.Count > 2 && InternalClipper.IsCollinear(
                 result[result.Count - 1], result[result.Count - 2], result[0]))
        {
            result.RemoveAt(result.Count - 1);
        }
        if (result.Count < 3)
            result.Clear();
    }
    return result;
}

3.8 路径简化算法

3.8.1 Ramer-Douglas-Peucker 算法

这是经典的线段简化算法：

internal static void RDP(Path64 path, int begin, int end, 
    double epsSqrd, List<bool> flags)
{
    while (true)
    {
        int idx = 0;
        double max_d = 0;
        
        // 跳过首尾相同的点
        while (end > begin && path[begin] == path[end]) 
            flags[end--] = false;
        
        // 找到距离首尾连线最远的点
        for (int i = begin + 1; i < end; ++i)
        {
            double d = PerpendicDistFromLineSqrd(path[i], path[begin], path[end]);
            if (d <= max_d) continue;
            max_d = d;
            idx = i;
        }

        // 如果最大距离小于阈值，返回
        if (max_d <= epsSqrd) return;
        
        // 保留该点，递归处理两侧
        flags[idx] = true;
        if (idx > begin + 1) RDP(path, begin, idx, epsSqrd, flags);
        if (idx < end - 1)
        {
            begin = idx;
            continue;  // 尾递归优化
        }
        break;
    }
}

public static Path64 RamerDouglasPeucker(Path64 path, double epsilon)
{
    int len = path.Count;
    if (len < 5) return path;
    
    List<bool> flags = new List<bool>(new bool[len]) 
    { 
        [0] = true, 
        [len - 1] = true 
    };
    
    RDP(path, 0, len - 1, Sqr(epsilon), flags);
    
    Path64 result = new Path64(len);
    for (int i = 0; i < len; ++i)
        if (flags[i]) result.Add(path[i]);
    return result;
}

3.8.2 SimplifyPath 方法

另一种简化算法，基于删除对整体形状影响最小的点：

public static Path64 SimplifyPath(Path64 path,
    double epsilon, bool isClosedPath = true)
{
    int len = path.Count, high = len - 1;
    double epsSqr = Sqr(epsilon);
    if (len < 4) return path;

    bool[] flags = new bool[len];
    double[] dsq = new double[len];  // 存储每个点到相邻点连线的距离
    int curr = 0;

    // 计算每个点的重要性（到相邻点连线的距离）
    if (isClosedPath)
    {
        dsq[0] = PerpendicDistFromLineSqrd(path[0], path[high], path[1]);
        dsq[high] = PerpendicDistFromLineSqrd(path[high], path[0], path[high - 1]);
    }
    else
    {
        dsq[0] = double.MaxValue;
        dsq[high] = double.MaxValue;
    }

    for (int i = 1; i < high; ++i)
        dsq[i] = PerpendicDistFromLineSqrd(path[i], path[i - 1], path[i + 1]);

    // 迭代删除重要性最低的点
    for (; ; )
    {
        // 找到下一个需要删除的点
        if (dsq[curr] > epsSqr)
        {
            int start = curr;
            do {
                curr = GetNext(curr, high, ref flags);
            } while (curr != start && dsq[curr] > epsSqr);
            if (curr == start) break;
        }

        int prev = GetPrior(curr, high, ref flags);
        int next = GetNext(curr, high, ref flags);
        if (next == prev) break;

        // 删除当前点并更新相邻点的距离
        // ... 省略详细逻辑
    }
    
    // 构建结果
    Path64 result = new Path64(len);
    for (int i = 0; i < len; i++)
        if (!flags[i]) result.Add(path[i]);
    return result;
}

3.9 路径面积计算

3.9.1 Shoelace 公式

public static double Area(Path64 path)
{
    // https://en.wikipedia.org/wiki/Shoelace_formula
    double a = 0.0;
    int cnt = path.Count;
    if (cnt < 3) return 0.0;
    
    Point64 prevPt = path[cnt - 1];
    foreach (Point64 pt in path)
    {
        a += (double) (prevPt.Y + pt.Y) * (prevPt.X - pt.X);
        prevPt = pt;
    }
    return a * 0.5;
}

Shoelace 公式（鞋带公式）：

Area = 0.5 * |Σ(x[i]*y[i+1] - x[i+1]*y[i])|

3.9.2 判断路径方向

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool IsPositive(Path64 poly)
{
    return Area(poly) >= 0;
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool IsPositive(PathD poly)
{
    return Area(poly) >= 0;
}

• 正面积：逆时针方向（在 Y 轴向下的坐标系中）
• 负面积：顺时针方向

3.10 本章小结

本章详细介绍了 Clipper2 的路径和多边形数据结构：

1. 四种路径类型：Path64、PathD、Paths64、PathsD
2. 继承设计：直接继承 List，获得所有列表功能
3. 便捷创建：MakePath 等工厂方法
4. 类型转换：Path64 ⇔ PathD，带/不带缩放
5. 路径操作：平移、反转、去重、简化
6. 面积计算：基于 Shoelace 公式

这些路径结构是后续所有裁剪、偏移等操作的基础。

上一章：核心数据结构 | 返回目录 | 下一章：矩形边界