第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
}

关键设计决策：

1. 使用 struct 而非 class：

   • 值类型，存储在栈上，避免堆分配和垃圾回收开销
   • 在大量点操作时性能更好
   • 赋值时自动复制，无需担心引用共享

2. 使用 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;
}

构造函数分析：

1. 整数构造函数：直接赋值，最高效
2. 浮点构造函数：将 double 转换为 cInt，注意这是截断而非四舍五入
3. 复制构造函数：从另一个 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;
}

设计要点：

1. 只比较 X 和 Y：即使在 3D 模式下，相等性比较也只考虑 X、Y 坐标
2. 使用整数比较：整数比较是精确的，这是选择整数坐标的主要优势

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

实现细节：

1. 空值检查：防止 NullReferenceException
2. 类型检查：使用 is 关键字检查类型
3. 值比较：与 == 运算符行为一致

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 主要用途

1. 法向量计算：在偏移操作中计算边的单位法向量
2. 中间计算：某些几何计算需要浮点精度
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);
}

算法解析：

1. 计算方向向量 (dx, dy)
2. 计算长度的倒数 f = 1/√(dx² + dy²)
3. 归一化得到单位向量 (dx*f, dy*f)
4. 旋转 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;
}

算法分析：

1. 空路径处理：跳过没有点的路径
2. 初始化：使用第一个有效点初始化边界
3. 遍历更新：检查每个点，更新最小/最大坐标
4. 时间复杂度：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 的三个基础数据结构：

1. IntPoint：

   • 核心坐标结构，使用整数确保精确性
   • 支持 2D 和 3D 模式
   • 提供完整的相等性比较支持

2. DoublePoint：

   • 浮点坐标结构，用于中间计算
   • 主要在偏移操作中使用
   • 提供与 IntPoint 的双向转换

3. IntRect：

   • 边界矩形结构
   • 用于快速边界检测和碰撞检测
   • GetBounds 方法计算路径集合的边界

4. Path 和 Paths：

   • 类型别名，简化代码
   • 遵循方向约定区分外轮廓和孔洞

这些基础结构的设计体现了 Clipper 追求精确性和性能的设计理念，为后续的复杂算法提供了坚实的基础。

---

上一章：概述与入门 | 返回目录 | 下一章：路径与多边形表示