在多边形裁剪运算中，矩形边界框（Bounding Box）是一个关键的优化结构。通过快速判断两个多边形的边界框是否相交，可以在早期排除不可能相交的情况，大大提高算法效率。Clipper2 提供了 Rect64 和 RectD 两种矩形结构。
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。
// 从四个边界值创建
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;
}
无效矩形是一个巧妙的设计，用于边界框的累积计算：
// 创建无效矩形
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;
}
public long Width
{
readonly get => right - left;
set => right = left + value;
}
public long Height
{
readonly get => bottom - top;
set => bottom = top + value;
}
这些属性同时提供了 getter 和 setter，允许通过设置宽高来调整矩形大小。
// 判断矩形是否为空（宽或高 <= 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);
}
// 判断点是否在矩形内（不含边界）
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。
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（轴对齐边界框）相交测试算法。
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 向下坐标系中）。
public struct RectD
{
public double left;
public double top;
public double right;
public double bottom;
}
RectD 与 Rect64 结构完全相同，只是使用 double 类型。
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³⁰⁸），而我们需要的是"任何正常值都比它大"的初始值。
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;
}
// 单条路径的边界框
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;
}
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;
}
这些预定义的无效矩形用作边界计算的初始值。
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 方法，但实现略有不同。
[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 参数，直接修改原矩形，避免结构体复制。
[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 内部处理。
在裁剪操作前，检查边界框可以快速排除不相交的情况：
// 伪代码示例
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; // 原样返回主体
// ...
}
}
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);
}
使用 struct 而非 class 的原因：
方法使用 readonly 修饰：
public readonly bool IsEmpty()
public readonly bool Contains(Point64 pt)
public readonly bool Intersects(Rect64 rec)
这告诉编译器方法不会修改结构体字段，允许在 readonly 结构体实例上调用，并可能获得更好的优化。
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void InflateRect(ref Rect64 rec, int dx, int dy)
对于简单操作，使用 AggressiveInlining 确保方法被内联，避免方法调用开销。
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()}");
Point64 testPoint = new Point64(50, 50);
Rect64 bounds = Clipper.GetBounds(polygon);
if (bounds.Contains(testPoint))
{
// 点在边界框内，可能在多边形内
// 需要进一步使用 PointInPolygon 精确判断
}
else
{
// 点在边界框外，肯定不在多边形内
}
// 使用矩形快速裁剪
Rect64 clipRect = new Rect64(25, 25, 75, 75);
Paths64 subject = new Paths64 { polygon };
Paths64 result = Clipper.RectClip(clipRect, subject);
本章详细介绍了 Clipper2 的矩形边界结构：
边界框是提高裁剪算法效率的重要手段，通过简单的矩形测试可以排除大量不必要的复杂计算。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。