第2章：核心数据结构 - Point64、PointD

2.1 概述

在 Clipper2 中，所有几何运算的基础是点（Point）数据结构。与 Clipper1 不同，Clipper2 提供了两种点类型：

Point64：使用 64 位整数坐标
PointD：使用双精度浮点坐标

这两种类型定义在 Clipper.Core.cs 文件中，是整个库的基石。

2.2 Point64 结构

2.2.1 结构定义

public struct Point64
{
    public long X;
    public long Y;

#if USINGZ
    public long Z;
#endif
}

设计特点：

值类型（struct）：避免堆分配，提高性能
公共字段：直接暴露 X、Y 字段，避免属性访问开销
条件 Z 坐标：通过预处理器指令可选启用

2.2.2 构造函数

Point64 提供了多个构造函数以适应不同场景：

// 从另一个 Point64 复制
public Point64(Point64 pt)
{
    X = pt.X;
    Y = pt.Y;
#if USINGZ
    Z = pt.Z;
#endif
}

// 从 Point64 复制并缩放
public Point64(Point64 pt, double scale)
{
    X = (long) Math.Round(pt.X * scale, MidpointRounding.AwayFromZero);
    Y = (long) Math.Round(pt.Y * scale, MidpointRounding.AwayFromZero);
#if USINGZ
    Z = (long) Math.Round(pt.Z * scale, MidpointRounding.AwayFromZero);
#endif
}

// 从整数坐标创建
public Point64(long x, long y
#if USINGZ
    , long z = 0
#endif
) {
    X = x;
    Y = y;
#if USINGZ
    Z = z;
#endif
}

// 从浮点坐标创建（自动四舍五入）
public Point64(double x, double y
#if USINGZ
    , double z = 0.0
#endif
) {
    X = (long) Math.Round(x, MidpointRounding.AwayFromZero);
    Y = (long) Math.Round(y, MidpointRounding.AwayFromZero);
#if USINGZ
    Z = (long) Math.Round(z, MidpointRounding.AwayFromZero);
#endif
}

// 从 PointD 创建
public Point64(PointD pt)
{
    X = (long) Math.Round(pt.x, MidpointRounding.AwayFromZero);
    Y = (long) Math.Round(pt.y, MidpointRounding.AwayFromZero);
#if USINGZ
    Z = pt.z;
#endif
}

// 从 PointD 创建并缩放
public Point64(PointD pt, double scale)
{
    X = (long) Math.Round(pt.x * scale, MidpointRounding.AwayFromZero);
    Y = (long) Math.Round(pt.y * scale, MidpointRounding.AwayFromZero);
#if USINGZ
    Z = pt.z;
#endif
}

2.2.3 舍入策略

注意所有涉及浮点到整数转换的地方都使用了 MidpointRounding.AwayFromZero：

Math.Round(x, MidpointRounding.AwayFromZero)

这种舍入方式的特点：

0.5 向上舍入到 1
-0.5 向下舍入到 -1
即"四舍五入"的传统行为

与默认的 MidpointRounding.ToEven（银行家舍入）不同，确保了一致性。

2.2.4 运算符重载

// 相等判断
public static bool operator ==(Point64 lhs, Point64 rhs)
{
    return lhs.X == rhs.X && lhs.Y == rhs.Y;
}

public static bool operator !=(Point64 lhs, Point64 rhs)
{
    return lhs.X != rhs.X || lhs.Y != rhs.Y;
}

// 加法
public static Point64 operator +(Point64 lhs, Point64 rhs)
{
    return new Point64(lhs.X + rhs.X, lhs.Y + rhs.Y
#if USINGZ
        , lhs.Z + rhs.Z
#endif
    );
}

// 减法
public static Point64 operator -(Point64 lhs, Point64 rhs)
{
    return new Point64(lhs.X - rhs.X, lhs.Y - rhs.Y
#if USINGZ
        , lhs.Z - rhs.Z
#endif
    );
}

注意：相等判断不比较 Z 坐标！这是设计决策——在 2D 裁剪操作中，只关心 X、Y 坐标的相等性。

2.2.5 ToString 方法

public readonly override string ToString()
{
    // nb: trailing space
#if USINGZ
    return $"{X},{Y},{Z} ";
#else
    return $"{X},{Y} ";
#endif
}

输出格式为 "X,Y " 或 "X,Y,Z "，注意末尾有空格，便于路径的字符串连接。

2.2.6 Equals 和 GetHashCode

public readonly override bool Equals(object? obj)
{
    if (obj != null && obj is Point64 p)
        return this == p;
    return false;
}

public readonly override int GetHashCode()
{
    return HashCode.Combine(X, Y); // #599
}

GetHashCode 使用 HashCode.Combine 方法，这是 .NET Core 2.1+ 引入的高效哈希计算方法。注释中的 #599 是 GitHub issue 编号，表明这是一个经过社区讨论和优化的实现。

2.3 PointD 结构

2.3.1 结构定义

public struct PointD
{
    public double x;
    public double y;

#if USINGZ
    public long z;  // 注意：Z 仍然是整数
#endif
}

注意：即使在浮点点结构中，Z 坐标仍然是 long 类型。这是因为 Z 通常用于存储额外信息（如索引、标记），而非连续坐标。

2.3.2 命名风格差异

public struct Point64
{
    public long X;  // 大写
    public long Y;
}

public struct PointD
{
    public double x;  // 小写
    public double y;
}

这种命名差异可能是为了与其他库兼容或历史原因。在使用时需要注意。

2.3.3 构造函数

// 从另一个 PointD 复制
public PointD(PointD pt)
{
    x = pt.x;
    y = pt.y;
#if USINGZ
    z = pt.z;
#endif
}

// 从 Point64 创建
public PointD(Point64 pt)
{
    x = pt.X;
    y = pt.Y;
#if USINGZ
    z = pt.Z;
#endif
}

// 从 Point64 创建并缩放
public PointD(Point64 pt, double scale)
{
    x = pt.X * scale;
    y = pt.Y * scale;
#if USINGZ
    z = pt.Z;
#endif
}

// 从 PointD 创建并缩放
public PointD(PointD pt, double scale)
{
    x = pt.x * scale;
    y = pt.y * scale;
#if USINGZ
    z = pt.z;
#endif
}

// 从整数坐标创建
public PointD(long x, long y
#if USINGZ
    , long z = 0
#endif
) {
    this.x = x;
    this.y = y;
#if USINGZ
    this.z = z;
#endif
}

// 从浮点坐标创建
public PointD(double x, double y
#if USINGZ
    , long z = 0
#endif
) {
    this.x = x;
    this.y = y;
#if USINGZ
    this.z = z;
#endif
}

2.3.4 运算符重载

public static bool operator ==(PointD lhs, PointD rhs)
{
    return InternalClipper.IsAlmostZero(lhs.x - rhs.x) && 
           InternalClipper.IsAlmostZero(lhs.y - rhs.y);
}

public static bool operator !=(PointD lhs, PointD rhs)
{
    return !InternalClipper.IsAlmostZero(lhs.x - rhs.x) || 
           !InternalClipper.IsAlmostZero(lhs.y - rhs.y);
}

重要区别：PointD 的相等比较使用近似相等（IsAlmostZero），而不是精确相等。这是处理浮点数精度问题的标准做法。

internal const double floatingPointTolerance = 1E-12;

internal static bool IsAlmostZero(double value)
{
    return (Math.Abs(value) <= floatingPointTolerance);
}

容差值为 10⁻¹²，这是一个非常小的值，足以处理大多数双精度浮点数的舍入误差。

2.3.5 Negate 方法

public void Negate() 
{ 
    x = -x; 
    y = -y; 
}

这是一个原地修改方法，将点的坐标取反。用于向量反转等操作。

2.3.6 ToString 方法（带精度）

{% raw %}

public readonly string ToString(int precision = 2)
{
#if USINGZ
    return string.Format($"{{0:F{precision}}},{{1:F{precision}}},{{2:D}}", x, y, z);
#else
    return string.Format($"{{0:F{precision}}},{{1:F{precision}}}", x, y);
#endif
}

{% endraw %}

支持指定小数位数，默认 2 位。例如："12.34,56.78"

2.4 点类型转换

Clipper2 提供了多种点类型转换方法：

2.4.1 静态转换方法

在 Clipper 静态类中：

// Point64 缩放
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static Point64 ScalePoint64(Point64 pt, double scale)
{
    Point64 result = new Point64()
    {
        X = (long) Math.Round(pt.X * scale, MidpointRounding.AwayFromZero),
        Y = (long) Math.Round(pt.Y * scale, MidpointRounding.AwayFromZero),
#if USINGZ
        Z = pt.Z
#endif
    };
    return result;
}

// Point64 转 PointD 并缩放
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static PointD ScalePointD(Point64 pt, double scale)
{
    PointD result = new PointD()
    {
        x = pt.X * scale,
        y = pt.Y * scale,
#if USINGZ
        z = pt.Z,
#endif
    };
    return result;
}

2.4.2 使用场景

// 将浮点坐标转换为整数（用于内部计算）
double scale = 1000.0;  // 保留3位小数
Point64 intPt = new Point64(floatPt, scale);

// 将整数结果转换回浮点
PointD floatResult = new PointD(intResult, 1.0 / scale);

2.5 性能考量

2.5.1 结构体 vs 类

点类型被设计为 struct 而非 class，原因：

避免堆分配：结构体存储在栈上或内联在容器中
无 GC 压力：不需要垃圾回收
复制语义：值类型按值传递，更符合点的数学性质
缓存友好：连续内存布局提高缓存命中率

2.5.2 公共字段 vs 属性

使用公共字段而非属性：

// Clipper2 的做法
public long X;
public long Y;

// 而不是
public long X { get; set; }
public long Y { get; set; }

虽然属性提供封装性，但在性能关键代码中，字段访问更快（尽管现代 JIT 通常会内联简单属性）。

2.5.3 readonly 修饰符

只读方法使用 readonly 修饰：

public readonly override string ToString()
{
    // ...
}

public readonly override bool Equals(object? obj)
{
    // ...
}

这告诉编译器方法不会修改结构体状态，允许更好的优化。

2.6 Z 坐标的应用

当启用 USINGZ 时，点包含额外的 Z 坐标：

2.6.1 用途

3D 坐标：存储真实的三维位置
索引标记：存储原始顶点索引
自定义数据：任意整数用户数据

2.6.2 Z 回调函数

public delegate void ZCallback64(Point64 bot1, Point64 top1,
    Point64 bot2, Point64 top2, ref Point64 intersectPt);

当计算交点时，可以通过回调函数决定交点的 Z 值：

clipper.ZCallback = (Point64 bot1, Point64 top1, 
    Point64 bot2, Point64 top2, ref Point64 ip) =>
{
    // 使用线性插值计算 Z 值
    double t = (ip.Y - bot1.Y) / (double)(top1.Y - bot1.Y);
    ip = new Point64(ip.X, ip.Y, 
        (long)(bot1.Z + t * (top1.Z - bot1.Z)));
};

2.6.3 内置 Z 处理

Clipper2 有默认的 Z 处理逻辑：

private void SetZ(Active e1, Active e2, ref Point64 intersectPt)
{
    if (_zCallback == null) return;

    // 优先使用主体顶点的 Z 值
    if (GetPolyType(e1) == PathType.Subject)
    {
        if (XYCoordsEqual(intersectPt, e1.bot))
            intersectPt = new Point64(intersectPt.X, intersectPt.Y, e1.bot.Z);
        else if (XYCoordsEqual(intersectPt, e1.top))
            intersectPt = new Point64(intersectPt.X, intersectPt.Y, e1.top.Z);
        // ... 更多逻辑
    }
    // ...
}

2.7 实用方法

2.7.1 中点计算

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static Point64 MidPoint(Point64 pt1, Point64 pt2)
{
    return new Point64((pt1.X + pt2.X) / 2, (pt1.Y + pt2.Y) / 2);
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static PointD MidPoint(PointD pt1, PointD pt2)
{
    return new PointD((pt1.x + pt2.x) / 2, (pt1.y + pt2.y) / 2);
}

2.7.2 距离平方计算

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static double DistanceSqr(Point64 pt1, Point64 pt2)
{
    return Sqr(pt1.X - pt2.X) + Sqr(pt1.Y - pt2.Y);
}

使用距离平方而非距离，避免开方运算：

// 比较两点距离时
if (DistanceSqr(pt1, pt2) < thresholdSqr)  // 避免 sqrt

2.7.3 点的近似相等

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool PointsNearEqual(PointD pt1, PointD pt2, double distanceSqrd)
{
    return Sqr(pt1.x - pt2.x) + Sqr(pt1.y - pt2.y) < distanceSqrd;
}

2.8 本章小结

本章详细分析了 Clipper2 的两种点数据结构：

Point64：高精度整数点，用于核心裁剪算法
PointD：浮点点，用于用户接口和输入输出

关键设计要点：

使用 struct 值类型提高性能
浮点比较使用容差值避免精度问题
可选的 Z 坐标支持 3D 数据
MidpointRounding.AwayFromZero 确保一致的四舍五入
大量使用 AggressiveInlining 优化性能

在下一章中，我们将学习基于这些点类型构建的路径和多边形数据结构。

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

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

博客园 - 我才是银古