闵可夫斯基和
(这里的闵可夫斯基和只针对凸多边形)
定义
- 两个欧几里得空间里点集的和，又称作两个空间的膨胀集，即：$A+B=\{a+b|a\in A,b\in B\}$
- 其实可以把$B$看作一个向量集，把$A$每个点沿着$B$中每一个向量进行一波平移。
（图中粉色边框即为$A$和$B$的闵可夫斯基和）
性质
- 满足加法交换律：$A+B=B+A$
- 两个凸包的闵可夫斯基和由两个凸包的边构成。
过菜不会证明
求法
- 根据性质二，只需要把边集取出来直接极角排序
- 之后分别找到边界点绕着跑一圈即可定位
例题
-
- 题意：将一个点集根据一个向量进行平移，判断是否会与另一个点集冲突，当两者的凸包出现重叠时发生冲突
- 题解：直接将待平移的点集取反，然后求两个点集的闵可夫斯基和，判断平移的向量坐标是否位于期中即可
-
- 题意：矩形房间，一个扫地机器人和一些家具，均为凸多边形，求机器人能扫到的面积
- 题解：和上一道思路差不多，求出来闵可夫斯基和之后直接扫描线