1. 从一个几何直觉问题说起最近在整理一些计算几何相关的笔记翻到了“闵可夫斯基和”这个概念。说实话第一次听到这个名字感觉挺唬人的像是某种高深的数学理论。但当我真正去理解它背后的几何意义和实际应用后发现它其实是一个非常直观、且在某些场景下极其有用的工具。它不是什么空中楼阁而是解决一类特定几何问题的“瑞士军刀”。简单来说闵可夫斯基和描述的是两个图形通常是凸多边形或点集所有点向量相加后得到的新图形。如果你想象两个图形一个固定另一个在上面“滑动”那么闵可夫斯基和就是这个滑动过程中另一个图形的参考点比如它的原点所扫过的区域。为什么我们需要关心这个一个最经典的动机是碰撞检测。想象一下在游戏开发或者机器人路径规划中我们有两个形状复杂的物体A和B。我们想知道它们是否会发生碰撞。一个朴素的想法是去检测A的每个点是否在B内部或者检测它们的边是否相交这在形状复杂时计算量会很大。而利用闵可夫斯基和我们可以将“两个物体是否相交”的问题转化为“一个点是否在一个新的图形内部”的问题。具体来说我们计算B相对于A的闵可夫斯基差可以理解为A和(-B)的闵可夫斯基和那么A和B相交当且仅当坐标原点在这个闵可夫斯基差图形内部。这样一来问题就简化为了更高效的点在多边形内的包含性检测。另一个常见的应用场景是运动规划。假设一个机器人可以看作一个凸多边形需要在一个有障碍物的环境中移动。我们可以将机器人“收缩”为一个点同时将每个障碍物根据机器人的形状进行“膨胀”。这个膨胀操作本质上就是障碍物与机器人的闵可夫斯基和。规划机器人的路径就变成了为这个点在新生成的“膨胀障碍物”地图中寻找一条无碰撞路径这大大简化了问题。所以无论你是做图形学、游戏物理、机器人导航还是算法竞赛理解闵可夫斯基和都能为你打开一扇新的大门。它把两个物体间的相对位置关系巧妙地映射到了一个物体与一个点的关系上。2. 闵可夫斯基和的严格定义与核心性质在深入算法之前我们必须先把它从直观理解上升到准确定义这样才能确保后续的所有推导和实现都是坚实的。2.1 形式化定义给定欧几里得空间中的两个点集集合A和B它们的闵可夫斯基和Minkowski Sum记作 A ⊕ B定义为 A ⊕ B { a b | a ∈ A, b ∈ B } 其中a b 表示向量a和向量b的逐分量相加。换句话说新集合中的每一个点都是来自A的一个点和来自B的一个点的向量和。关键理解向量加法视角这是最本质的视角。我们把集合A和B都看作向量的集合。闵可夫斯基和就是所有可能的向量和的集合。滑动视角固定集合A将集合B看作一个“画笔”让B的参考点通常是其局部坐标系原点扫过A的每一个点那么B本身所经过的所有位置点的并集就是A ⊕ B。这个视角对于理解其几何形状非常有帮助。卷积视角在信号处理或图像处理中这类似于两个集合的卷积。不过我们这里只做几何上的理解。2.2 针对凸多边形的重要性质当A和B都是凸集特别是我们最常处理的凸多边形时闵可夫斯基和展现出非常优美的性质这些性质正是我们能高效计算它的基础凸性保持如果A和B是凸集那么A ⊕ B也是凸集。这是一个非常重要的性质它保证了结果仍然是“规则”的没有凹陷便于处理。边界的构成凸多边形A ⊕ B的边界是由A和B的边按极角与x轴正方向的夹角排序后依次首尾相连得到的。更具体地说如果我们把A和B的边都视为向量从当前顶点指向下一个顶点那么结果凸包的边向量集合就是A和B所有边向量的并集并按极角排序后的序列。这个性质是后续“和排序”算法的直接依据。顶点与边的关系A ⊕ B的每一个顶点都是A的一个顶点与B的一个顶点的和。但是并非所有顶点对的和都会成为结果凸包的顶点。只有那些在各自多边形上“朝外”方向一致的顶点对它们的和才会出现在最终的凸包上。这引出了下一个关键概念。支撑函数Support Function这是理解闵可夫斯基和与碰撞检测Gilbert–Johnson–Keerthi, GJK算法关系的核心。对于凸集C和给定方向向量d其支撑函数s_C(d)返回的是在d方向上C的极值点即 argmax_{c ∈ C} (c · d)点积最大。闵可夫斯基和有一个绝佳的性质s_{A⊕B}(d) s_A(d) s_B(d)。也就是说在和集上找某个方向的最远点等价于分别在两个原集上找到该方向的最远点然后相加。GJK算法正是利用这一性质通过迭代寻找支撑点来判断两个凸集是否相交即原点是否在闵可夫斯基差内。注意这些优美性质强烈依赖于“凸性”。如果A或B是非凸的A ⊕ B可能非常复杂计算难度急剧上升。因此在实际应用中我们通常要么处理凸形状要么先将非凸形状分解为多个凸部分的并集凸分解再分别计算闵可夫斯基和。3. 计算凸多边形闵可夫斯基和的“和排序”算法理论很美但我们需要能把它算出来。对于两个凸多边形最常用且直观的算法是“和排序”Minkowski Sum via Convex Hull of Sums。不过直接求出所有顶点对的和O(n*m)个点再求凸包效率是O(nm log(nm))不够优。我们可以利用性质2实现一个O(nm)的线性时间算法。3.1 算法步骤详解假设我们有两个凸多边形A和B它们的顶点序列已经按逆时针顺序排列这是计算几何中的常见约定。我们的目标是计算出凸多边形C A ⊕ B。步骤一准备边向量对于多边形A有n个顶点我们得到n条边向量。设A的顶点为A[0], A[1], ..., A[n-1]。边向量 eA[i] A[(i1)%n] - A[i]。这些向量已经按逆时针顺序排列。同理对于多边形B有m个顶点得到m条边向量 eB[j] B[(j1)%m] - B[j]。步骤二合并并排序边向量关键点来了根据性质2C的边向量集合就是 {eA[0], eA[1], ..., eA[n-1]} ∪ {eB[0], eB[1], ..., eB[m-1]}。并且这些边向量在C上也是按极角从小到大逆时针排列的。 因此我们可以将两个边向量列表合并并按照它们的极角进行排序。由于原多边形的边向量序列本身是有序的我们可以使用归并排序的思想在O(nm)时间内完成“排序”——实际上是比较两个列表头部的向量的极角取较小的那个。这比通用排序快。如何比较极角可以使用叉积cross product。对于两个向量u和v计算 u × v u.x * v.y - u.y * v.x。如果叉积 0说明u在v的逆时针方向u的极角更小如果都是从x轴正方向开始逆时针转的话。如果叉积 0说明u在v的顺时针方向v的极角更小。如果叉积 0说明两者共线。这时需要根据实际需求决定顺序通常按照向量模长长度来排或者任意但一致的顺序。在凸多边形中共线的相邻边可能被合并。步骤三构造结果多边形我们从某个起始点开始依次应用排序好的边向量就能得到结果多边形C的顶点。选择起始点起始点可以是 A[0] B[0]即两个多边形各自“起始”顶点的和。但为了确保得到的是完整的凸包一个更稳健的方法是选择在某个方向上比如最下方最左侧的点即求凸包时常用的参考点的支撑点之和。简单实现中用A[0]B[0]在大多数情况下可行尤其是当A和B的顶点序列都是从最小极角点开始时。生成顶点设当前点为 P start_point。遍历排序后的边向量列表中的每一个向量 v将P加入结果顶点列表。更新 P P v。即沿着当前边向量走到下一个顶点。遍历完所有边向量后我们会回到起点形成一个闭合的多边形。3.2 一个手算示例与代码思路假设A是一个正方形顶点为(0,0), (1,0), (1,1), (0,1)。B是一个三角形顶点为(0,0), (0.5, 1), (1, 0)。这里为了简化B也是一个凸形且包含原点。A的边向量逆时针 eA0 (1,0) - (0,0) (1,0) eA1 (1,1) - (1,0) (0,1) eA2 (0,1) - (1,1) (-1,0) eA3 (0,0) - (0,1) (0,-1)B的边向量逆时针 eB0 (0.5,1) - (0,0) (0.5, 1) eB1 (1,0) - (0.5,1) (0.5, -1) eB2 (0,0) - (1,0) (-1, 0)合并并按极角排序边向量 我们需要比较每个向量的方向。可以用atan2(y, x)计算极角但用叉积比较更高效稳定。这里为了演示我们直接观察 (0.5, 1) 角度约63度 (1, 0) 角度0度 (0,1) 角度90度 (0.5, -1) 角度 -63度 (-1,0) 角度180度 (0,-1) 角度 -90度按逆时针顺序角度从小到大(0.5, -1) - (-1,0) - (0,-1) - (1,0) - (0.5,1) - (0,1) 注意(0.5,-1)和(0,-1)角度为负但按逆时针转-90度270度实际上在180度之后。所以更准确的排序需要处理角度周期。使用叉积可以无痛解决这个问题。假设我们从(1,0)开始归并最终排序后的向量序列可能是(1,0), (0.5,1), (0,1), (0.5,-1), (-1,0), (0,-1)。具体顺序取决于起点和比较细节但最终形成的图形是一样的。选择起点A[0] B[0] (0,0) (0,0) (0,0)。构造顶点 P0 (0,0) P1 P0 (1,0) (1,0) P2 P1 (0.5,1) (1.5, 1) P3 P2 (0,1) (1.5, 2) P4 P3 (0.5,-1) (2.0, 1) P5 P4 (-1,0) (1.0, 1) P6 P5 (0,-1) (1.0, 0) // 回到了起点(0,0)吗没有这里出现了问题。问题出在哪里我们得到了一个不闭合的序列。这是因为我们忽略了两个关键点起始点的选择A[0]B[0]不一定在结果凸包的顶点上。在上述例子中(0,0)这个点可能位于结果凸包的内部。边向量的完整性我们合并的边向量必须完整遍历360度确保总和为零向量才能回到起点。正确的做法算法实现 实际上在步骤二中我们合并的是“循环”的边向量列表。我们需要模拟两个多边形同时遍历的过程。更标准的算法描述如下找到A和B中y坐标最小的点如果y相同取x最小作为各自的“起始顶点”索引i和j。这保证了我们从一个“最低点”开始构造类似于求凸包。初始化当前点 P A[i] B[j]。将P加入结果列表。使用两个指针i和j分别指向A和B当前使用的边向量。循环直到我们遍历完A的所有边和B的所有边即总共走了nm步 a. 计算当前A的边向量 eA A[(i1)%n] - A[i]。 b. 计算当前B的边向量 eB B[(j1)%m] - B[j]。 c.用叉积比较 eA 和 eB 的极角 - 如果 cross(eA, eB) 0选择 eA并令 i (i1)%n。 - 否则选择 eB并令 j (j1)%m。 这里“0”的选择决定了当共线时优先用哪个多边形的边只要一致即可。 d. 更新 P P 被选中的边向量。 e. 将新的P加入结果列表。结果列表中的点就是闵可夫斯基和的凸包顶点但可能包含共线点可以在最后做一次凸包简化去除。对于上面的正方形和三角形这个算法会生成正确的六边形顶点序列。代码框架Python风格import math def minkowski_sum_convex(P, Q): 计算两个凸多边形P和Q的闵可夫斯基和顶点均为逆时针顺序。 # 辅助函数找最小y然后最小x的点索引 def bottom_index(poly): min_idx 0 for i in range(1, len(poly)): if poly[i][1] poly[min_idx][1] or (poly[i][1] poly[min_idx][1] and poly[i][0] poly[min_idx][0]): min_idx i return min_idx n, m len(P), len(Q) i bottom_index(P) j bottom_index(Q) result [] # 起始点 cur_point (P[i][0] Q[j][0], P[i][1] Q[j][1]) result.append(cur_point) # 遍历所有边 for _ in range(n m): # 当前边向量 eP (P[(i1)%n][0] - P[i][0], P[(i1)%n][1] - P[i][1]) eQ (Q[(j1)%m][0] - Q[j][0], Q[(j1)%m][1] - Q[j][1]) # 用叉积比较极角 cross eP[0] * eQ[1] - eP[1] * eQ[0] if cross 0: # 选择P的边 next_point (cur_point[0] eP[0], cur_point[1] eP[1]) i (i 1) % n else: # 选择Q的边 next_point (cur_point[0] eQ[0], cur_point[1] eQ[1]) j (j 1) % m # 如果下一个点和上一个点相同可能发生在共线且零向量可以跳过 if next_point ! cur_point: result.append(next_point) cur_point next_point # 结果可能首尾相同去掉最后一个点如果和第一个点相同 if result and result[-1] result[0]: result.pop() # 可选去除结果中的共线点三点共线去掉中间点 return remove_collinear(result) # 需要实现remove_collinear函数4. 闵可夫斯基差与碰撞检测的深度关联这是闵可夫斯基和最具实用价值的领域之一。我们之前提到碰撞检测问题可以转化为原点包含性问题。这里我们深入细节。4.1 从和到差闵可夫斯基差Minkowski Difference通常定义为 A ⊖ B { a - b | a ∈ A, b ∈ B }。注意这等价于 A ⊕ (-B)其中-B是B关于原点的对称图形每个点坐标取反。核心定理两个凸集A和B相交有公共点当且仅当原点 (0, 0) 属于它们的闵可夫斯基差 A ⊖ B。直观理解如果A和B相交存在点 a ∈ A, b ∈ B使得 a b。那么 a - b 0即原点在A ⊖ B中。反之如果原点在A ⊖ B中则存在 a ∈ A, b ∈ B使得 a - b 0即 a b所以A和B相交。这个定理的伟大之处在于它将两个任意形状的凸集是否相交的判定转化为了一个点是否在一个凸集内的判定。而判断点是否在凸多边形内有非常高效的算法如射线法、环绕法。4.2 GJK算法不求完整形状只问是否包含然而在诸如物理引擎这样的实时应用中我们通常并不需要显式地计算出整个闵可夫斯基差A ⊖ B的完整几何形状这仍然是O(nm)的代价。我们只关心一个问题原点在不在里面GJK算法Gilbert–Johnson–Keerthi正是利用闵可夫斯基差和支撑函数的性质通过一种迭代的方式高效回答这个问题。它的核心思想是我们并不构造完整的A ⊖ B而是在迭代过程中在A ⊖ B内部构造一个不断逼近原点的单纯形Simplex即点、线段、三角形或四面体取决于维度。在每一步迭代中我们需要知道在当前搜索方向d上A ⊖ B的极值点即支撑点。根据支撑函数的性质s_{A⊖B}(d) s_A(d) - s_B(-d)。因此我们可以在O(n)和O(m)时间内分别求出A在方向d上的最远点和B在方向-d上的最远点对于凸多边形可以通过点积最大来查找然后相减得到A ⊖ B的支撑点。算法检查当前单纯形是否包含原点或者找到一个新的搜索方向使得下一次迭代能构造一个更接近原点的单纯形。如果某次迭代发现单纯形包含了原点则判定为碰撞。如果单纯形无法再向原点靠近并且不包含原点则判定为分离。GJK算法的美妙之处在于它通常只需要很少的迭代次数3-10次就能得出结论并且支撑点的计算可以优化如使用爬山法或利用上一帧的缓存信息使得它在动态碰撞检测中速度极快。它成为了现代物理引擎如Bullet, Box2D中处理凸形状碰撞检测的标配算法。一个极简的GJK思想演示 假设我们想判断线段一维凸集A和B是否相交。A[1, 3] B[5, 7]。A⊖B [1-7, 3-5] [-6, -2]。这个区间不包含原点0所以不相交。GJK不会去算整个区间[-6,-2]它会初始方向任意比如d1。支撑点s_A(1)3, s_B(-1)5因为方向-d-1B在-1方向最远点是5。支撑点 3 - 5 -2。单纯形现在是点(-2)。它不包含原点且方向从(-2)指向原点(0)是d2。新支撑点s_A(2)3, s_B(-2)5。支撑点3-5-2。和上一点相同。无法再找到更靠近原点的新点迭代终止判定为不相交。虽然这个例子简单但它体现了GJK“迭代构建单纯形逼近原点”的精髓。在二维和三维中单纯形可以是线段、三角形、四面体逻辑类似但几何判断更复杂。4.3 分离轴定理SAT与闵可夫斯基和的关系另一个常用的碰撞检测算法是分离轴定理Separating Axis Theorem。它指出两个凸集不相交当且仅当存在一条直线在2D或一个平面在3D能将它们分开并且该直线/平面的法线方向即“分离轴”垂直于它们投影不重叠的区间。SAT和闵可夫斯基和/差有着内在联系。判断两个凸集在某个轴上的投影区间是否重叠本质上是在判断它们在该轴方向上的“宽度”之和是否小于它们中心之间的距离。而一个凸集在某个方向上的宽度与其支撑函数有关。更进一步两个凸集投影区间不重叠的条件可以转化为原点不在它们闵可夫斯基差在该轴方向上的投影区间内。因此SAT可以看作是在一系列特定的方向通常是边的法线方向上对“原点是否在闵可夫斯基差内”这一条件进行采样检查。如果所有候选轴上都找不到分离轴则原点必然在闵可夫斯基差内即物体相交。所以GJK和SAT是解决同一类问题的两种不同思路GJK是迭代搜索试图在闵可夫斯基差内部找到包含原点的单纯形SAT是枚举检验试图在有限个方向上证明原点不在闵可夫斯基差内。两者结合使用也很常见例如先用快速的SAT进行粗略排除再用GJK进行精确判断并计算穿透深度通过EPA算法。5. 非凸形状的处理与工程实践中的挑战现实世界中的物体很少是完美的凸多边形。一辆汽车、一个角色模型大多是非凸的。直接对非凸形状计算闵可夫斯基和结果会异常复杂且失去凸性带来的优良性质。5.1 凸分解Convex Decomposition标准的解决方案是凸分解。将复杂的非凸多边形或网格分割成若干个凸部分的并集。有许多算法可以做到这一点例如耳切法Ear Clipping适用于简单多边形递归剪掉“耳朵”凸顶点来生成三角形最简单的凸形集合。Hertel-Mehlhorn算法在三角化的基础上尽可能合并相邻的三角形以形成更大的凸多边形减少凸块的数量。基于BSP树或Voronoi图的分解适用于更复杂的形状。分解后对于需要做碰撞检测的两个非凸物体A和B我们分别有凸部分集合{A1, A2, ...}和{B1, B2, ...}。那么A和B的碰撞检测就转化为判断是否存在一对凸部分Ai和Bj发生碰撞。即 Collision(A, B) ∃ i, j such that Collision(Ai, Bj) is True. 而每一对凸部分Ai和Bj的碰撞就可以用我们前面讨论的GJK算法来高效判断。5.2 计算膨胀Offset与运动规划在机器人运动规划中闵可夫斯基和被用来计算配置空间障碍物C-space obstacle。如前所述将机器人R“收缩”为点同时将障碍物O“膨胀”为O ⊕ (-R)。这里-R是R关于原点的对称如果R不是原点对称的膨胀后的障碍物形状就是O和-R的闵可夫斯基和。工程实现细节机器人原点需要谨慎选择机器人的参考点局部坐标系原点。通常选择机器人的几何中心或运动中心。膨胀操作是围绕这个点进行的。旋转的机器人如果机器人可以旋转那么问题就变成了在三维配置空间(x, y, θ)中的规划。对于每个离散的朝向θ都需要计算一次O ⊕ (-R(θ))其中R(θ)是机器人旋转θ角度后的形状。这会导致计算量增大通常需要使用一些近似或分层规划策略。栅格化与距离场在基于栅格Grid的规划中我们不一定需要显式计算出膨胀后的多边形边界。我们可以预先计算一个距离场Distance Field或膨胀距离图。对于地图中的每个栅格计算它到最近障碍物的距离。如果这个距离小于机器人的外接圆半径或更精确的沿该方向到机器人边界的距离则该栅格被视为在膨胀障碍物内。这种方法在实现上更简单且易于处理任意形状。5.3 数值稳定性与退化情况在实际编程中处理几何计算必须格外小心数值误差。共线边处理在“和排序”算法中当两个边向量共线时叉积为0选择哪一个先走必须制定一致的规则比如优先用第一个多边形的边或者比较向量长度。如果处理不当可能会导致生成的顶点序列中出现零长度的边或者顶点顺序错乱。浮点数精度点积、叉积、角度比较都会受到浮点数精度影响。判断“等于零”时应使用一个很小的容差值epsilon例如abs(cross) 1e-9。退化多边形输入的多边形可能不是严格凸的比如有连续三个顶点共线或者有重复顶点。在计算闵可夫斯基和之前最好先对输入多边形进行一次凸包计算和去退化处理确保输入是“干净”的凸多边形。GJK算法的终止条件GJK迭代可能因为数值误差而无法收敛或者在原点非常接近边界时出现振荡。需要设置最大迭代次数以及对“接近原点”的容差判断。一个实用的建议在实现这些算法时务必编写大量的单元测试。测试用例应包括简单的标准形状矩形、三角形。共线边、退化三角形。完全分离、刚好相切、部分重叠、完全包含的物体。随机生成的大量凸多边形对与暴力算法如SAT或直接点检测的结果进行对比。只有通过严格的测试才能保证算法在复杂多变的实际环境中稳定工作。闵可夫斯基和从一个抽象的数学概念通过凸性、支撑函数、迭代算法这些桥梁最终落地为游戏里真实的碰撞、机器人流畅的移动路径。理解其背后的几何原理能让你在遇到相关问题时不仅知道如何调用库函数更能清晰地洞察问题的本质并能在必要时自己动手实现或定制优化方案。这大概就是理论学习对于工程实践最大的价值所在。