Path64、PathD、Paths64、PathsD如何表示路径与多边形？
摘要：layout: default title: 第3章：路径与多边形表示 - Path64、PathD、Paths64、PathsD 第3章：路径与多边形表示 - Path64、PathD、Paths64、PathsD 3.1 概述 在 Cl
第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 设计特点
继承 List：直接获得所有列表操作方法
多个构造函数：支持空构造、预分配容量、从集合初始化
自定义 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 的路径和多边形数据结构：
四种路径类型：Path64、PathD、Paths64、PathsD
继承设计：直接继承 List，获得所有列表功能
便捷创建：MakePath 等工厂方法
类型转换：Path64 ⇔ PathD，带/不带缩放
路径操作：平移、反转、去重、简化
面积计算：基于 Shoelace 公式
这些路径结构是后续所有裁剪、偏移等操作的基础。
上一章：核心数据结构 | 返回目录 | 下一章：矩形边界