第4章：矩形边界 - Rect64、RectD

4.1 概述

在多边形裁剪运算中，矩形边界框（Bounding Box）是一个关键的优化结构。通过快速判断两个多边形的边界框是否相交，可以在早期排除不可能相交的情况，大大提高算法效率。Clipper2 提供了 Rect64 和 RectD 两种矩形结构。

4.2 Rect64 结构

4.2.1 结构定义

public struct Rect64
{
    public long left;
    public long top;
    public long right;
    public long bottom;
}

坐标系统：

left：左边界（最小 X）
top：上边界（最小 Y）
right：右边界（最大 X）
bottom：下边界（最大 Y）

注意：在 Clipper2 中，Y 轴默认向下，因此 top < bottom。

4.2.2 构造函数

// 从四个边界值创建
public Rect64(long l, long t, long r, long b)
{
    left = l;
    top = t;
    right = r;
    bottom = b;
}

// 创建有效或无效矩形
public Rect64(bool isValid)
{
    if (isValid)
    {
        left = 0; top = 0; right = 0; bottom = 0;
    }
    else
    {
        // 无效矩形：用于初始化，等待后续更新
        left = long.MaxValue; 
        top = long.MaxValue; 
        right = long.MinValue; 
        bottom = long.MinValue;
    }
}

// 复制构造函数
public Rect64(Rect64 rec)
{
    left = rec.left;
    top = rec.top;
    right = rec.right;
    bottom = rec.bottom;
}

4.2.3 无效矩形的设计

无效矩形是一个巧妙的设计，用于边界框的累积计算：

// 创建无效矩形
Rect64 bounds = new Rect64(false);
// 此时: left = MaxValue, right = MinValue
// 任何点都会扩展这个边界

// 累积边界
foreach (Point64 pt in path)
{
    if (pt.X < bounds.left) bounds.left = pt.X;
    if (pt.X > bounds.right) bounds.right = pt.X;
    if (pt.Y < bounds.top) bounds.top = pt.Y;
    if (pt.Y > bounds.bottom) bounds.bottom = pt.Y;
}

4.2.4 宽度和高度属性

public long Width
{ 
    readonly get => right - left;
    set => right = left + value;
}

public long Height
{ 
    readonly get => bottom - top;
    set => bottom = top + value;
}

这些属性同时提供了 getter 和 setter，允许通过设置宽高来调整矩形大小。

4.2.5 核心判断方法

// 判断矩形是否为空（宽或高 <= 0）
public readonly bool IsEmpty()
{
    return bottom <= top || right <= left;
}

// 判断矩形是否有效
public readonly bool IsValid()
{
    return left < long.MaxValue;
}

// 计算中心点
public readonly Point64 MidPoint()
{
    return new Point64((left + right) / 2, (top + bottom) / 2);
}

4.2.6 包含判断

// 判断点是否在矩形内（不含边界）
public readonly bool Contains(Point64 pt)
{
    return pt.X > left && pt.X < right &&
           pt.Y > top && pt.Y < bottom;
}

// 判断另一个矩形是否完全在此矩形内
public readonly bool Contains(Rect64 rec)
{
    return rec.left >= left && rec.right <= right &&
           rec.top >= top && rec.bottom <= bottom;
}

注意：Contains(Point64) 使用严格不等式（> 和 <），边界上的点返回 false。

4.2.7 相交判断

public readonly bool Intersects(Rect64 rec)
{
    return (Math.Max(left, rec.left) <= Math.Min(right, rec.right)) &&
           (Math.Max(top, rec.top) <= Math.Min(bottom, rec.bottom));
}

这是经典的 AABB（轴对齐边界框）相交测试算法。

4.2.8 转换为路径

public readonly Path64 AsPath()
{
    Path64 result = new Path64(4)
    {
        new Point64(left, top),
        new Point64(right, top),
        new Point64(right, bottom),
        new Point64(left, bottom)
    };
    return result;
}

将矩形转换为闭合的四边形路径，顺时针方向（在 Y 向下坐标系中）。

4.3 RectD 结构

4.3.1 结构定义

public struct RectD
{
    public double left;
    public double top;
    public double right;
    public double bottom;
}

RectD 与 Rect64 结构完全相同，只是使用 double 类型。

4.3.2 构造函数

public RectD(double l, double t, double r, double b)
{
    left = l;
    top = t;
    right = r;
    bottom = b;
}

public RectD(RectD rec)
{
    left = rec.left;
    top = rec.top;
    right = rec.right;
    bottom = rec.bottom;
}

public RectD(bool isValid)
{
    if (isValid)
    {
        left = 0; top = 0; right = 0; bottom = 0;
    }
    else
    {
        left = double.MaxValue; 
        top = double.MaxValue;
        right = -double.MaxValue;  // 注意：使用负最大值
        bottom = -double.MaxValue;
    }
}

注意：无效 RectD 的 right 和 bottom 使用 -double.MaxValue 而非 double.MinValue。这是因为 double.MinValue 实际上是一个很大的负数（约 -1.7×10³⁰⁸），而我们需要的是”任何正常值都比它大”的初始值。

4.3.3 主要方法

public double Width
{ 
    readonly get => right - left;
    set => right = left + value;
}

public double Height
{ 
    readonly get => bottom - top;
    set => bottom = top + value;
}

public readonly bool IsEmpty()
{
    return bottom <= top || right <= left;
}

public readonly PointD MidPoint()
{
    return new PointD((left + right) / 2, (top + bottom) / 2);
}

public readonly bool Contains(PointD pt)
{
    return pt.x > left && pt.x < right &&
           pt.y > top && pt.y < bottom;
}

public readonly bool Contains(RectD rec)
{
    return rec.left >= left && rec.right <= right &&
           rec.top >= top && rec.bottom <= bottom;
}

// 注意：RectD 的相交判断使用严格不等式
public readonly bool Intersects(RectD rec)
{
    return (Math.Max(left, rec.left) < Math.Min(right, rec.right)) &&
           (Math.Max(top, rec.top) < Math.Min(bottom, rec.bottom));
}

public readonly PathD AsPath()
{
    PathD result = new PathD(4)
    {
        new PointD(left, top),
        new PointD(right, top),
        new PointD(right, bottom),
        new PointD(left, bottom)
    };
    return result;
}

4.4 边界框计算

4.4.1 GetBounds 方法

// 单条路径的边界框
public static Rect64 GetBounds(Path64 path)
{
    Rect64 result = InvalidRect64;  // 无效矩形作为初始值
    foreach (Point64 pt in path)
    {
        if (pt.X < result.left) result.left = pt.X;
        if (pt.X > result.right) result.right = pt.X;
        if (pt.Y < result.top) result.top = pt.Y;
        if (pt.Y > result.bottom) result.bottom = pt.Y;
    }
    return result.left == long.MaxValue ? new Rect64() : result;
}

// 多条路径的边界框
public static Rect64 GetBounds(Paths64 paths)
{
    Rect64 result = InvalidRect64;
    foreach (Path64 path in paths)
        foreach (Point64 pt in path)
        {
            if (pt.X < result.left) result.left = pt.X;
            if (pt.X > result.right) result.right = pt.X;
            if (pt.Y < result.top) result.top = pt.Y;
            if (pt.Y > result.bottom) result.bottom = pt.Y;
        }
    return result.left == long.MaxValue ? new Rect64() : result;
}

4.4.2 静态无效矩形常量

public static class Clipper
{
    private static Rect64 invalidRect64 = new Rect64(false);
    public static Rect64 InvalidRect64 => invalidRect64;

    private static RectD invalidRectD = new RectD(false);
    public static RectD InvalidRectD => invalidRectD;
}

这些预定义的无效矩形用作边界计算的初始值。

4.4.3 InternalClipper 中的 GetBounds

public static Rect64 GetBounds(Path64 path)
{
    if (path.Count == 0) return new Rect64();
    Rect64 result = Clipper.InvalidRect64;
    foreach (Point64 pt in path)
    {
        if (pt.X < result.left) result.left = pt.X;
        if (pt.X > result.right) result.right = pt.X;
        if (pt.Y < result.top) result.top = pt.Y;
        if (pt.Y > result.bottom) result.bottom = pt.Y;
    }
    return result;
}

注意：InternalClipper 和 Clipper 类都有 GetBounds 方法，但实现略有不同。

4.5 矩形操作

4.5.1 矩形膨胀

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void InflateRect(ref Rect64 rec, int dx, int dy)
{
    rec.left -= dx;
    rec.right += dx;
    rec.top -= dy;
    rec.bottom += dy;
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void InflateRect(ref RectD rec, double dx, double dy)
{
    rec.left -= dx;
    rec.right += dx;
    rec.top -= dy;
    rec.bottom += dy;
}

注意：这些方法使用 ref 参数，直接修改原矩形，避免结构体复制。

4.5.2 矩形缩放

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static Rect64 ScaleRect(RectD rec, double scale)
{
    Rect64 result = new Rect64()
    {
        left = (long) (rec.left * scale),
        top = (long) (rec.top * scale),
        right = (long) (rec.right * scale),
        bottom = (long) (rec.bottom * scale)
    };
    return result;
}

这个方法用于将浮点矩形转换为整数矩形，常用于 ClipperD 内部处理。

4.6 矩形在裁剪中的应用

4.6.1 快速剔除

在裁剪操作前，检查边界框可以快速排除不相交的情况：

// 伪代码示例
Rect64 subjectBounds = GetBounds(subject);
Rect64 clipBounds = GetBounds(clip);

if (!subjectBounds.Intersects(clipBounds))
{
    // 边界框不相交，直接返回
    switch (clipType)
    {
        case ClipType.Intersection:
            return new Paths64();  // 空结果
        case ClipType.Union:
            // 返回两者合并
            break;
        case ClipType.Difference:
            return subject;  // 原样返回主体
        // ...
    }
}

4.6.2 RectClip 优化

Clipper2 引入了专门的矩形裁剪算法 RectClip64，当裁剪多边形为矩形时效率更高：

public static Paths64 RectClip(Rect64 rect, Paths64 paths)
{
    if (rect.IsEmpty() || paths.Count == 0) return new Paths64();
    RectClip64 rc = new RectClip64(rect);
    return rc.Execute(paths);
}

4.7 边界框的性能考量

4.7.1 结构体优势

使用 struct 而非 class 的原因：

栈分配：避免堆分配和 GC 压力
值语义：复制时是完整复制，不共享状态
内联性能：编译器更容易内联结构体操作

4.7.2 只读方法

方法使用 readonly 修饰：

public readonly bool IsEmpty()
public readonly bool Contains(Point64 pt)
public readonly bool Intersects(Rect64 rec)

这告诉编译器方法不会修改结构体字段，允许在 readonly 结构体实例上调用，并可能获得更好的优化。

4.7.3 内联优化

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void InflateRect(ref Rect64 rec, int dx, int dy)

对于简单操作，使用 AggressiveInlining 确保方法被内联，避免方法调用开销。

4.8 实际使用示例

4.8.1 计算多边形边界

Path64 polygon = Clipper.MakePath(new long[] {
    0, 0, 100, 0, 100, 100, 0, 100
});

Rect64 bounds = Clipper.GetBounds(polygon);
Console.WriteLine($"左: {bounds.left}, 上: {bounds.top}");
Console.WriteLine($"右: {bounds.right}, 下: {bounds.bottom}");
Console.WriteLine($"宽: {bounds.Width}, 高: {bounds.Height}");
Console.WriteLine($"中心: {bounds.MidPoint()}");

4.8.2 判断点是否在多边形边界内

Point64 testPoint = new Point64(50, 50);
Rect64 bounds = Clipper.GetBounds(polygon);

if (bounds.Contains(testPoint))
{
    // 点在边界框内，可能在多边形内
    // 需要进一步使用 PointInPolygon 精确判断
}
else
{
    // 点在边界框外，肯定不在多边形内
}

4.8.3 矩形裁剪

// 使用矩形快速裁剪
Rect64 clipRect = new Rect64(25, 25, 75, 75);
Paths64 subject = new Paths64 { polygon };

Paths64 result = Clipper.RectClip(clipRect, subject);

4.9 本章小结

本章详细介绍了 Clipper2 的矩形边界结构：

Rect64 和 RectD：分别用于整数和浮点坐标
无效矩形：用于边界累积计算的初始值
核心操作：包含判断、相交判断、中心点计算
性能优化：结构体设计、只读方法、内联优化
实际应用：快速剔除、矩形裁剪

边界框是提高裁剪算法效率的重要手段，通过简单的矩形测试可以排除大量不必要的复杂计算。

上一章：路径与多边形表示

返回目录

下一章：枚举类型与常量