This is not the end.

0%

Minkowski Sum 闵可夫斯基和

Posted on

定义

这是一种对两个向量集合定义的运算。对于两个集合$A,B\in R^n$，它们的Minkowski Sum定义为：

一个重要的性质

如果我们把凸多边形的顶点看做向量，用$Conv(S)$表示点集$S$内的点的凸包，那么有一个性质：

证明如下：
首先，设$Conv(A)=\{ v_1,v_2\cdots v_n\}$，则任何一个$Conv(A)$内的点可以用它们的凸组合（convex combination）表示，即：

对于一个点集$S=\{ x_1,x_2,\cdots x_n\}$，一个形如$\alpha_1 x_1 + \alpha_2x_2 + \alpha_3 v_3\cdots \alpha_nv_n$且满足$\alpha_1+\alpha_2 +\alpha_3 + \cdots +\alpha_n =1$并且$\forall i\in [1,n],0\le \alpha_i\le 1$的点，称为$S$的一个凸组合。显然一个点集所有的凸组合等于这个点集的凸包内部的点（可以这样去理解：首先，对于只有两个点，它们的凸组合是它们之间的线段上的点；如果再加一个点，三角形内的点可以看做一条边上的一点与和这条边的相对的顶点的凸组合，以此类推）。

设$v=\sum \alpha_i\cdot v_i,w=\sum \beta_i\cdot w_i$，即$v,w$分别是$A,B$的两个凸组合，则

即$v+w$为$A+B$的凸组合。

计算方法

假如现在有两个凸多边形，要计算它们的Minkowski Sum。按照逆时针方向，令两个凸多边形的边为从它的一个端点指向下一个端点的向量（“下一个”是指凸多边形上按照逆时针方向的下一个），然后对所有的这些向量进行极角排序。选择两个凸多边形最靠左的两个顶点，显然这两个顶点相加一定在$Conv(A+B)$上，然后从这两个顶点相加得到的点开始，将排好序的向量依次拿出来接在上一个顶点的后面，最后将得到一个凸多边形，这个凸多边形就是$Conv(A+B)$。

例题

JSOI 2018 部落战争

题意：给两个点集，设这两个点的凸包分别为$A$和$B$，每次询问给一个向量，判断$A$中是否存在一个点，这个点加上这个向量过后得到的点在$B$内。

Solution：要求$a+d=b$，也就是求$d=a-b$。将$B$中所有向量取反，与$A$做Minkowski Sum，判断询问是否在Minkowski Sum中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
template <class T>
inline void read(T &x)
{
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=1e5+10;
const int eps=1e-8;
struct Point{
	ll x,y; double ag;
	Point(ll x=0,ll y=0,double ag=0): x(x),y(y),ag(ag) {};
	friend Point operator +(Point a,Point b){return Point (a.x+b.x,a.y+b.y);}
	friend Point operator -(Point a,Point b){return Point (a.x-b.x,a.y-b.y);}
}st[N];
ll Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}
int dcmp(double x){return fabs(x)<eps?0:(x>0?1:-1);}
double Dis(Point a){return 1.0*a.x*a.x+1.0*a.y*a.y;}
bool cmp(Point a,Point b){return dcmp(a.ag-b.ag)==0?Dis(a)<Dis(b):a.ag<b.ag;}
void get(Point *p,int &n)
{
	for(int i=2;i<=n;i++) if(p[i].x<p[1].x||(p[i].x-p[1].x==0&&p[i].y<p[1].y)) swap(p[1],p[i]);
	for(int i=2;i<=n;i++) p[i]=p[i]-p[1],p[i].ag=atan2(p[i].y,p[i].x);
	sort(p+2,p+n+1,cmp);
	
	int top=0; st[++top]=Point(0,0);
	for(int i=2;i<=n;i++)
	{
		while(top>1&&Cross(st[top]-st[top-1],p[i]-st[top-1])<=0) top--;
		st[++top]=p[i];
	}
	for(int i=1;i<=top;i++) p[i]=st[i]+p[1];
	
	n=top;
	
}
Point p1[N],p2[N],pt[N<<1];
int n,m,tot;
void cal()
{
	int l1=1,l2=1; pt[++tot]=p1[1]+p2[1];
	while(l1<=n||l2<=m)
	{
		if(l1<=n&&Cross(p1[l1%n+1]-p1[l1],p2[l2%m+1]-p2[l2])>0)
			tot++,pt[tot]=pt[tot-1]+(p1[l1%n+1]-p1[l1]),l1++;
		else if(l2<=m) tot++,pt[tot]=pt[tot-1]+(p2[l2%m+1]-p2[l2]),l2++;
		else break;
	}
	get(pt,tot);
}
bool che(Point Q)
{
	if(Cross(Q-pt[1],pt[2]-pt[1])>0||Cross(Q-pt[1],pt[tot]-pt[1])<0) return 0;
	int l=1,r=tot,ans=l;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(Cross(pt[mid]-pt[1],Q-pt[1])>=0) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return Cross(pt[ans%tot+1]-pt[ans],Q-pt[ans])>=0;
}
int main()
{
	int q; read(n),read(m),read(q);
	for(int i=1;i<=n;i++) read(p1[i].x),read(p1[i].y); get(p1,n);
	for(int i=1;i<=m;i++) read(p2[i].x),read(p2[i].y),p2[i]=Point(0,0)-p2[i]; get(p2,m);
	cal();
	while(q--)
	{
		Point Q; read(Q.x),read(Q.y);
		if(che(Q)) puts("1");
		else puts("0");
	}
	return 0;
}

正睿OI 省选模拟 Nagisa

题意：给你三个凸多边形，有$m$次询问，每次给出一个点的坐标，询问以这个点作为重心且三个顶点分别位于三个凸多边形内的三角形是否存在。

题解：可行区域就是三个凸包的Minkowki Sum。

参考资料：

几篇证明：1 2
维基百科：Minkowski Sum