第五章矩形裁剪与闵可夫斯基操作（C#版）

5.1 引言

除了布尔运算和多边形偏移之外，Clipper2还提供了两个专门的几何操作：矩形裁剪（Rectangle Clipping）和闵可夫斯基运算（Minkowski Operations）。矩形裁剪是一种针对轴对齐矩形优化的高效裁剪算法，在地图瓦片生成、视窗裁剪等场景下非常有用。闵可夫斯基运算则在碰撞检测、机器人路径规划等领域有着重要的应用。本章将详细介绍Clipper2 C#版本中这两种操作的原理和使用方法。

5.2 矩形裁剪

5.2.1 什么是矩形裁剪

矩形裁剪是使用轴对齐矩形（Axis-Aligned Rectangle）作为裁剪区域对多边形进行裁剪的操作。由于矩形具有特殊的几何性质（四条边分别与坐标轴平行），可以设计比通用布尔运算更高效的算法。

     原始多边形              裁剪矩形              裁剪结果
    
        ╱╲                  ┌─────┐               ┌─────┐
       ╱  ╲                 │     │               │     │
      ╱    ╲         ∩      │     │        =      │     │
     ╱      ╲               │     │               │ ╱╲  │
    ╱────────╲              └─────┘               ╱─┘  └─╲

5.2.2 矩形裁剪的优势

相比于使用通用布尔运算进行裁剪，专用的矩形裁剪算法具有以下优势：

更高的性能

矩形裁剪算法的时间复杂度更低，通常比通用布尔运算快2-5倍，对于简单的多边形可能更快。

更简单的实现

由于矩形边与坐标轴对齐，边与边的交点计算更加简单直接。

内存效率

算法不需要构建复杂的事件队列和活动边列表，内存占用更低。

5.2.3 使用RectClip函数

Clipper2提供了RectClip函数用于裁剪闭合多边形：

using Clipper2Lib;

// 创建要裁剪的多边形
Paths64 subject = new Paths64();
subject.Add(Clipper.MakePath(new long[] { 0, 0, 200, 0, 200, 200, 0, 200 }));
subject.Add(Clipper.MakePath(new long[] { 50, 50, 150, 50, 150, 150, 50, 150 }));  // 孔洞

// 定义裁剪矩形
Rect64 clipRect = new Rect64(25, 25, 175, 175);

// 执行矩形裁剪
Paths64 result = Clipper.RectClip(clipRect, subject);

// result 包含裁剪后的多边形

5.2.4 使用RectClipLines函数

对于开放的折线（而非闭合多边形），使用RectClipLines函数：

// 创建开放折线
Paths64 lines = new Paths64();
lines.Add(Clipper.MakePath(new long[] { 0, 100, 200, 100 }));  // 水平线
lines.Add(Clipper.MakePath(new long[] { 100, 0, 100, 200 }));  // 垂直线
lines.Add(Clipper.MakePath(new long[] { 0, 0, 200, 200 }));    // 对角线

// 定义裁剪矩形
Rect64 clipRect = new Rect64(50, 50, 150, 150);

// 裁剪折线
Paths64 result = Clipper.RectClipLines(clipRect, lines);
// result 包含被裁剪到矩形内的线段

5.2.5 RectClip64类

对于需要多次使用同一矩形进行裁剪的场景，可以使用RectClip64类以获得更好的性能：

// 创建裁剪对象
Rect64 clipRect = new Rect64(0, 0, 100, 100);
RectClip64 rectClipper = new RectClip64(clipRect);

// 裁剪多个多边形
foreach (Path64 polygon in polygons)
{
    Paths64 result = rectClipper.Execute(new Paths64 { polygon });
    ProcessResult(result);
}

5.2.6 RectClipLines64类

类似地，对于折线裁剪：

Rect64 clipRect = new Rect64(0, 0, 100, 100);
RectClipLines64 lineClipper = new RectClipLines64(clipRect);

foreach (Path64 line in lines)
{
    Paths64 result = lineClipper.Execute(new Paths64 { line });
    ProcessResult(result);
}

5.2.7 浮点数版本

使用浮点数坐标的版本：

// 浮点数矩形裁剪
PathsD subject = new PathsD();
subject.Add(Clipper.MakePath(new double[] { 0.0, 0.0, 10.0, 0.0, 10.0, 10.0, 0.0, 10.0 }));

RectD clipRect = new RectD(2.5, 2.5, 7.5, 7.5);

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

5.2.8 矩形裁剪的边界情况

边界上的顶点

当多边形顶点恰好在裁剪矩形的边界上时，算法会正确处理：

// 顶点在边界上的多边形
Paths64 subject = new Paths64();
subject.Add(Clipper.MakePath(new long[] { 50, 0, 100, 50, 50, 100, 0, 50 }));  // 菱形

Rect64 clipRect = new Rect64(0, 0, 100, 100);  // 边界与菱形顶点重合
Paths64 result = Clipper.RectClip(clipRect, subject);

完全在矩形内的多边形

如果多边形完全在裁剪矩形内部，返回原始多边形：

Paths64 subject = new Paths64();
subject.Add(Clipper.MakePath(new long[] { 25, 25, 75, 25, 75, 75, 25, 75 }));

Rect64 clipRect = new Rect64(0, 0, 100, 100);
Paths64 result = Clipper.RectClip(clipRect, subject);
// result 与 subject 相同

完全在矩形外的多边形

如果多边形完全在裁剪矩形外部，返回空结果：

Paths64 subject = new Paths64();
subject.Add(Clipper.MakePath(new long[] { 200, 200, 300, 200, 300, 300, 200, 300 }));

Rect64 clipRect = new Rect64(0, 0, 100, 100);
Paths64 result = Clipper.RectClip(clipRect, subject);
// result 为空

5.2.9 矩形裁剪的应用场景

地图瓦片生成

// 生成256x256的地图瓦片
static void GenerateTile(int tileX, int tileY, int zoom, Paths64 mapData)
{
    // 计算瓦片的地理范围
    int tileSize = 256;

    Rect64 tileBounds = new Rect64(
        tileX * tileSize,
        tileY * tileSize,
        (tileX + 1) * tileSize,
        (tileY + 1) * tileSize
    );

    // 裁剪地图数据到瓦片范围
    Paths64 tileData = Clipper.RectClip(tileBounds, mapData);

    // 渲染瓦片
    RenderTile(tileData);
}

视窗裁剪

// 裁剪到可见视窗区域
static Paths64 ClipToViewport(Paths64 geometry,
                              int viewportWidth, int viewportHeight,
                              int scrollX, int scrollY)
{
    Rect64 viewport = new Rect64(
        scrollX,
        scrollY,
        scrollX + viewportWidth,
        scrollY + viewportHeight
    );

    return Clipper.RectClip(viewport, geometry);
}

空间分区

// 将几何体分配到四叉树节点（QuadTreeNode 为自定义四叉树结构）
static void QuadTreeInsert(QuadTreeNode node, Paths64 geometry)
{
    Rect64 nodeBounds = node.GetBounds();
    Paths64 clipped = Clipper.RectClip(nodeBounds, geometry);

    if (clipped.Count > 0)
    {
        if (node.IsLeaf() || Clipper.Area(clipped) < threshold)
        {
            node.AddGeometry(clipped);
        }
        else
        {
            // 分配到子节点
            foreach (QuadTreeNode child in node.Children())
            {
                QuadTreeInsert(child, clipped);
            }
        }
    }
}

5.3 闵可夫斯基运算

5.3.1 什么是闵可夫斯基运算

闵可夫斯基运算是以德国数学家赫尔曼·闵可夫斯基（Hermann Minkowski）命名的几何操作。主要包括两种运算：

闵可夫斯基和（Minkowski Sum）

两个点集A和B的闵可夫斯基和定义为： A ⊕ B = {a + b | a ∈ A, b ∈ B}

直观理解：将形状B的中心放在形状A的每个边界点上，所有这些B形状的并集就是闵可夫斯基和。

     多边形A              多边形B            闵可夫斯基和
    
    ┌───────┐              ○               ╭───────────╮
    │       │              ↓               │   ╭─────╮ │
    │       │      ⊕                  =    │   │     │ │
    │       │                              │   ╰─────╯ │
    └───────┘                              ╰───────────╯
                                          （圆角矩形）

闵可夫斯基差（Minkowski Difference）

A和B的闵可夫斯基差定义为： A ⊖ B = A ⊕ (-B) = {a - b | a ∈ A, b ∈ B}

其中-B是B关于原点的反射。

5.3.2 闵可夫斯基和的几何意义

闵可夫斯基和有几个重要的几何解释：

形态膨胀

当B是一个以原点为中心的圆时，A ⊕ B 等于A的圆形偏移。

可达区域

如果A表示障碍物，B表示移动物体，那么A ⊕ (-B)表示移动物体中心不能到达的区域。

碰撞检测

两个多边形A和B相交，当且仅当(A ⊖ B)包含原点。

5.3.3 使用MinkowskiSum函数

Clipper2提供了闵可夫斯基和函数：

using Clipper2Lib;

// 创建第一个多边形（矩形）
Path64 pattern = Clipper.MakePath(new long[] { -50, -50, 50, -50, 50, 50, -50, 50 });

// 创建第二个多边形（三角形，以原点为中心）
Path64 path = Clipper.MakePath(new long[] { 0, -30, 26, 15, -26, 15 });

// 计算闵可夫斯基和
Paths64 result = Clipper.MinkowskiSum(pattern, path, false);
// 参数：pattern（图案）, path（路径）, isClosed（路径是否闭合）

5.3.4 使用MinkowskiDiff函数

// 计算闵可夫斯基差
Path64 polygon1 = Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 });
Path64 polygon2 = Clipper.MakePath(new long[] { -20, -20, 20, -20, 20, 20, -20, 20 });

Paths64 diff = Clipper.MinkowskiDiff(polygon1, polygon2, false);

5.3.5 闵可夫斯基和的参数

public static Paths64 MinkowskiSum(
    Path64 pattern,   // 图案多边形
    Path64 path,      // 路径
    bool isClosed     // 路径是否闭合
);

pattern（图案）：被复制到path每个顶点的形状

path（路径）：定义图案放置位置的路径

isClosed：

true：路径是闭合的多边形
false：路径是开放的折线

5.3.6 开放路径与闭合路径

using Clipper2Lib;

// 圆盘图案（正多边形近似，中心在原点）
static Path64 MakeDisk(long radius, int edgeCount = 32)
{
    Path64 disk = new Path64(edgeCount);
    for (int i = 0; i < edgeCount; i++)
    {
        double angle = 2 * Math.PI * i / edgeCount;
        disk.Add(new Point64(
            (long)Math.Round(radius * Math.Cos(angle)),
            (long)Math.Round(radius * Math.Sin(angle))));
    }
    return disk;
}

Path64 circle = MakeDisk(20);
Path64 square = Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 });  // 正方形路径

// 闭合路径：产生圆角矩形
Paths64 closedResult = Clipper.MinkowskiSum(circle, square, true);

// 开放路径：产生胶囊形
Path64 line = Clipper.MakePath(new long[] { 0, 0, 100, 0 });  // 线段路径
Paths64 openResult = Clipper.MinkowskiSum(circle, line, false);

5.3.7 实际应用示例

碰撞检测

使用闵可夫斯基差进行碰撞检测：

using Clipper2Lib;

// 两个多边形
Path64 polygonA = Clipper.MakePath(new long[] { 0, 0, 50, 0, 50, 50, 0, 50 });
Path64 polygonB = Clipper.MakePath(new long[] { 30, 30, 80, 30, 80, 80, 30, 80 });

// 计算闵可夫斯基差
Paths64 minkDiff = Clipper.MinkowskiDiff(polygonA, polygonB, true);

// 检查原点是否在闵可夫斯基差内
Point64 origin = new Point64(0, 0);
bool colliding = false;
foreach (Path64 path in minkDiff)
{
    if (Clipper.PointInPolygon(origin, path) != PointInPolygonResult.IsOutside)
    {
        colliding = true;
        break;
    }
}

if (colliding)
{
    Console.WriteLine("多边形相交！");
}

机器人路径规划

使用闵可夫斯基和计算配置空间障碍物：

// 机器人形状（以中心为原点）
Path64 robotShape = Clipper.MakePath(new long[] { -10, -10, 10, -10, 10, 10, -10, 10 });

// 障碍物列表
List<Path64> obstacles = new List<Path64>
{
    Clipper.MakePath(new long[] { 100, 100, 200, 100, 200, 200, 100, 200 }),
    Clipper.MakePath(new long[] { 300, 50, 400, 50, 400, 150, 300, 150 })
};

// 计算配置空间障碍物
Paths64 configSpaceObstacles = new Paths64();
foreach (Path64 obstacle in obstacles)
{
    // 使用机器人形状的反射
    Path64 reflectedRobot = new Path64(robotShape.Count);
    foreach (Point64 pt in robotShape)
        reflectedRobot.Add(new Point64(-pt.X, -pt.Y));

    // 闵可夫斯基和
    Paths64 expanded = Clipper.MinkowskiSum(reflectedRobot, obstacle, true);

    // 合并到配置空间障碍物
    configSpaceObstacles.AddRange(expanded);
}

// 合并重叠的障碍物
Paths64 mergedObstacles = Clipper.Union(configSpaceObstacles, FillRule.NonZero);

// 现在可以在点空间中进行路径规划，只要路径不穿过这些障碍物

形态学膨胀

使用闵可夫斯基和模拟形态学膨胀：

// 原始形状
Path64 shape = Clipper.MakePath(new long[] { 0, 0, 100, 0, 100, 100, 0, 100 });

// 结构元素（圆盘，中心在原点，MakeDisk 定义见 5.3.6）
Path64 structuringElement = MakeDisk(20);

// 形态学膨胀
Paths64 dilated = Clipper.MinkowskiSum(structuringElement, shape, true);

计算可达边界

// 移动物体的形状
Path64 movingObject = Clipper.MakePath(new long[] { -5, -5, 5, -5, 5, 5, -5, 5 });

// 轨迹路径
Path64 trajectory = Clipper.MakePath(new long[] { 0, 0, 100, 50, 200, 0, 300, 50 });

// 计算移动物体沿轨迹运动时扫过的区域
Paths64 sweptArea = Clipper.MinkowskiSum(movingObject, trajectory, false);

5.3.8 闵可夫斯基运算的性能考虑

复杂度分析

闵可夫斯基和的时间复杂度大约为O(m * n)，其中m和n分别是两个多边形的顶点数。对于复杂的多边形，这可能会很慢。

优化策略

// 1. 简化输入多边形
Path64 simplifiedPattern = Clipper.SimplifyPath(pattern, tolerance);
Path64 simplifiedPath = Clipper.SimplifyPath(path, tolerance);
Paths64 result = Clipper.MinkowskiSum(simplifiedPattern, simplifiedPath, true);

// 2. 对于凸多边形使用专门的算法（IsConvex/ConvexMinkowskiSum 需自行实现）
if (IsConvex(pattern) && IsConvex(path))
{
    Paths64 convexResult = ConvexMinkowskiSum(pattern, path);
}

// 3. 分解为凸多边形（ConvexPartition 需自行实现）
Paths64 convexPattern = ConvexPartition(pattern);
Paths64 convexPath = ConvexPartition(path);
Paths64 decomposed = new Paths64();
foreach (Path64 cp in convexPattern)
{
    foreach (Path64 cpp in convexPath)
    {
        Paths64 partial = Clipper.MinkowskiSum(cp, cpp, true);
        decomposed.AddRange(partial);
    }
}
decomposed = Clipper.Union(decomposed, FillRule.NonZero);

5.3.9 闵可夫斯基和的数学性质

交换律

A ⊕ B = B ⊕ A

结合律

(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

分配律（对于并集）

A ⊕ (B ∪ C) = (A ⊕ B) ∪ (A ⊕ C)

与原点的关系

如果O是只包含原点的点集，则 A ⊕ O = A

这些性质可以用于优化计算：

// 利用分配律分解计算
Path64 A = Clipper.MakePath(new long[] { /* A 的顶点坐标 */ });
Paths64 B = new Paths64();  // B 由多个分离的多边形组成

// 闵可夫斯基和对并集满足分配律，可把 B 分解为单个多边形分别求和后再合并
Paths64 result = new Paths64();
foreach (Path64 bi in B)
{
    Paths64 partial = Clipper.MinkowskiSum(A, bi, true);
    result.AddRange(partial);
}
result = Clipper.Union(result, FillRule.NonZero);

5.3.10 形态学操作（任意结构元素）

5.3.7 中的”形态学膨胀”只是形态学操作的一种。完整的形态学（Morphology）操作还包括腐蚀（Erode）、开运算（Open）、闭运算（Close）和形态学梯度（Gradient），它们广泛应用于矢量数据清理：剔除细小图斑、弥合窄缝、填充凹口、提取边界带等。

当结构元素是以原点为中心的圆盘时，这些操作都可以用第四章介绍的偏移函数（Clipper.InflatePaths 配 JoinType.Round）等价实现。但当结构元素是任意形状（矩形、线段、十字等）时，必须借助闵可夫斯基运算。下面给出基于闵可夫斯基运算的通用实现。

辅助函数

首先需要三个辅助函数：圆盘结构元素（MakeDisk）、包围盒补集（Complement）以及结构元素关于原点的反射（ReflectPath）。

using Clipper2Lib;

// 圆盘结构元素（正多边形近似，中心在原点）
public static Path64 MakeDisk(long radius, int edgeCount = 32)
{
    Path64 disk = new Path64(edgeCount);
    for (int i = 0; i < edgeCount; i++)
    {
        double angle = 2 * Math.PI * i / edgeCount;
        disk.Add(new Point64(
            (long)Math.Round(radius * Math.Cos(angle)),
            (long)Math.Round(radius * Math.Sin(angle))));
    }
    return disk;
}

// 补集：包围盒减去 paths
public static Paths64 Complement(Paths64 paths, Rect64 bounds)
{
    Path64 box = Clipper.MakePath(new long[] {
        bounds.left, bounds.top,
        bounds.right, bounds.top,
        bounds.right, bounds.bottom,
        bounds.left, bounds.bottom });
    return Clipper.Difference(new Paths64 { box }, paths, FillRule.NonZero);
}

// 结构元素关于原点的反射：B^r = {-b : b in B}
public static Path64 ReflectPath(Path64 pattern)
{
    Path64 reflected = new Path64(pattern.Count);
    foreach (Point64 pt in pattern)
        reflected.Add(new Point64(-pt.X, -pt.Y));
    return reflected;
}

膨胀与腐蚀

膨胀定义为闵可夫斯基和；腐蚀则通过”补集 → 膨胀 → 再取补集”实现。

// 形态学膨胀：A ⊕ B = MinkowskiSum(A, B)
public static Paths64 MorphDilate(Path64 shape, Path64 se)
    => Clipper.MinkowskiSum(shape, se, true);

// 形态学腐蚀：A ⊖ B = (A^c ⊕ B^r)^c
public static Paths64 MorphErode(Path64 shape, Path64 se)
{
    Rect64 b = Clipper.GetBounds(shape);
    Rect64 sb = Clipper.GetBounds(se);
    long w = sb.right - sb.left, h = sb.bottom - sb.top;
    Rect64 bounds = new Rect64(b.left - w, b.top - h, b.right + w, b.bottom + h);

    Paths64 comp = Complement(new Paths64 { shape }, bounds);
    Path64 seReflected = ReflectPath(se);
    Paths64 grown = new Paths64();
    foreach (Path64 p in comp)
        grown.AddRange(Clipper.MinkowskiSum(p, seReflected, true));
    return Complement(grown, bounds);
}

开运算与闭运算

开运算是先腐蚀后膨胀；闭运算是先膨胀后腐蚀。

// 开运算：(A ⊖ B) ⊕ B
public static Paths64 MorphOpen(Path64 shape, Path64 se)
{
    Paths64 eroded = MorphErode(shape, se);
    Paths64 opened = new Paths64();
    foreach (Path64 p in eroded)
        opened.AddRange(Clipper.MinkowskiSum(p, se, true));
    return Clipper.Union(opened, FillRule.NonZero);
}

// 闭运算：(A ⊕ B) ⊖ B
public static Paths64 MorphClose(Path64 shape, Path64 se)
{
    Paths64 dilated = MorphDilate(shape, se);
    Paths64 closed = new Paths64();
    foreach (Path64 p in dilated)
        closed.AddRange(MorphErode(p, se));
    return Clipper.Union(closed, FillRule.NonZero);
}

形态学梯度

// 形态学梯度：(A ⊕ B) \ (A ⊖ B)
public static Paths64 MorphGradient(Path64 shape, Path64 se)
    => Clipper.Difference(MorphDilate(shape, se), MorphErode(shape, se), FillRule.NonZero);

注意：闵可夫斯基差不等于腐蚀

闵可夫斯基差 A ⊖ B 定义为 A ⊕ (−B)，即把结构元素关于原点反射后再做闵可夫斯基和。它主要用于碰撞检测（见 5.3.7），表示”物体 B 的中心不能进入的区域”。而形态学腐蚀 A ⊖ B 是完全不同的操作——它通过”补集的膨胀再取补集”实现，用于收缩形状、剔除细小结构。二者在数学上并不等价，不可混用。

圆盘结构元素等价于偏移

当结构元素为圆盘时，上述形态学操作与第四章的 Round 偏移完全等价：

Paths64 dilated = Clipper.InflatePaths(paths,  r, JoinType.Round, EndType.Polygon);   // 膨胀
Paths64 eroded  = Clipper.InflatePaths(paths, -r, JoinType.Round, EndType.Polygon);   // 腐蚀
// 开 = 先 -r 后 +r；闭 = 先 +r 后 -r；梯度 = 膨胀 - 腐蚀

圆盘结构元素使用偏移实现更简洁高效；只有在需要非圆盘（如线段、矩形）结构元素时才必须使用本节的闵可夫斯基实现。

5.4 综合应用案例

5.4.1 地图瓦片系统

class TileSystem
{
    private readonly int tileSize;
    private readonly int maxZoom;

    public TileSystem(int tileSize = 256, int maxZoom = 20)
    {
        this.tileSize = tileSize;
        this.maxZoom = maxZoom;
    }

    public Paths64 ClipToTile(Paths64 geometry, int x, int y, int zoom)
    {
        // 计算瓦片边界
        long scale = 1L << zoom;
        long tileX = x * tileSize;
        long tileY = y * tileSize;

        Rect64 tileBounds = new Rect64(
            tileX, tileY,
            tileX + tileSize, tileY + tileSize
        );

        // 使用矩形裁剪
        return Clipper.RectClip(tileBounds, geometry);
    }

    public Dictionary<(int x, int y), Paths64> GenerateTiles(Paths64 geometry, int zoom)
    {
        var tiles = new Dictionary<(int x, int y), Paths64>();

        // 获取几何体的边界框
        Rect64 bounds = Clipper.GetBounds(geometry);

        // 计算涉及的瓦片范围
        int minTileX = (int)(bounds.left / tileSize);
        int minTileY = (int)(bounds.top / tileSize);
        int maxTileX = (int)(bounds.right / tileSize);
        int maxTileY = (int)(bounds.bottom / tileSize);

        // 为每个瓦片裁剪几何体
        for (int ty = minTileY; ty <= maxTileY; ty++)
        {
            for (int tx = minTileX; tx <= maxTileX; tx++)
            {
                Paths64 tileGeometry = ClipToTile(geometry, tx, ty, zoom);
                if (tileGeometry.Count > 0)
                {
                    tiles[(tx, ty)] = tileGeometry;
                }
            }
        }

        return tiles;
    }
}

5.4.2 碰撞检测系统

class CollisionDetector
{
    // 检测两个多边形是否碰撞
    public bool CheckCollision(Path64 polygonA, Path64 polygonB)
    {
        // 计算闵可夫斯基差
        Paths64 minkDiff = Clipper.MinkowskiDiff(polygonA, polygonB, true);

        // 检查原点是否在差集内
        Point64 origin = new Point64(0, 0);
        foreach (Path64 path in minkDiff)
        {
            if (Clipper.PointInPolygon(origin, path) != PointInPolygonResult.IsOutside)
                return true;
        }
        return false;
    }

    // 计算穿透深度和方向
    public (double distance, PointD direction) GetPenetration(Path64 polygonA, Path64 polygonB)
    {
        Paths64 minkDiff = Clipper.MinkowskiDiff(polygonA, polygonB, true);

        Point64 origin = new Point64(0, 0);
        double minDist = double.MaxValue;
        PointD minDirection = new PointD(0, 0);

        foreach (Path64 path in minkDiff)
        {
            if (Clipper.PointInPolygon(origin, path) == PointInPolygonResult.IsOutside)
                continue;

            // 找到原点到边界的最短距离
            for (int i = 0; i < path.Count; i++)
            {
                Point64 p1 = path[i];
                Point64 p2 = path[(i + 1) % path.Count];

                // 计算点到线段的距离
                double dist = DistanceToSegment(origin, p1, p2);
                if (dist < minDist)
                {
                    minDist = dist;
                    // 计算法线方向
                    double dx = p2.X - p1.X;
                    double dy = p2.Y - p1.Y;
                    double len = Math.Sqrt(dx * dx + dy * dy);
                    minDirection = new PointD(-dy / len, dx / len);
                }
            }
        }

        return (minDist, minDirection);
    }

    private double DistanceToSegment(Point64 pt, Point64 a, Point64 b)
    {
        double dx = b.X - a.X;
        double dy = b.Y - a.Y;
        double t = Math.Max(0.0, Math.Min(1.0,
            ((pt.X - a.X) * dx + (pt.Y - a.Y) * dy) / (dx * dx + dy * dy)));
        double projX = a.X + t * dx;
        double projY = a.Y + t * dy;
        return Math.Sqrt((pt.X - projX) * (pt.X - projX) +
                         (pt.Y - projY) * (pt.Y - projY));
    }
}

5.4.3 扫掠体积计算

class SweptVolume
{
    // 计算物体沿路径移动时扫过的区域
    public Paths64 ComputeSweptArea(Path64 objectShape, Path64 motionPath, bool closedPath = false)
    {
        // 使用闵可夫斯基和
        return Clipper.MinkowskiSum(objectShape, motionPath, closedPath);
    }

    // 计算旋转物体的扫掠区域（近似）
    public Paths64 ComputeRotationalSweep(Path64 objectShape, Point64 pivot,
                                          double startAngle, double endAngle, int numSteps = 36)
    {
        Paths64 result = new Paths64();

        double angleStep = (endAngle - startAngle) / numSteps;

        for (int i = 0; i <= numSteps; i++)
        {
            double angle = startAngle + i * angleStep;
            Path64 rotated = RotatePath(objectShape, pivot, angle);
            result.Add(rotated);
        }

        // 合并所有位置
        return Clipper.Union(result, FillRule.NonZero);
    }

    private Path64 RotatePath(Path64 path, Point64 pivot, double angle)
    {
        Path64 result = new Path64();
        double cosA = Math.Cos(angle);
        double sinA = Math.Sin(angle);

        foreach (Point64 pt in path)
        {
            double dx = pt.X - pivot.X;
            double dy = pt.Y - pivot.Y;
            result.Add(new Point64(
                (long)(pivot.X + dx * cosA - dy * sinA),
                (long)(pivot.Y + dx * sinA + dy * cosA)
            ));
        }

        return result;
    }
}

5.4.4 安全区域计算

class SafetyZoneCalculator
{
    // 计算机器人的安全导航区域
    public Paths64 ComputeSafeZone(Paths64 obstacles, Path64 robotShape, double additionalMargin = 0)
    {
        Paths64 expandedObstacles = new Paths64();

        // 计算机器人形状的反射
        Path64 reflectedRobot = new Path64(robotShape.Count);
        foreach (Point64 pt in robotShape)
            reflectedRobot.Add(new Point64(-pt.X, -pt.Y));

        // 如果需要额外边距，先膨胀反射形状
        Path64 marginedRobot = reflectedRobot;
        if (additionalMargin > 0)
        {
            Paths64 inflated = Clipper.InflatePaths(new Paths64 { reflectedRobot },
                                                    additionalMargin,
                                                    JoinType.Round,
                                                    EndType.Polygon);
            if (inflated.Count > 0)
            {
                marginedRobot = inflated[0];
            }
        }

        // 扩展每个障碍物
        foreach (Path64 obstacle in obstacles)
        {
            Paths64 expanded = Clipper.MinkowskiSum(marginedRobot, obstacle, true);
            expandedObstacles.AddRange(expanded);
        }

        // 合并重叠的障碍物
        return Clipper.Union(expandedObstacles, FillRule.NonZero);
    }

    // 计算工作区域内的可用空间
    public Paths64 ComputeFreeSpace(Path64 workspace, Paths64 obstacles, Path64 robotShape)
    {
        Paths64 expandedObstacles = ComputeSafeZone(obstacles, robotShape);
        return Clipper.Difference(new Paths64 { workspace }, expandedObstacles, FillRule.NonZero);
    }
}

5.5 性能对比

5.5.1 矩形裁剪 vs 布尔交集

using System;
using System.Diagnostics;
using Clipper2Lib;

static void BenchmarkRectClip()
{
    // 创建测试数据
    Paths64 subject = new Paths64();
    for (int i = 0; i < 100; i++)
        subject.Add(MakeRandomPolygon());  // MakeRandomPolygon 为自定义随机多边形生成函数

    Rect64 clipRect = new Rect64(0, 0, 500, 500);
    Paths64 clipPolygon = new Paths64();
    clipPolygon.Add(Clipper.MakePath(new long[] { 0, 0, 500, 0, 500, 500, 0, 500 }));

    // 测试矩形裁剪
    var sw1 = Stopwatch.StartNew();
    for (int i = 0; i < 1000; i++)
    {
        Paths64 result = Clipper.RectClip(clipRect, subject);
    }
    sw1.Stop();

    // 测试布尔交集
    var sw2 = Stopwatch.StartNew();
    for (int i = 0; i < 1000; i++)
    {
        Paths64 result = Clipper.Intersect(subject, clipPolygon, FillRule.NonZero);
    }
    sw2.Stop();

    Console.WriteLine($"矩形裁剪: {sw1.ElapsedMilliseconds} ms");
    Console.WriteLine($"布尔交集: {sw2.ElapsedMilliseconds} ms");
}

典型结果显示，矩形裁剪比布尔交集快2-5倍。

5.6 本章小结

本章我们学习了Clipper2的两个专门几何操作：

矩形裁剪
- RectClip和RectClipLines函数
- RectClip64和RectClipLines64类
- 性能优势和使用场景
- 地图瓦片生成、视窗裁剪等应用
闵可夫斯基运算
- 闵可夫斯基和与闵可夫斯基差
- MinkowskiSum和MinkowskiDiff函数
- 碰撞检测、机器人路径规划等应用
- 性能考虑和优化策略
形态学操作
- 膨胀（闵可夫斯基和）与腐蚀（补集法）
- 开运算、闭运算、形态学梯度
- 圆盘结构元素等价于偏移，任意结构元素用闵可夫斯基运算
- 注意闵可夫斯基差不等于腐蚀
综合应用
- 地图瓦片系统
- 碰撞检测系统
- 扫掠体积计算
- 安全区域计算

在下一章中，我们将学习Clipper2的高级应用技巧和性能优化方法。

第五章 矩形裁剪与闵可夫斯基操作（C#版）