凸多边形 Minkowski 和的边归并

形式陈述

固定一个坐标原点，将平面位置表示成 $\mathbb R^2$ 中的向量。两个集合 $P,Q\subseteq\mathbb R^2$ 的 Minkowski 和定义为

P\oplus Q=\{p+q:p\in P,\ q\in Q\}.

若两者都是凸集，其和也凸：两个和点的凸组合可以分别在 $P,Q$ 中取凸组合，再相加。对两个按逆时针极点序列给出的凸多边形，怎样不用枚举所有点对就求出这个集合的边界？

把各轮廓旋转编号，使最低点排在首位，同高时选最左点。其边向量沿极角有序。维护两个指针 $i,j$ ，输出当前和点 $p_i+q_j$ ；比较下一条边向量 $e_i=p_{i+1}-p_i$ 与 $f_j=q_{j+1}-q_j$ 的方向：

每条边恰好消费一次。最终回到起始和点，只保留一份闭环顶点，合并连续共线边。对 $m,n$ 条输入边，算法时间为 $O(m+n)$ ，输出至多 $m+n$ 条边。

直觉

给定方向 $u$ ，支撑函数为 $h_P(u)=\max_{p\in P}\langle u,p\rangle$ 。逐点和满足

h_{P\oplus Q}(u)=h_P(u)+h_Q(u),

因为 $p,q$ 可以独立选取。于是和多边形在某个方向的支撑点，就是两个输入在该方向的支撑点之和。方向连续旋转时，只有当其中一个输入跨过一条边的法向，和的支撑点才改变。

两份边方向已经有序，因此这一步与归并两个有序序列相同。不是把所有顶点加一遍再凭感觉连线，而是按支撑方向的变化次序确定输出的整条边界。同向边要同时前进，否则会输出一个多余的共线中间点。

例子与边界

设 $B$ 是机器人相对参考点的轮廓，把参考点放在位置 $x$ 后，机器人占据 $x+B$ 。障碍为 $O$ 。两者相交当且仅当存在 $b\in B,o\in O$ 使

x+b=o, \qquad\text{即}\qquad x=o-b.

所以碰撞参考点集合为

O\oplus(-B),\qquad -B=\{-b:b\in B\}.

反射来自这个等式，而不是一种绘图习惯。机器人若关于参考点中心对称，反射恰好看不出区别；非对称轮廓会暴露错误。

取矩形障碍

O=[4,7]\times[2,4]

与三角机器人

B=\operatorname{conv}\{(0,0),(2,0),(0,1)\}.

反射三角形的顶点为 $(0,0),(-2,0),(0,-1)$ 。方向归并输出的五边形为

(2,2),(4,1),(7,1),(7,4),(2,4).

这里是五边形，因为矩形与三角形有同向边，归并时同时消费。逐点穷举十二个顶点和再取凸包，得到完全相同的极点，构成独立核对。

把参考点放在 $x=(3,2)$ ，机器人顶点 $(2,0)$ 被平移到 $(5,2)$ ，已经碰到障碍下边。因此 $x$ 必须被禁区包含，确实位于上面五边形中。错误使用 $O\oplus B$ 会使最左横坐标仍为 $4$ ，把这一碰撞位置漏掉。

上述碰撞使用闭集合相交，连单点接触也禁止。若规划模型允许擦边，应在构造后的自由空间中采用一致的边界约定；安全余量则可再加一个半径为 $r$ 的圆盘。圆盘 offset 会出现圆弧，不再是原算法的有限直线边输入。

两个非凸多边形的和可能非凸，也可能有孔。把其边方向排序后直接归并会丢掉凹部信息。可先分解为凸块，分别计算块对的和，再做几何并；块对数量与并集构造成本都要计入，不能继续宣称 $O(m+n)$ 。

允许机器人旋转时， $B$ 随姿态改变。此页只为固定姿态、仅平移的二维机器人构造禁区；把所有角度的轮廓混在一张平面图里，不能表达姿态转换的可行性。

推论与应用

边归并每轮至少推进一个指针，故最多 $m+n$ 轮。方向比较使用半平面编号和叉积；两份完整方向序列的比较不能只凭叉积符号而忽略跨越 $\pi$ 的极角区间。对标准最低点起始的凸轮廓，可以用已知旋转次序组织归并，但实现仍应显式处理同向、末尾耗尽与零边。

Minkowski 和与凸包不同。凸包允许在一个集合中取凸组合；Minkowski 和允许从两个集合各选一个点相加。有限凸多边形满足

\operatorname{conv}(P_0)\oplus\operatorname{conv}(Q_0) =\operatorname{conv}\{p+q:p\in P_0,q\in Q_0\},

因为展开两份凸组合后，系数乘积非负且和一；反方向由和集凸性得到。这也解释了为什么“枚举全部顶点和后取凸包”是正确但更慢的核验方法。

构造禁区后，可把参考点交给可见图最短路。若膨胀后的障碍互相重叠，需要先合并边界；不能仍把相交障碍当成满足两两不交合约的独立输入。

先按耳切页给出的十边形坐标，从 $s=(1,5)$ 走到 $t=(7,5)$ 。任务是给出合法剖分、单调块、门户序列、漏斗每次改变的链，以及与独立可见图一致的最短长度；再完成本页的非对称三角机器人禁区计算。

一份解答先输出八片三角形

(1,2,3),(1,3,4),(0,1,4),(0,4,5), (9,0,5),(5,6,7),(9,5,7),(7,8,9).

它们面积和为 $38$ ，内部对角线成对出现。单调划分给出对角线 $(5,7)$ 、 $(1,5)$ ；第三面 $(5,7,8,9,0,1)$ 的栈剖分以方向值 $\operatorname{orient}(v_5,v_7,v_9)=4$ 认证一次弹栈。

三角通道依次经过门户 $((4,2),(0,0))$ 、 $((6,2),(0,0))$ 、 $((6,2),(8,0))$ 、 $((6,6),(8,0))$ 。第三门户使 apex 从 $s$ 移到 $(4,2)$ ，目标插入又删去可绕过的 $(6,6)$ ，最终得到

s\to(4,2)\to(6,2)\to t, \qquad 3\sqrt2+2+\sqrt{10}.

验收时同时检查：各段留在房间内，长度与可见图相同，merge 义务没有遗漏，漏斗没有重扫旧门户；机器人部分必须使用 $O\oplus(-B)$ ，并判断 $(3,2)$ 为碰撞位置。仅给一个看似合理的折线或一张正确面积的图，不足以完成任务。

可下载完整题解、Python 标准库复算脚本与实际运行结果。保存脚本后运行 python foundation-geometry-capstone.py，会写出完整状态表，并执行精确几何断言及独立算法交叉核验。

参考资料

CGAL，2D Minkowski Sums User Manual，Introduction、Computing the Minkowski Sum of Two Polygons，以及非凸/含孔输入的分解与卷积边界。
Joseph O’Rourke，Computational Geometry in C，第 2 版，1998，Chapter 8，Code 8.5；作者的代码位置索引。
Mark de Berg 等，Computational Geometry: Algorithms and Applications，第 3 版，2008，Chapter 13，固定姿态平移机器人的配置空间。课程原书