第2章：核心数据结构 - IntPoint、DoublePoint、IntRect
2.1 概述
Clipper1 定义了三个基础的几何数据结构：IntPoint（整数点）、DoublePoint（浮点点）和 IntRect（整数矩形）。这些结构是整个库的基石，用于表示坐标点和边界框。
2.2 IntPoint 结构
IntPoint 是 Clipper 中最核心的数据结构，用于表示一个二维（或三维）整数坐标点。
2.2.1 基本定义
public struct IntPoint
{
public cInt X;
public cInt Y;
#if use_xyz
public cInt Z;
#endif
}
关键设计决策：
- 使用
struct而非class：- 值类型，存储在栈上，避免堆分配和垃圾回收开销
- 在大量点操作时性能更好
- 赋值时自动复制，无需担心引用共享
- 使用
cInt类型别名：- 可以在编译时选择 32 位或 64 位整数
- 默认为
Int64，提供更大的坐标范围
2.2.2 构造函数（2D 模式）
当 use_xyz 未定义时，IntPoint 只有 X、Y 两个坐标：
public IntPoint(cInt X, cInt Y)
{
this.X = X;
this.Y = Y;
}
public IntPoint(double x, double y)
{
this.X = (cInt)x;
this.Y = (cInt)y;
}
public IntPoint(IntPoint pt)
{
this.X = pt.X;
this.Y = pt.Y;
}
构造函数分析：
- 整数构造函数：直接赋值，最高效
- 浮点构造函数：将
double转换为cInt，注意这是截断而非四舍五入 - 复制构造函数：从另一个 IntPoint 复制坐标
2.2.3 构造函数（3D 模式）
当定义了 use_xyz 时，IntPoint 增加 Z 坐标：
#if use_xyz
public IntPoint(cInt x, cInt y, cInt z = 0)
{
this.X = x;
this.Y = y;
this.Z = z;
}
public IntPoint(double x, double y, double z = 0)
{
this.X = (cInt)x;
this.Y = (cInt)y;
this.Z = (cInt)z;
}
public IntPoint(DoublePoint dp)
{
this.X = (cInt)dp.X;
this.Y = (cInt)dp.Y;
this.Z = 0;
}
public IntPoint(IntPoint pt)
{
this.X = pt.X;
this.Y = pt.Y;
this.Z = pt.Z;
}
#endif
Z 坐标的用途：
- 存储高程信息（3D 应用）
- 存储自定义属性（如点的索引、颜色等）
- 在裁剪操作中保留和插值属性
2.2.4 相等性比较运算符
public static bool operator ==(IntPoint a, IntPoint b)
{
return a.X == b.X && a.Y == b.Y;
}
public static bool operator !=(IntPoint a, IntPoint b)
{
return a.X != b.X || a.Y != b.Y;
}
设计要点：
- 只比较 X 和 Y：即使在 3D 模式下，相等性比较也只考虑 X、Y 坐标
- 使用整数比较：整数比较是精确的，这是选择整数坐标的主要优势
2.2.5 Equals 方法重写
public override bool Equals(object obj)
{
if (obj == null) return false;
if (obj is IntPoint)
{
IntPoint a = (IntPoint)obj;
return (X == a.X) && (Y == a.Y);
}
else return false;
}
实现细节：
- 空值检查：防止 NullReferenceException
- 类型检查：使用
is关键字检查类型 - 值比较：与
==运算符行为一致
2.2.6 GetHashCode 方法
public override int GetHashCode()
{
//simply prevents a compiler warning
return base.GetHashCode();
}
注意：这里的实现只是为了消除编译器警告（重写 Equals 时必须重写 GetHashCode）。实际使用中，如果需要将 IntPoint 用作字典键或放入 HashSet，应该提供更好的哈希实现。
更好的哈希实现建议：
public override int GetHashCode()
{
unchecked
{
int hash = 17;
hash = hash * 31 + X.GetHashCode();
hash = hash * 31 + Y.GetHashCode();
return hash;
}
}
2.2.7 使用示例
// 创建点
IntPoint p1 = new IntPoint(100, 200);
IntPoint p2 = new IntPoint(100.7, 200.9); // 截断为 (100, 200)
IntPoint p3 = new IntPoint(p1); // 复制
// 比较
bool equal = (p1 == p2); // true，因为截断后相等
bool notEqual = (p1 != new IntPoint(101, 200)); // true
// 作为 Path 的元素
Path polygon = new Path();
polygon.Add(new IntPoint(0, 0));
polygon.Add(new IntPoint(100, 0));
polygon.Add(new IntPoint(100, 100));
polygon.Add(new IntPoint(0, 100));
2.3 DoublePoint 结构
DoublePoint 用于表示双精度浮点坐标点，主要在内部计算和偏移操作中使用。
2.3.1 结构定义
public struct DoublePoint
{
public double X;
public double Y;
public DoublePoint(double x = 0, double y = 0)
{
this.X = x;
this.Y = y;
}
public DoublePoint(DoublePoint dp)
{
this.X = dp.X;
this.Y = dp.Y;
}
public DoublePoint(IntPoint ip)
{
this.X = ip.X;
this.Y = ip.Y;
}
}
2.3.2 与 IntPoint 的转换
// IntPoint -> DoublePoint（无损）
IntPoint ip = new IntPoint(100, 200);
DoublePoint dp = new DoublePoint(ip); // (100.0, 200.0)
// DoublePoint -> IntPoint（可能有精度损失）
DoublePoint dp2 = new DoublePoint(100.7, 200.9);
IntPoint ip2 = new IntPoint((cInt)dp2.X, (cInt)dp2.Y); // (100, 200)
2.3.3 主要用途
- 法向量计算：在偏移操作中计算边的单位法向量
- 中间计算：某些几何计算需要浮点精度
- 坐标转换：作为整数和浮点坐标之间的桥梁
2.3.4 在 ClipperOffset 中的应用
// ClipperOffset 内部使用 DoublePoint 存储法向量
internal static DoublePoint GetUnitNormal(IntPoint pt1, IntPoint pt2)
{
double dx = (pt2.X - pt1.X);
double dy = (pt2.Y - pt1.Y);
if ((dx == 0) && (dy == 0)) return new DoublePoint();
double f = 1 * 1.0 / Math.Sqrt(dx * dx + dy * dy);
dx *= f;
dy *= f;
return new DoublePoint(dy, -dx);
}
算法解析：
- 计算方向向量
(dx, dy) - 计算长度的倒数
f = 1/√(dx² + dy²) - 归一化得到单位向量
(dx*f, dy*f) - 旋转 90 度得到法向量
(dy*f, -dx*f)
2.4 IntRect 结构
IntRect 表示一个轴对齐的整数边界矩形（Axis-Aligned Bounding Box, AABB）。
2.4.1 结构定义
public struct IntRect
{
public cInt left;
public cInt top;
public cInt right;
public cInt bottom;
public IntRect(cInt l, cInt t, cInt r, cInt b)
{
this.left = l;
this.top = t;
this.right = r;
this.bottom = b;
}
public IntRect(IntRect ir)
{
this.left = ir.left;
this.top = ir.top;
this.right = ir.right;
this.bottom = ir.bottom;
}
}
2.4.2 坐标约定
Clipper 使用的坐标系统中：
- left ≤ right（X 方向）
- top ≤ bottom（Y 方向，注意：Y 轴向下增长）
这与计算机图形学中常用的屏幕坐标系一致。
2.4.3 GetBounds 静态方法
ClipperBase 类提供了计算路径集合边界框的方法：
public static IntRect GetBounds(Paths paths)
{
int i = 0, cnt = paths.Count;
// 跳过空路径
while (i < cnt && paths[i].Count == 0) i++;
if (i == cnt) return new IntRect(0, 0, 0, 0);
IntRect result = new IntRect();
// 初始化为第一个点
result.left = paths[i][0].X;
result.right = result.left;
result.top = paths[i][0].Y;
result.bottom = result.top;
// 遍历所有点，更新边界
for (; i < cnt; i++)
for (int j = 0; j < paths[i].Count; j++)
{
if (paths[i][j].X < result.left)
result.left = paths[i][j].X;
else if (paths[i][j].X > result.right)
result.right = paths[i][j].X;
if (paths[i][j].Y < result.top)
result.top = paths[i][j].Y;
else if (paths[i][j].Y > result.bottom)
result.bottom = paths[i][j].Y;
}
return result;
}
算法分析：
- 空路径处理：跳过没有点的路径
- 初始化：使用第一个有效点初始化边界
- 遍历更新：检查每个点，更新最小/最大坐标
- 时间复杂度：O(n)，n 为所有路径的总点数
2.4.4 使用示例
// 创建一些路径
Paths paths = new Paths();
Path p1 = new Path();
p1.Add(new IntPoint(10, 20));
p1.Add(new IntPoint(100, 30));
p1.Add(new IntPoint(50, 80));
paths.Add(p1);
Path p2 = new Path();
p2.Add(new IntPoint(200, 10));
p2.Add(new IntPoint(250, 100));
paths.Add(p2);
// 计算边界框
IntRect bounds = ClipperBase.GetBounds(paths);
// 结果: left=10, top=10, right=250, bottom=100
Console.WriteLine($"边界: ({bounds.left}, {bounds.top}) - ({bounds.right}, {bounds.bottom})");
Console.WriteLine($"宽度: {bounds.right - bounds.left}");
Console.WriteLine($"高度: {bounds.bottom - bounds.top}");
2.5 类型别名 Path 和 Paths
虽然不是结构体，但 Path 和 Paths 是 Clipper 中最常用的类型：
using Path = List<IntPoint>;
using Paths = List<List<IntPoint>>;
2.5.1 Path（路径）
Path polygon = new Path();
// 添加顶点（顺时针方向 = 外轮廓）
polygon.Add(new IntPoint(0, 0));
polygon.Add(new IntPoint(100, 0));
polygon.Add(new IntPoint(100, 100));
polygon.Add(new IntPoint(0, 100));
// 访问顶点
IntPoint first = polygon[0];
int count = polygon.Count;
// 遍历
foreach (IntPoint pt in polygon)
{
Console.WriteLine($"({pt.X}, {pt.Y})");
}
// 反转方向
polygon.Reverse();
2.5.2 Paths（路径集合）
Paths polygons = new Paths();
// 添加外轮廓
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));
polygons.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));
polygons.Add(hole);
// 访问
int pathCount = polygons.Count;
Path firstPath = polygons[0];
2.5.3 路径方向约定
Clipper 遵循以下方向约定（在 Y 轴向上的坐标系中）：
| 类型 | 方向 | 面积符号 |
|---|---|---|
| 外轮廓 | 逆时针 | 正 |
| 孔洞 | 顺时针 | 负 |
注意：在 Y 轴向下的屏幕坐标系中，方向相反。
2.5.4 判断路径方向
// 使用 Orientation 方法
bool isCounterClockwise = Clipper.Orientation(polygon);
// 使用 Area 方法
double area = Clipper.Area(polygon);
bool isOuter = area > 0; // 正面积 = 逆时针 = 外轮廓
bool isHole = area < 0; // 负面积 = 顺时针 = 孔洞
2.6 内存布局分析
2.6.1 IntPoint 内存布局
32位模式 (use_int32):
+---+---+
| X | Y | = 8 bytes
+---+---+
(4 bytes each)
64位模式 (默认):
+-------+-------+
| X | Y | = 16 bytes
+-------+-------+
(8 bytes each)
64位模式 + use_xyz:
+-------+-------+-------+
| X | Y | Z | = 24 bytes
+-------+-------+-------+
(8 bytes each)
2.6.2 性能考虑
// 值类型复制 - 每次赋值都会复制所有字段
IntPoint p1 = new IntPoint(100, 200);
IntPoint p2 = p1; // 复制 16 字节
p2.X = 50; // 不影响 p1
// 引用传递优化
void ProcessPoint(ref IntPoint pt)
{
pt.X = pt.X * 2;
}
// 避免在循环中频繁创建新实例
Path optimized = new Path(1000); // 预分配容量
for (int i = 0; i < 1000; i++)
{
optimized.Add(new IntPoint(i, i * 2));
}
2.7 与其他库的互操作
2.7.1 与 System.Drawing 互操作
using System.Drawing;
// Point -> IntPoint
Point sysPoint = new Point(100, 200);
IntPoint clipperPoint = new IntPoint(sysPoint.X, sysPoint.Y);
// IntPoint -> Point
IntPoint ip = new IntPoint(100, 200);
Point sp = new Point((int)ip.X, (int)ip.Y);
// PointF -> IntPoint（带缩放）
const double scale = 1000.0;
PointF pf = new PointF(1.5f, 2.7f);
IntPoint scaled = new IntPoint((cInt)(pf.X * scale), (cInt)(pf.Y * scale));
2.7.2 序列化支持
由于 IntPoint 是简单的结构体，可以轻松序列化：
// JSON 序列化示例
using System.Text.Json;
Path polygon = new Path();
polygon.Add(new IntPoint(0, 0));
polygon.Add(new IntPoint(100, 0));
polygon.Add(new IntPoint(100, 100));
// 转换为 JSON 友好的格式
var jsonData = polygon.Select(p => new { x = p.X, y = p.Y }).ToArray();
string json = JsonSerializer.Serialize(jsonData);
// [{"x":0,"y":0},{"x":100,"y":0},{"x":100,"y":100}]
2.8 本章小结
本章详细分析了 Clipper1 的三个基础数据结构：
- IntPoint：
- 核心坐标结构，使用整数确保精确性
- 支持 2D 和 3D 模式
- 提供完整的相等性比较支持
- DoublePoint：
- 浮点坐标结构，用于中间计算
- 主要在偏移操作中使用
- 提供与 IntPoint 的双向转换
- IntRect：
- 边界矩形结构
- 用于快速边界检测和碰撞检测
- GetBounds 方法计算路径集合的边界
- Path 和 Paths：
- 类型别名，简化代码
- 遵循方向约定区分外轮廓和孔洞
这些基础结构的设计体现了 Clipper 追求精确性和性能的设计理念，为后续的复杂算法提供了坚实的基础。
| 上一章：概述与入门 | 返回目录 | 下一章：路径与多边形表示 |