📅 发布时间：2026/6/19 12:36:19

第五章矩形裁剪与闵可夫斯基操作（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函数用于裁剪闭合多边形：

#include "clipper2/clipper.h"
using namespace Clipper2Lib;int main() {// 创建要裁剪的多边形Paths64 subject;subject.push_back(MakePath({0, 0, 200, 0, 200, 200, 0, 200}));subject.push_back(MakePath({50, 50, 150, 50, 150, 150, 50, 150}));  // 孔洞// 定义裁剪矩形Rect64 clipRect(25, 25, 175, 175);// 执行矩形裁剪Paths64 result = RectClip(clipRect, subject);// result 包含裁剪后的多边形return 0;
}

5.2.4 使用RectClipLines函数

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

// 创建开放折线
Paths64 lines;
lines.push_back(MakePath({0, 100, 200, 100}));  // 水平线
lines.push_back(MakePath({100, 0, 100, 200}));  // 垂直线
lines.push_back(MakePath({0, 0, 200, 200}));    // 对角线// 定义裁剪矩形
Rect64 clipRect(50, 50, 150, 150);// 裁剪折线
Paths64 result = RectClipLines(clipRect, lines);
// result 包含被裁剪到矩形内的线段

5.2.5 RectClip64类

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

// 创建裁剪对象
Rect64 clipRect(0, 0, 100, 100);
RectClip64 rectClipper(clipRect);// 裁剪多个多边形
for (const auto& polygon : polygons) {Paths64 result = rectClipper.Execute(Paths64{polygon});ProcessResult(result);
}

5.2.6 RectClipLines64类

类似地，对于折线裁剪：

Rect64 clipRect(0, 0, 100, 100);
RectClipLines64 lineClipper(clipRect);for (const auto& line : lines) {Paths64 result = lineClipper.Execute(Paths64{line});ProcessResult(result);
}

5.2.7 浮点数版本

使用浮点数坐标的版本：

// 浮点数矩形裁剪
PathsD subject;
subject.push_back(MakePathD({0.0, 0.0, 10.0, 0.0, 10.0, 10.0, 0.0, 10.0}));RectD clipRect(2.5, 2.5, 7.5, 7.5);PathsD result = RectClip(clipRect, subject);

5.2.8 矩形裁剪的边界情况

边界上的顶点

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

// 顶点在边界上的多边形
Paths64 subject;
subject.push_back(MakePath({50, 0, 100, 50, 50, 100, 0, 50}));  // 菱形Rect64 clipRect(0, 0, 100, 100);  // 边界与菱形顶点重合
Paths64 result = RectClip(clipRect, subject);

完全在矩形内的多边形

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

Paths64 subject;
subject.push_back(MakePath({25, 25, 75, 25, 75, 75, 25, 75}));Rect64 clipRect(0, 0, 100, 100);
Paths64 result = RectClip(clipRect, subject);
// result 与 subject 相同

完全在矩形外的多边形

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

Paths64 subject;
subject.push_back(MakePath({200, 200, 300, 200, 300, 300, 200, 300}));Rect64 clipRect(0, 0, 100, 100);
Paths64 result = RectClip(clipRect, subject);
// result 为空

5.2.9 矩形裁剪的应用场景

地图瓦片生成

// 生成256x256的地图瓦片
void GenerateTile(int tileX, int tileY, int zoom, const Paths64& mapData) {// 计算瓦片的地理范围int tileSize = 256;int worldSize = tileSize << zoom;Rect64 tileBounds(tileX * tileSize,tileY * tileSize,(tileX + 1) * tileSize,(tileY + 1) * tileSize);// 裁剪地图数据到瓦片范围Paths64 tileData = RectClip(tileBounds, mapData);// 渲染瓦片RenderTile(tileData);
}

视窗裁剪

// 裁剪到可见视窗区域
Paths64 ClipToViewport(const Paths64& geometry, int viewportWidth, int viewportHeight,int scrollX, int scrollY) {Rect64 viewport(scrollX,scrollY,scrollX + viewportWidth,scrollY + viewportHeight);return RectClip(viewport, geometry);
}

空间分区

// 将几何体分配到四叉树节点
void QuadTreeInsert(QuadTreeNode& node, const Paths64& geometry) {Rect64 nodeBounds = node.getBounds();Paths64 clipped = RectClip(nodeBounds, geometry);if (!clipped.empty()) {if (node.isLeaf() || Area(clipped) < threshold) {node.addGeometry(clipped);} else {// 分配到子节点for (auto& child : 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提供了闵可夫斯基和函数：

#include "clipper2/clipper.h"
using namespace Clipper2Lib;int main() {// 创建第一个多边形（矩形）Path64 pattern = MakePath({-50, -50, 50, -50, 50, 50, -50, 50});// 创建第二个多边形（三角形，以原点为中心）Path64 path = MakePath({0, -30, 26, 15, -26, 15});// 计算闵可夫斯基和Paths64 result = MinkowskiSum(pattern, path, false);// 参数：pattern（图案）, path（路径）, isClosed（路径是否闭合）return 0;
}

5.3.4 使用MinkowskiDiff函数

// 计算闵可夫斯基差
Path64 polygon1 = MakePath({0, 0, 100, 0, 100, 100, 0, 100});
Path64 polygon2 = MakePath({-20, -20, 20, -20, 20, 20, -20, 20});Paths64 diff = MinkowskiDiff(polygon1, polygon2, false);

5.3.5 闵可夫斯基和的参数

Paths64 MinkowskiSum(const Path64& pattern,    // 图案多边形const Path64& path,       // 路径bool pathIsClosed,        // 路径是否闭合FillRule fillRule = FillRule::NonZero  // 填充规则
);

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

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

pathIsClosed：

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

5.3.6 开放路径与闭合路径

// 闭合路径的闵可夫斯基和
Path64 circle = MakeCircle(Point64(0, 0), 20);  // 圆形图案
Path64 square = MakePath({0, 0, 100, 0, 100, 100, 0, 100});  // 正方形路径// 闭合路径：产生圆角矩形
Paths64 closedResult = MinkowskiSum(circle, square, true);// 开放路径：产生胶囊形
Path64 line = MakePath({0, 0, 100, 0});  // 线段路径
Paths64 openResult = MinkowskiSum(circle, line, false);

5.3.7 实际应用示例

碰撞检测

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

// 两个多边形
Path64 polygonA = MakePath({0, 0, 50, 0, 50, 50, 0, 50});
Path64 polygonB = MakePath({30, 30, 80, 30, 80, 80, 30, 80});// 计算闵可夫斯基差
Paths64 minkDiff = MinkowskiDiff(polygonA, polygonB, true);// 检查原点是否在闵可夫斯基差内
Point64 origin(0, 0);
bool colliding = false;
for (const auto& path : minkDiff) {if (PointInPolygon(origin, path) != PointInPolygonResult::IsOutside) {colliding = true;break;}
}if (colliding) {std::cout << "多边形相交！" << std::endl;
}

机器人路径规划

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

// 机器人形状（以中心为原点）
Path64 robotShape = MakePath({-10, -10, 10, -10, 10, 10, -10, 10});// 障碍物列表
std::vector<Path64> obstacles = {MakePath({100, 100, 200, 100, 200, 200, 100, 200}),MakePath({300, 50, 400, 50, 400, 150, 300, 150})
};// 计算配置空间障碍物
Paths64 configSpaceObstacles;
for (const auto& obstacle : obstacles) {// 使用机器人形状的反射Path64 reflectedRobot;for (const auto& pt : robotShape) {reflectedRobot.push_back(Point64(-pt.x, -pt.y));}// 闵可夫斯基和Paths64 expanded = MinkowskiSum(reflectedRobot, obstacle, true);// 合并到配置空间障碍物configSpaceObstacles.insert(configSpaceObstacles.end(),expanded.begin(), expanded.end());
}// 合并重叠的障碍物
Paths64 mergedObstacles = Union(configSpaceObstacles, FillRule::NonZero);// 现在可以在点空间中进行路径规划，只要路径不穿过这些障碍物

形态学膨胀

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

// 原始形状
Path64 shape = MakePath({...});// 结构元素（圆形）
Path64 structuringElement = MakeCircle(Point64(0, 0), radius);// 形态学膨胀
Paths64 dilated = MinkowskiSum(structuringElement, shape, true);

计算可达边界

// 移动物体的形状
Path64 movingObject = MakePath({-5, -5, 5, -5, 5, 5, -5, 5});// 轨迹路径
Path64 trajectory = MakePath({0, 0, 100, 50, 200, 0, 300, 50});// 计算移动物体沿轨迹运动时扫过的区域
Paths64 sweptArea = MinkowskiSum(movingObject, trajectory, false);

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

复杂度分析

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

优化策略

// 1. 简化输入多边形
Path64 simplifiedPattern = SimplifyPath(pattern, tolerance);
Path64 simplifiedPath = SimplifyPath(path, tolerance);
Paths64 result = MinkowskiSum(simplifiedPattern, simplifiedPath, true);// 2. 对于凸多边形使用专门的算法
if (IsConvex(pattern) && IsConvex(path)) {// 凸多边形的闵可夫斯基和可以更高效地计算Paths64 result = ConvexMinkowskiSum(pattern, path);
}// 3. 分解为凸多边形
Paths64 convexPattern = ConvexPartition(pattern);
Paths64 convexPath = ConvexPartition(path);
Paths64 result;
for (const auto& cp : convexPattern) {for (const auto& cpp : convexPath) {Paths64 partial = MinkowskiSum(cp, cpp, true);result.insert(result.end(), partial.begin(), partial.end());}
}
result = Union(result, 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

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

// 利用分配律分解计算
Paths64 A = ...;
Paths64 B = ...;  // B由多个分离的多边形组成// 方法1：直接计算（如果B是一个Paths）
// Paths64 result = MinkowskiSum(A, B);// 方法2：分解计算（可能更快）
Paths64 result;
for (const auto& bi : B) {Paths64 partial = MinkowskiSum(A[0], bi, true);result.insert(result.end(), partial.begin(), partial.end());
}
result = Union(result, FillRule::NonZero);

5.4 综合应用案例

5.4.1 地图瓦片系统

class TileSystem {
private:int tileSize_;int maxZoom_;public:TileSystem(int tileSize = 256, int maxZoom = 20): tileSize_(tileSize), maxZoom_(maxZoom) {}Paths64 ClipToTile(const Paths64& geometry, int x, int y, int zoom) const {// 计算瓦片边界int64_t scale = 1LL << zoom;int64_t tileX = x * tileSize_;int64_t tileY = y * tileSize_;Rect64 tileBounds(tileX, tileY,tileX + tileSize_, tileY + tileSize_);// 使用矩形裁剪return RectClip(tileBounds, geometry);}std::map<std::pair<int, int>, Paths64> GenerateTiles(const Paths64& geometry, int zoom) const {std::map<std::pair<int, int>, Paths64> tiles;// 获取几何体的边界框Rect64 bounds = Bounds(geometry);// 计算涉及的瓦片范围int minTileX = bounds.left / tileSize_;int minTileY = bounds.top / tileSize_;int maxTileX = bounds.right / tileSize_;int maxTileY = 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.empty()) {tiles[{tx, ty}] = std::move(tileGeometry);}}}return tiles;}
};

5.4.2 碰撞检测系统

class CollisionDetector {
public:// 检测两个多边形是否碰撞bool CheckCollision(const Path64& polygonA, const Path64& polygonB) const {// 计算闵可夫斯基差Paths64 minkDiff = MinkowskiDiff(polygonA, polygonB, true);// 检查原点是否在差集内Point64 origin(0, 0);for (const auto& path : minkDiff) {auto result = PointInPolygon(origin, path);if (result != PointInPolygonResult::IsOutside) {return true;}}return false;}// 计算穿透深度和方向std::pair<double, PointD> GetPenetration(const Path64& polygonA, const Path64& polygonB) const {Paths64 minkDiff = MinkowskiDiff(polygonA, polygonB, true);Point64 origin(0, 0);double minDist = std::numeric_limits<double>::max();PointD minDirection(0, 0);for (const auto& path : minkDiff) {auto result = PointInPolygon(origin, path);if (result == PointInPolygonResult::IsOutside) {continue;}// 找到原点到边界的最短距离for (size_t i = 0; i < path.size(); i++) {Point64 p1 = path[i];Point64 p2 = path[(i + 1) % path.size()];// 计算点到线段的距离double dist = DistanceToSegment(origin, p1, p2);if (dist < minDist) {minDist = dist;// 计算法线方向PointD edge(p2.x - p1.x, p2.y - p1.y);double len = std::sqrt(edge.x * edge.x + edge.y * edge.y);minDirection = PointD(-edge.y / len, edge.x / len);}}}return {minDist, minDirection};}private:double DistanceToSegment(const Point64& pt, const Point64& a, const Point64& b) const {double dx = b.x - a.x;double dy = b.y - a.y;double t = std::max(0.0, std::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 std::sqrt((pt.x - projX) * (pt.x - projX) + (pt.y - projY) * (pt.y - projY));}
};

5.4.3 扫掠体积计算

class SweptVolume {
public:// 计算物体沿路径移动时扫过的区域Paths64 ComputeSweptArea(const Path64& objectShape,const Path64& motionPath,bool closedPath = false) const {// 使用闵可夫斯基和return MinkowskiSum(objectShape, motionPath, closedPath);}// 计算旋转物体的扫掠区域（近似）Paths64 ComputeRotationalSweep(const Path64& objectShape,const Point64& pivot,double startAngle,double endAngle,int numSteps = 36) const {Paths64 result;double angleStep = (endAngle - startAngle) / numSteps;for (int i = 0; i <= numSteps; i++) {double angle = startAngle + i * angleStep;Path64 rotated = RotatePath(objectShape, pivot, angle);result.push_back(rotated);}// 合并所有位置return Union(result, FillRule::NonZero);}private:Path64 RotatePath(const Path64& path, const Point64& pivot, double angle) const {Path64 result;double cosA = std::cos(angle);double sinA = std::sin(angle);for (const auto& pt : path) {double dx = pt.x - pivot.x;double dy = pt.y - pivot.y;result.push_back(Point64(static_cast<int64_t>(pivot.x + dx * cosA - dy * sinA),static_cast<int64_t>(pivot.y + dx * sinA + dy * cosA)));}return result;}
};

5.4.4 安全区域计算

class SafetyZoneCalculator {
public:// 计算机器人的安全导航区域Paths64 ComputeSafeZone(const Paths64& obstacles,const Path64& robotShape,double additionalMargin = 0) const {Paths64 expandedObstacles;// 计算机器人形状的反射Path64 reflectedRobot;for (const auto& pt : robotShape) {reflectedRobot.push_back(Point64(-pt.x, -pt.y));}// 如果需要额外边距，先膨胀反射形状Path64 marginedRobot = reflectedRobot;if (additionalMargin > 0) {Paths64 inflated = InflatePaths(Paths64{reflectedRobot}, additionalMargin,JoinType::Round, EndType::Polygon);if (!inflated.empty()) {marginedRobot = inflated[0];}}// 扩展每个障碍物for (const auto& obstacle : obstacles) {Paths64 expanded = MinkowskiSum(marginedRobot, obstacle, true);expandedObstacles.insert(expandedObstacles.end(),expanded.begin(), expanded.end());}// 合并重叠的障碍物return Union(expandedObstacles, FillRule::NonZero);}// 计算工作区域内的可用空间Paths64 ComputeFreeSpace(const Path64& workspace,const Paths64& obstacles,const Path64& robotShape) const {Paths64 expandedObstacles = ComputeSafeZone(obstacles, robotShape);return Difference(Paths64{workspace}, expandedObstacles, FillRule::NonZero);}
};

5.5 性能对比

5.5.1 矩形裁剪 vs 布尔交集

#include <chrono>void BenchmarkRectClip() {// 创建测试数据Paths64 subject;for (int i = 0; i < 100; i++) {subject.push_back(MakeRandomPolygon());}Rect64 clipRect(0, 0, 500, 500);Paths64 clipPolygon;clipPolygon.push_back(MakePath({0, 0, 500, 0, 500, 500, 0, 500}));// 测试矩形裁剪auto start1 = std::chrono::high_resolution_clock::now();for (int i = 0; i < 1000; i++) {Paths64 result = RectClip(clipRect, subject);}auto end1 = std::chrono::high_resolution_clock::now();// 测试布尔交集auto start2 = std::chrono::high_resolution_clock::now();for (int i = 0; i < 1000; i++) {Paths64 result = Intersect(subject, clipPolygon, FillRule::NonZero);}auto end2 = std::chrono::high_resolution_clock::now();auto rectTime = std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start1);auto boolTime = std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2);std::cout << "矩形裁剪: " << rectTime.count() << " ms" << std::endl;std::cout << "布尔交集: " << boolTime.count() << " ms" << std::endl;
}

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

5.6 本章小结

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

矩形裁剪
- RectClip和RectClipLines函数
- RectClip64和RectClipLines64类
- 性能优势和使用场景
- 地图瓦片生成、视窗裁剪等应用
闵可夫斯基运算
- 闵可夫斯基和与闵可夫斯基差
- MinkowskiSum和MinkowskiDiff函数
- 碰撞检测、机器人路径规划等应用
- 性能考虑和优化策略
综合应用
- 地图瓦片系统
- 碰撞检测系统
- 扫掠体积计算
- 安全区域计算

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

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

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

5.1 引言

5.2 矩形裁剪

5.2.1 什么是矩形裁剪

5.2.2 矩形裁剪的优势

5.2.3 使用RectClip函数

5.2.4 使用RectClipLines函数

5.2.5 RectClip64类

5.2.6 RectClipLines64类

5.2.7 浮点数版本

5.2.8 矩形裁剪的边界情况

5.2.9 矩形裁剪的应用场景

5.3 闵可夫斯基运算

5.3.1 什么是闵可夫斯基运算

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

5.3.3 使用MinkowskiSum函数

5.3.4 使用MinkowskiDiff函数

5.3.5 闵可夫斯基和的参数

5.3.6 开放路径与闭合路径

5.3.7 实际应用示例

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

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

5.4 综合应用案例

5.4.1 地图瓦片系统

5.4.2 碰撞检测系统

5.4.3 扫掠体积计算

5.4.4 安全区域计算

5.5 性能对比

5.5.1 矩形裁剪 vs 布尔交集

5.6 本章小结

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

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