第二章 Clipper2核心数据结构(C#版)
2.1 引言
在使用Clipper2进行几何运算之前,深入理解其核心数据结构是非常必要的。Clipper2的数据结构设计精巧而高效,它们构成了整个库的基础。本章将详细介绍C#版本中的Point(点)、Path(路径)、Paths(路径集合)、Rect(矩形)以及PolyTree(多边形树)等核心数据结构,并探讨它们的使用方法和最佳实践。
2.2 点(Point)结构
点是最基本的几何元素,Clipper2提供了两种点类型来满足不同的需求。
2.2.1 Point64结构
Point64是Clipper2的核心点类型,使用64位有符号整数存储坐标值。
public struct Point64
{
public long X;
public long Y;
// 构造函数
public Point64(long x, long y)
{
X = x;
Y = y;
}
// 从浮点数创建(自动四舍五入)
public Point64(double x, double y)
{
X = (long)Math.Round(x);
Y = (long)Math.Round(y);
}
// 运算符重载
public static bool operator ==(Point64 lhs, Point64 rhs);
public static bool operator !=(Point64 lhs, Point64 rhs);
public static Point64 operator +(Point64 lhs, Point64 rhs);
public static Point64 operator -(Point64 lhs, Point64 rhs);
}
基本使用
using Clipper2Lib;
class Point64Example
{
static void Main()
{
// 创建点
Point64 p1 = new Point64(100, 200);
Point64 p2 = new Point64(300, 400);
// 点的加法
Point64 sum = new Point64(p1.X + p2.X, p1.Y + p2.Y); // (400, 600)
// 点的减法
Point64 diff = new Point64(p2.X - p1.X, p2.Y - p1.Y); // (200, 200)
// 判断相等
bool equal = (p1 == p2); // false
// 从浮点数创建(自动四舍五入)
Point64 fromDouble = new Point64(100.7, 200.3); // (101, 200)
Console.WriteLine($"p1: ({p1.X}, {p1.Y})");
Console.WriteLine($"p2: ({p2.X}, {p2.Y})");
Console.WriteLine($"相等: {equal}");
}
}
2.2.2 PointD结构
PointD使用双精度浮点数存储坐标,适用于需要浮点数精度的场景。
public struct PointD
{
public double X;
public double Y;
public PointD(double x, double y)
{
X = x;
Y = y;
}
// 从Point64转换
public PointD(Point64 pt)
{
X = pt.X;
Y = pt.Y;
}
}
使用示例
using Clipper2Lib;
class PointDExample
{
static void Main()
{
// 创建浮点数点
PointD pd1 = new PointD(10.5, 20.3);
PointD pd2 = new PointD(30.7, 40.9);
// 从整数点转换
Point64 intPt = new Point64(100, 200);
PointD fromInt = new PointD(intPt); // (100.0, 200.0)
Console.WriteLine($"pd1: ({pd1.X}, {pd1.Y})");
Console.WriteLine($"fromInt: ({fromInt.X}, {fromInt.Y})");
}
}
2.2.3 点的运算与辅助函数
Clipper2提供了丰富的点运算方法:
点与多边形的关系
using Clipper2Lib;
class PointInPolygonExample
{
static void Main()
{
// 创建多边形
Path64 polygon = Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 });
// 判断点是否在多边形内部
Point64 testPoint = new Point64(50, 50);
PointInPolygonResult result = Clipper.PointInPolygon(testPoint, polygon);
// 可能的返回值:
// PointInPolygonResult.IsInside - 点在多边形内部
// PointInPolygonResult.IsOutside - 点在多边形外部
// PointInPolygonResult.IsOn - 点在多边形边界上
Console.WriteLine($"点({testPoint.X}, {testPoint.Y})在多边形中的位置: {result}");
}
}
2.2.4 带Z值的点(可选功能)
在C#版本中,可以使用带Z值的点结构来存储额外的顶点信息:
using Clipper2Lib;
class ZValueExample
{
static void Main()
{
// 在某些版本中,Point64可以包含Z值
// Z值可用于存储顶点ID、高程等信息
// 创建Clipper64并设置Z值回调
Clipper64 clipper = new Clipper64();
// 设置Z值回调函数(当产生新顶点时调用)
clipper.ZCallback = (Point64 e1bot, Point64 e1top,
Point64 e2bot, Point64 e2top,
ref Point64 pt) =>
{
// 自定义Z值计算逻辑
// 例如:使用线性插值
pt = new Point64(pt.X, pt.Y);
};
}
}
Z值的主要用途:
- 存储原始顶点的索引或ID
- 在GIS应用中传递高程信息
- 传递自定义的顶点属性
2.3 路径(Path)结构
路径是一系列有序点的集合,可以表示一个多边形的边界或一条折线。
2.3.1 Path64类型
Path64是Point64的列表(动态数组),继承自List<Point64>。
public class Path64 : List<Point64>
{
public Path64() : base() { }
public Path64(int capacity) : base(capacity) { }
public Path64(IEnumerable<Point64> path) : base(path) { }
}
创建路径
using Clipper2Lib;
class PathCreationExample
{
static void Main()
{
// 方式一:使用MakePath辅助函数(推荐)
Path64 path1 = Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 });
// 创建一个正方形:(0,0) → (100,0) → (100,100) → (0,100)
// 方式二:逐个添加点
Path64 path2 = new Path64();
path2.Add(new Point64(0, 0));
path2.Add(new Point64(100, 0));
path2.Add(new Point64(100, 100));
path2.Add(new Point64(0, 100));
// 方式三:使用集合初始化器
Path64 path3 = new Path64
{
new Point64(0, 0),
new Point64(100, 0),
new Point64(100, 100),
new Point64(0, 100)
};
// 方式四:指定初始容量(提高性能)
Path64 path4 = new Path64(1000); // 预分配1000个点的空间
for (int i = 0; i < 1000; i++)
{
path4.Add(new Point64(i, i));
}
Console.WriteLine($"path1 顶点数: {path1.Count}");
Console.WriteLine($"path2 顶点数: {path2.Count}");
}
}
2.3.2 PathD类型
PathD使用PointD类型,适用于浮点数坐标:
using Clipper2Lib;
class PathDExample
{
static void Main()
{
// 创建浮点数路径
PathD pathD = Clipper.MakePath(new double[] { 0.0, 0.0, 10.5, 0.0, 10.5, 10.5, 0.0, 10.5 });
// 或使用集合初始化器
PathD pathD2 = new PathD
{
new PointD(0.0, 0.0),
new PointD(10.5, 0.0),
new PointD(10.5, 10.5),
new PointD(0.0, 10.5)
};
Console.WriteLine($"pathD 顶点数: {pathD.Count}");
}
}
2.3.3 路径方向(Orientation)
多边形路径的顶点顺序决定了其方向,这在某些填充规则下非常重要。
using Clipper2Lib;
class OrientationExample
{
static void Main()
{
// 判断路径是否为正方向(逆时针)
Path64 path = Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 });
bool isPositive = Clipper.IsPositive(path); // true(逆时针)
// 注意:这是在标准数学坐标系下的定义
// 如果Y轴向下(如屏幕坐标系),方向会相反
Console.WriteLine($"路径是否为正方向: {isPositive}");
// 反转路径方向
Path64 reversed = Clipper.ReversePath(path);
// 原路径:(0,0) → (100,0) → (100,100) → (0,100)
// 反转后:(0,100) → (100,100) → (100,0) → (0,0)
bool isReversedPositive = Clipper.IsPositive(reversed);
Console.WriteLine($"反转后是否为正方向: {isReversedPositive}");
}
}
2.3.4 路径的几何属性
using Clipper2Lib;
class PathPropertiesExample
{
static void Main()
{
// 创建一个正方形
Path64 square = Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 });
// 计算多边形面积
double area = Clipper.Area(square); // 10000.0
Console.WriteLine($"面积: {area}");
// 面积的符号表示方向:
// 正值 - 逆时针(正方向)
// 负值 - 顺时针(负方向)
// 获取路径的轴对齐边界框
Path64 path = Clipper.MakePath(new long[] { 10, 20, 50, 30, 40, 80, 15, 60 });
Rect64 bounds = Clipper.GetBounds(path);
Console.WriteLine($"边界框: Left={bounds.left}, Top={bounds.top}, Right={bounds.right}, Bottom={bounds.bottom}");
}
}
2.3.5 路径简化与处理
using Clipper2Lib;
class PathSimplificationExample
{
static void Main()
{
// 简化路径(使用Douglas-Peucker算法)
PathD complexPath = new PathD();
// 假设这是一条包含很多点的复杂路径
for (int i = 0; i < 100; i++)
{
complexPath.Add(new PointD(i, Math.Sin(i * 0.1) * 10));
}
// 使用给定的容差简化路径
PathsD simplified = Clipper.SimplifyPaths(new PathsD { complexPath }, 2.0);
// 容差为2.0,这会移除对整体形状影响很小的点
Console.WriteLine($"原始点数: {complexPath.Count}");
Console.WriteLine($"简化后点数: {simplified[0].Count}");
}
}
2.3.6 路径的坐标转换
using Clipper2Lib;
class PathTransformExample
{
static void Main()
{
Path64 path = Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 });
// 缩放路径坐标
Paths64 scaled = Clipper.ScalePaths(new Paths64 { path }, 2.0);
// 结果:{(0,0), (200,0), (200,200), (0,200)}
// 平移路径
Paths64 translated = Clipper.TranslatePaths(new Paths64 { path }, 50, 50);
// 结果:{(50,50), (150,50), (150,150), (50,150)}
// Path64与PathD之间的转换
PathsD pathsD = Clipper.Paths64ToPathsD(new Paths64 { path });
Paths64 paths64 = Clipper.PathsDToPaths64(pathsD);
Console.WriteLine($"原始路径第一个点: ({path[0].X}, {path[0].Y})");
Console.WriteLine($"缩放后第一个点: ({scaled[0][0].X}, {scaled[0][0].Y})");
Console.WriteLine($"平移后第一个点: ({translated[0][0].X}, {translated[0][0].Y})");
}
}
2.4 路径集合(Paths)结构
Paths是Path的集合,可以表示多个独立的多边形,也可以表示一个带有孔洞的复杂多边形。
2.4.1 Paths64类型
public class Paths64 : List<Path64>
{
public Paths64() : base() { }
public Paths64(int capacity) : base(capacity) { }
public Paths64(IEnumerable<Path64> paths) : base(paths) { }
}
2.4.2 创建Paths
using Clipper2Lib;
class PathsCreationExample
{
static void Main()
{
// 创建包含多个多边形的Paths
Paths64 paths = new Paths64();
paths.Add(Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 })); // 第一个多边形
paths.Add(Clipper.MakePath(new long[] { 200, 0, 300, 0, 300, 100, 200, 100 })); // 第二个多边形
// 创建带孔洞的多边形
Paths64 polygonWithHole = new Paths64();
// 外边界(逆时针)
polygonWithHole.Add(Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 }));
// 孔洞(顺时针)
polygonWithHole.Add(Clipper.MakePath(new long[] { 25, 25, 25, 75, 75, 75, 75, 25 }));
Console.WriteLine($"paths 包含 {paths.Count} 个多边形");
Console.WriteLine($"polygonWithHole 包含 {polygonWithHole.Count} 个路径");
}
}
2.4.3 Paths的几何属性
using Clipper2Lib;
class PathsPropertiesExample
{
static void Main()
{
Paths64 paths = new Paths64();
paths.Add(Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 }));
paths.Add(Clipper.MakePath(new long[] { 25, 25, 25, 75, 75, 75, 75, 25 })); // 孔洞
// 计算总面积
double totalArea = Clipper.Area(paths);
// 如果包含孔洞(顺时针路径),它们的面积会被减去
Console.WriteLine($"总面积: {totalArea}");
// 获取边界框
Rect64 bounds = Clipper.GetBounds(paths);
Console.WriteLine($"边界框: ({bounds.left}, {bounds.top}) - ({bounds.right}, {bounds.bottom})");
}
}
2.4.4 Paths的转换
using Clipper2Lib;
class PathsConversionExample
{
static void Main()
{
Paths64 paths = new Paths64();
paths.Add(Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 }));
// 缩放所有路径
Paths64 scaled = Clipper.ScalePaths(paths, 2.0);
// 平移所有路径
Paths64 translated = Clipper.TranslatePaths(paths, 100, 100);
// Paths64与PathsD之间的转换
PathsD pathsD = Clipper.Paths64ToPathsD(paths);
Paths64 backToInt = Clipper.PathsDToPaths64(pathsD);
Console.WriteLine($"缩放后顶点: ({scaled[0][0].X}, {scaled[0][0].Y})");
Console.WriteLine($"平移后顶点: ({translated[0][0].X}, {translated[0][0].Y})");
}
}
2.5 矩形(Rect)结构
矩形是一种特殊的多边形,在裁剪操作中经常使用。Clipper2提供了专门的矩形类型和优化的矩形裁剪算法。
2.5.1 Rect64类型
public struct Rect64
{
public long left;
public long top;
public long right;
public long bottom;
public Rect64(long l, long t, long r, long b)
{
left = l;
top = t;
right = r;
bottom = b;
}
// 常用属性
public long Width => right - left;
public long Height => bottom - top;
public bool IsEmpty => bottom <= top || right <= left;
}
2.5.2 矩形操作
using Clipper2Lib;
class RectOperationsExample
{
static void Main()
{
// 创建矩形
Rect64 rect1 = new Rect64(0, 0, 100, 100);
Rect64 rect2 = new Rect64(50, 50, 150, 150);
// 获取属性
long width = rect1.Width; // 100
long height = rect1.Height; // 100
Console.WriteLine($"矩形宽度: {width}");
Console.WriteLine($"矩形高度: {height}");
Console.WriteLine($"矩形是否为空: {rect1.IsEmpty}");
// 使用GetBounds函数获取路径的边界矩形
Path64 path = Clipper.MakePath(new long[] { 10, 20, 50, 30, 40, 80, 15, 60 });
Rect64 bounds = Clipper.GetBounds(path);
Console.WriteLine($"边界框: ({bounds.left}, {bounds.top}) - ({bounds.right}, {bounds.bottom})");
}
}
2.5.3 矩形裁剪
Clipper2提供了专门优化的矩形裁剪函数,性能优于通用的布尔运算:
using Clipper2Lib;
class RectClipExample
{
static void Main()
{
Paths64 paths = new Paths64();
paths.Add(Clipper.MakePath(new long[] { 0, 0, 200, 0, 200, 200, 0, 200 }));
// 使用矩形裁剪多边形
Rect64 clipRect = new Rect64(50, 50, 150, 150);
// 裁剪闭合多边形
Paths64 result = Clipper.RectClip(clipRect, paths);
Console.WriteLine($"裁剪后包含 {result.Count} 个多边形");
// 裁剪开放折线
Paths64 openPaths = new Paths64();
openPaths.Add(Clipper.MakePath(new long[] { 0, 100, 200, 100 }));
Paths64 clippedLines = Clipper.RectClipLines(clipRect, openPaths);
Console.WriteLine($"裁剪后包含 {clippedLines.Count} 条线段");
}
}
2.6 多边形树(PolyTree)结构
PolyTree是Clipper2中用于表示嵌套多边形层次关系的树形结构。
2.6.1 为什么需要PolyTree
在很多实际应用中,多边形之间存在嵌套关系:
- 一个外边界包含多个孔洞
- 孔洞内部可能又包含岛屿
- 岛屿内部可能还有孔洞…
Paths结构只是一个简单的路径列表,无法表达这种层次关系。PolyTree则以树形结构清晰地表示这些关系。
2.6.2 PolyTree64使用
using Clipper2Lib;
class PolyTreeExample
{
static void Main()
{
Paths64 subject = new Paths64();
subject.Add(Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 }));
subject.Add(Clipper.MakePath(new long[] { 20, 20, 20, 80, 80, 80, 80, 20 })); // 孔洞
Paths64 clip = new Paths64();
clip.Add(Clipper.MakePath(new long[] { 50, 50, 150, 50, 150, 150, 50, 150 }));
// 使用Clipper64类进行布尔运算并输出PolyTree
Clipper64 clipper = new Clipper64();
clipper.AddSubject(subject);
clipper.AddClip(clip);
PolyTree64 tree = new PolyTree64();
Paths64 openPaths = new Paths64();
clipper.Execute(ClipType.Intersection, FillRule.NonZero, tree, openPaths);
// 遍历PolyTree
TraversePolyTree(tree, 0);
}
static void TraversePolyTree(PolyPath64 node, int depth)
{
string indent = new string(' ', depth * 2);
if (node.Polygon != null && node.Polygon.Count > 0)
{
string type = node.IsHole ? "孔洞" : "多边形";
double area = Clipper.Area(node.Polygon);
Console.WriteLine($"{indent}{type}, 顶点数: {node.Polygon.Count}, 面积: {Math.Abs(area)}");
}
// 遍历子节点
for (int i = 0; i < node.Count; i++)
{
TraversePolyTree(node[i], depth + 1);
}
}
}
2.6.3 PolyTree与Paths的转换
using Clipper2Lib;
class PolyTreeConversionExample
{
static void Main()
{
// 执行布尔运算获取PolyTree
Clipper64 clipper = new Clipper64();
// ... 添加多边形 ...
PolyTree64 tree = new PolyTree64();
Paths64 openPaths = new Paths64();
clipper.Execute(ClipType.Union, FillRule.NonZero, tree, openPaths);
// 将PolyTree转换为Paths(丢失层次信息)
Paths64 paths = Clipper.PolyTreeToPaths64(tree);
Console.WriteLine($"转换后路径数量: {paths.Count}");
// 如果只想获取外边界(不包括孔洞内的岛屿)
// 需要自定义遍历逻辑
Paths64 outerBoundaries = new Paths64();
for (int i = 0; i < tree.Count; i++)
{
PolyPath64 child = tree[i];
if (!child.IsHole && child.Polygon != null)
{
outerBoundaries.Add(child.Polygon);
}
}
}
}
2.6.4 判断多边形层次
using Clipper2Lib;
class PolygonHierarchyExample
{
static void ClassifyPaths(PolyPath64 node, Paths64 exteriors, Paths64 holes, int depth = 0)
{
if (node.Polygon != null && node.Polygon.Count > 0)
{
if (depth % 2 == 0)
{
// 深度为偶数(0, 2, 4...)- 外边界
exteriors.Add(node.Polygon);
}
else
{
// 深度为奇数(1, 3, 5...)- 孔洞
holes.Add(node.Polygon);
}
}
for (int i = 0; i < node.Count; i++)
{
ClassifyPaths(node[i], exteriors, holes, depth + 1);
}
}
}
2.7 PathType枚举
PathType枚举用于在Clipper类中指定路径的类型。
public enum PathType { Subject, Clip }
- Subject:主体路径,参与布尔运算的第一个操作数
- Clip:裁剪路径,参与布尔运算的第二个操作数
using Clipper2Lib;
class PathTypeExample
{
static void Main()
{
Clipper64 clipper = new Clipper64();
Path64 path1 = Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 });
Path64 path2 = Clipper.MakePath(new long[] { 50, 50, 150, 50, 150, 150, 50, 150 });
// 使用PathType指定路径类型
clipper.AddPath(path1, PathType.Subject);
clipper.AddPath(path2, PathType.Clip);
// 或者使用便捷方法
clipper.AddSubject(path1);
clipper.AddClip(path2);
}
}
2.8 数据结构的内存管理
2.8.1 C#中的内存管理
C#版本使用托管内存,由垃圾回收器自动管理,无需手动释放内存。
using Clipper2Lib;
class MemoryManagementExample
{
static void Main()
{
Paths64 paths = new Paths64();
paths.Add(Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 }));
// 不需要手动释放内存,GC会自动处理
}
}
2.8.2 性能建议
预分配容量
using Clipper2Lib;
class PerformanceExample
{
static void Main()
{
// 如果知道大概的点数,预分配可以减少内存重分配
Path64 path = new Path64(1000); // 预分配1000个点的空间
for (int i = 0; i < 1000; i++)
{
path.Add(new Point64(i, i));
}
}
}
复用对象
using Clipper2Lib;
class ReuseObjectsExample
{
static void ProcessMultipleOperations()
{
// 在循环中复用Clipper对象
Clipper64 clipper = new Clipper64();
Paths64 clip = new Paths64();
clip.Add(Clipper.MakePath(new long[] { 50, 50, 150, 50, 150, 150, 50, 150 }));
for (int i = 0; i < 100; i++)
{
clipper.Clear(); // 清空,但保留已分配的内存
Paths64 subject = new Paths64();
subject.Add(Clipper.MakePath(new long[] { i * 10, 0, i * 10 + 100, 0,
i * 10 + 100, 100, i * 10, 100 }));
clipper.AddSubject(subject);
clipper.AddClip(clip);
Paths64 result = new Paths64();
clipper.Execute(ClipType.Intersection, FillRule.NonZero, result);
// 处理结果...
}
}
}
2.9 类型别名与兼容性
2.9.1 类型定义
C#版本中的主要类型:
// 整数坐标类型
public struct Point64 { public long X, Y; }
public class Path64 : List<Point64> { }
public class Paths64 : List<Path64> { }
public struct Rect64 { public long left, top, right, bottom; }
// 浮点数坐标类型
public struct PointD { public double X, Y; }
public class PathD : List<PointD> { }
public class PathsD : List<PathD> { }
public struct RectD { public double left, top, right, bottom; }
2.9.2 自定义点类型的适配
如果你的应用已有自己的点类型,可以通过转换方法适配:
using System;
using System.Collections.Generic;
using Clipper2Lib;
// 假设你的点类型
public struct MyPoint
{
public float X, Y;
}
public static class PointConverter
{
// 转换为Path64
public static Path64 ConvertToPath64(List<MyPoint> myPoints, double scale)
{
Path64 path = new Path64(myPoints.Count);
foreach (var p in myPoints)
{
path.Add(new Point64((long)(p.X * scale), (long)(p.Y * scale)));
}
return path;
}
// 从Path64转换回来
public static List<MyPoint> ConvertFromPath64(Path64 path, double scale)
{
List<MyPoint> result = new List<MyPoint>(path.Count);
foreach (var p in path)
{
result.Add(new MyPoint { X = (float)(p.X / scale), Y = (float)(p.Y / scale) });
}
return result;
}
}
2.10 本章小结
本章我们深入学习了Clipper2 C#版本的核心数据结构:
- Point(点):Point64使用整数坐标,PointD使用浮点坐标,支持基本运算和几何判断
- Path(路径):有序点的集合,表示多边形边界或折线
- Paths(路径集合):多个路径的集合,可表示多个多边形或带孔洞的复杂多边形
- Rect(矩形):轴对齐矩形,用于边界框和优化裁剪
- PolyTree(多边形树):树形结构,表示嵌套多边形的层次关系
理解这些数据结构是使用Clipper2的基础。在下一章中,我们将学习如何使用这些数据结构进行布尔运算操作。