Minkowski和与差如何成？

第18章：Minkowski 和与差 18.1 概述 Minkowski 和与差是两种重要的几何运算，在碰撞检测、运动规划、膨胀/腐蚀等领域有广泛应用。Clipper2 提供了这些运算的实现。 18.2 数学定义 18.2.1 Minkowski 和 给定两个点集 A 和 B，它们的 Minkowski 和定义为： A ⊕ B = { a + b | a ∈ A, b ∈ B } 即 A 中的每个点与 B 中的每个点相加得到的所有点的集合。 18.2.2 Minkowski 差 A ⊖ B = { a - b | a ∈ A, b ∈ B } = A ⊕ (-B) 即 A 与 B 的反射的 Minkowski 和。 18.2.3 几何意义 Minkowski 和的几何意义： 将形状 B 的中心沿着形状 A 的边界移动，B 扫过的区域 A B A ⊕ B ┌─────┐ ┌──┐ ┌───────┐ │ │ ⊕ │ │ = │ │ │ │ └──┘ │ │ └─────┘ │ │ └───────┘ (圆角化) 18.3 Clipper2 中的实现 18.3.1 MinkowskiSum 方法 public static Paths64 MinkowskiSum(Path64 pattern, Path64 path, bool isClosed) { return Minkowski(pattern, path, true, isClosed); } public static PathsD MinkowskiSum(PathD pattern, PathD path, bool isClosed, int precision = 2) { InternalClipper.CheckPrecision(precision); double scale = Math.Pow(10, precision); Path64 pattern64 = Clipper.ScalePath64(pattern, scale); Path64 path64 = Clipper.ScalePath64(path, scale); Paths64 result64 = Minkowski(pattern64, path64, true, isClosed); return Clipper.ScalePathsD(result64, 1.0 / scale); } 18.3.2 MinkowskiDiff 方法 public static Paths64 MinkowskiDiff(Path64 pattern, Path64 path, bool isClosed) { return Minkowski(pattern, path, false, isClosed); } 18.3.3 Minkowski 核心实现 private static Paths64 Minkowski(Path64 pattern, Path64 path, bool isSum, bool isClosed) { int patternCnt = pattern.Count; int pathCnt = path.Count; if (patternCnt == 0 || pathCnt == 0) return new Paths64(); // 如果是差集，反转 pattern Path64 pat = isSum ? pattern : ReversePath(pattern); // 计算所有边的 Minkowski 结果 Paths64 result = new Paths64(); if (isClosed) { // 闭合路径 for (int i = 0; i < pathCnt; i++) { Path64 quad = TranslatePath(pat, path[i]); result.Add(quad); } } else { // 开放路径 for (int i = 0; i < pathCnt - 1; i++) { Path64 quad = TranslatePath(pat, path[i]); result.Add(quad); } // 最后一点 Path64 lastQuad = TranslatePath(pat, path[pathCnt - 1]); result.Add(lastQuad); } // 使用裁剪器合并所有结果 Clipper64 clipper = new Clipper64(); clipper.AddSubject(result); Paths64 solution = new Paths64(); clipper.Execute(ClipType.Union, FillRule.NonZero, solution); return solution; } 18.4 TranslatePath 18.4.1 实现 private static Path64 TranslatePath(Path64 path, Point64 delta) { Path64 result = new Path64(path.Count); foreach (Point64 pt in path) { result.Add(new Point64(pt.X + delta.X, pt.Y + delta.Y)); } return result; } 18.4.2 作用示意 原始 pattern: 平移到 path[i]: ○──○ ○──○ │ │ + (dx, dy) = │ │ ○──○ ○──○ ↑ 位于 path[i] 位置 18.5 详细算法 18.5.1 凸多边形 Minkowski 和 对于凸多边形，有更高效的算法： private static Path64 ConvexMinkowskiSum(Path64 a, Path64 b) { // 确保都是逆时针 if (!IsPositive(a)) a = ReversePath(a); if (!IsPositive(b)) b = ReversePath(b); // 合并边的旋转角 int i = IndexOfLowestPoint(a); int j = IndexOfLowestPoint(b); int lenA = a.Count; int lenB = b.Count; Path64 result = new Path64(lenA + lenB); int iEnd = i + lenA; int jEnd = j + lenB; while (i < iEnd || j < jEnd) { // 添加当前点 result.Add(new Point64( a[i % lenA].X + b[j % lenB].X, a[i % lenA].Y + b[j % lenB].Y )); // 比较边的角度，选择较小的前进 double angleA = EdgeAngle(a, i % lenA); double angleB = EdgeAngle(b, j % lenB); if (angleA < angleB) i++; else if (angleB < angleA) j++; else { i++; j++; } } return result; } 18.5.2 通用算法 对于非凸多边形，使用分解方法： private static Paths64 GeneralMinkowskiSum(Path64 pattern, Path64 path) { Paths64 result = new Paths64(); int pathLen = path.Count; int patternLen = pattern.Count; // 对于路径的每条边 for (int i = 0; i < pathLen; i++) { int j = (i + 1) % pathLen; // 创建边对应的四边形 Path64 quad = new Path64(patternLen * 2); // 沿着 pattern 平移 for (int k = 0; k < patternLen; k++) { quad.Add(new Point64( path[i].X + pattern[k].X, path[i].Y + pattern[k].Y )); } for (int k = patternLen - 1; k >= 0; k--) { quad.Add(new Point64( path[j].X + pattern[k].X, path[j].Y + pattern[k].Y )); } result.Add(quad); } // 合并所有四边形 return Clipper.Union(result, FillRule.NonZero); } 18.6 应用场景 18.6.1 碰撞检测 // 检测两个多边形是否碰撞 bool CheckCollision(Path64 polyA, Path64 polyB) { // 计算 Minkowski 差 Paths64 diff = Clipper.MinkowskiDiff(polyA, polyB, true); // 如果原点在差集内，则碰撞 Point64 origin = new Point64(0, 0); foreach (Path64 path in diff) { if (Clipper.PointInPolygon(origin, path) != PointInPolygonResult.IsOutside) { return true; // 碰撞 } } return false; // 无碰撞 } 18.6.2 机器人运动规划 // 计算机器人可以移动的空间 Paths64 ComputeConfigurationSpace(Path64 robot, Paths64 obstacles) { // 机器人围绕参考点（通常是中心） Path64 robotCentered = CenterPath(robot); Paths64 expandedObstacles = new Paths64(); foreach (Path64 obstacle in obstacles) { // 每个障碍物膨胀为 Minkowski 和 Paths64 expanded = Clipper.MinkowskiSum( robotCentered, obstacle, true); expandedObstacles.AddRange(expanded); } // 合并所有膨胀后的障碍物 return Clipper.Union(expandedObstacles, FillRule.NonZero); } 18.6.3 形态学操作 // 膨胀操作 Paths64 Dilate(Path64 shape, Path64 structuringElement) { // 膨胀 = Minkowski 和 return Clipper.MinkowskiSum(structuringElement, shape, true); } // 腐蚀操作 Paths64 Erode(Path64 shape, Path64 structuringElement) { // 腐蚀 = Minkowski 差（的边界内部） // 需要更复杂的处理... Path64 reflected = ReflectPath(structuringElement); Paths64 diff = Clipper.MinkowskiDiff(shape, reflected, true); return diff; } 18.7 性能优化 18.7.1 简化 pattern // 减少 pattern 的点数可以提高性能 Path64 SimplifyPattern(Path64 pattern, double tolerance) { return Clipper.SimplifyPath(pattern, tolerance); } 18.7.2 凸壳优化 // 如果只需要外轮廓，可以使用凸壳 Path64 ConvexHullMinkowski(Path64 pattern, Path64 path) { // 对于凸多边形，Minkowski 和的结果也是凸的 Path64 hullA = Clipper.ConvexHull(pattern); Path64 hullB = Clipper.ConvexHull(path); return ConvexMinkowskiSum(hullA, hullB); } 18.7.3 分而治之 // 对于大型路径，可以分段处理 Paths64 MinkowskiSumLarge(Path64 pattern, Path64 path) { const int chunkSize = 100; if (path.Count <= chunkSize) { return Clipper.MinkowskiSum(pattern, path, true); } Paths64 result = new Paths64(); for (int i = 0; i < path.Count; i += chunkSize) { int end = Math.Min(i + chunkSize + 1, path.Count); Path64 chunk = path.GetRange(i, end - i); Paths64 chunkResult = Clipper.MinkowskiSum(pattern, chunk, false); result.AddRange(chunkResult); } return Clipper.Union(result, FillRule.NonZero); } 18.8 使用示例 18.8.1 基本 Minkowski 和 // 正方形 pattern Path64 square = new Path64 { new Point64(-10, -10), new Point64(10, -10), new Point64(10, 10), new Point64(-10, 10) }; // 三角形路径 Path64 triangle = new Path64 { new Point64(0, 0), new Point64(100, 0), new Point64(50, 100) }; // 计算 Minkowski 和 Paths64 result = Clipper.MinkowskiSum(square, triangle, true); // 结果是三角形"膨胀"了正方形的大小 18.8.2 Minkowski 差用于碰撞 Path64 movingObject = CreateRectangle(0, 0, 20, 20); Path64 obstacle = CreateRectangle(50, 50, 30, 30); // 计算 Minkowski 差 Paths64 diff = Clipper.MinkowskiDiff(obstacle, movingObject, true); // 检查移动目标位置是否碰撞 Point64 targetPosition = new Point64(40, 40); bool willCollide = IsPointInPaths(targetPosition, diff); 18.8.3 浮点版本 PathD circleApprox = CreateCircleApprox(0, 0, 5.0, 32); PathD complexPath = LoadPathFromFile("path.dat"); // 使用浮点计算 PathsD result = Clipper.MinkowskiSum(circleApprox, complexPath, true, 3); 18.9 注意事项 18.9.1 路径方向 // Minkowski 和要求路径是逆时针的 // 确保方向正确 if (!Clipper.IsPositive(pattern)) pattern = Clipper.ReversePath(pattern); if (!Clipper.IsPositive(path)) path = Clipper.ReversePath(path); 18.9.2 自相交处理 // Minkowski 和可能产生自相交 // 结果通过 Union 自动清理 Paths64 raw = MinkowskiSumRaw(pattern, path); Paths64 clean = Clipper.Union(raw, FillRule.NonZero); 18.9.3 性能考量 时间复杂度：O(n * m + k log k) - n = pattern 点数 - m = path 点数 - k = 结果点数 空间复杂度：O(n * m) 18.10 本章小结 Minkowski 和与差是强大的几何运算： Minkowski 和：形状膨胀、扫描区域 Minkowski 差：碰撞检测、穿透深度 应用广泛：机器人、游戏、CAD 实现方式：分解为平移 + 并集 优化方法：凸壳、分段处理 正确使用这些运算可以解决许多实际问题。 上一章：RectClip矩形裁剪优化 | 返回目录 | 下一章：PolyTree多边形树结构