关于凸包位置关系的判断

近日恰好和同学谈到多边形之间怎么判断相交关系，便写下这篇博文。

由于非凸多边形的不确定性，这里就只谈论凸多边形间位置关系判断的优化。对于分别有 \(n\) 和 \(m\) 条边的非凸多边形可以枚举两个多边形的边判断线段是否相交，时间复杂度为 \(O(mn)\)。

凸多边形（以下简称凸包）也可以通过枚举边判断相交关系来判断两凸包是否相交，但 \(O(mn)\) 的复杂度有时属实过大。下面对如何优化进行讨论。

对于上图两个凸包，我们将凸包B绕着凸包A移动，并绘制出凸包B最左下角点的轨迹：

不难发现，最后凸包B最左下角点的轨迹为两凸包边重新拼接后形成的大凸包，即闵可夫斯基和。对于为什么绘制两凸包的闵可夫斯基和，可以从图中看出，当凸包B最左下角点位于该大凸包内时，两个凸包相交。这里判断点在凸包内则可以用Pick定理解决，最终复杂度为 \(O((m + n)\log(m + n) + (m + n))\)（包括求闵可夫斯基和对边进行极角排序和Pick定理判断单点是否在凸包内），即 \(O((m + n)\log(m + n))\)。

#include<bits/stdc++.h>
#define pii pair<int, int>
#define double long double
#define eps 1e-9

using namespace std;

//使用结构体表示向量方便进行极角排序
struct vec
{
	pii v;
	double ang;

	vec(pii v)
	{
		this->v = v;
		ang = atan2(v.second, v.first);
	}

	bool operator < (vec& r)
	{
		return this->ang < r.ang;
	}
};

pii operator + (pii& l, pii& r)
{
	return make_pair(l.first + r.first, l.second + r.second);
}

pii operator - (pii& l, pii& r)
{
	return make_pair(l.first - r.first, l.second - r.second);
}

bool cmp(vec l, vec r)
{
	return l.ang < r.ang;
}

//向量叉乘
double cross(pii l, pii r)
{
	return l.first * r.second - l.second * r.first;
}

int posOfCh(vector<pii> pochA, int size1, vector<pii> pochB, int size2) //pochA, pochB分别按顺时针顺序存储两凸包上的点
{
	vector<vec> vecs;
	pii maxp = pochA[0], minp = pochB[0];
	for (int i = 0; i < size1; i++)
	{
		vecs.push_back(vec(pochA[(i + 1) % size1] - pochA[i])); //将凸包的边按向量的形式存入，凸包A按顺时针，凸包B按逆时针
		maxp = max(maxp, pochA[i]); //同时查找凸包A中的最右上角点
	}
	for (int i = size2; i > 0; i--)
	{
		vecs.push_back(vec(pochB[i - 1] - pochB[i % size2]));
		minp = min(minp, pochB[i - 1]); //同时查找凸包B中的最左下角点
	}
	sort(vecs.begin(), vecs.end()); //极角排序
	
	//找到从极角-π/2开始（包括-π/2）顺时针方向第一条向量
	int pos = upper_bound(vecs.begin(), vecs.end(), vec({ 0, -1 }), cmp) - vecs.begin() - 1;
	
	//计算闵可夫斯基和的凸包顶点
	vector<pii> pomsch;
	pomsch.push_back(maxp);
	for (int i = pos, j = 0; j < vecs.size(); i = (i + vecs.size() - 1) % vecs.size(), j++)
	{
		pii p = pomsch.back() + vecs[i].v;
		while (pomsch.size() > 1 && cross(vecs[i].v, pomsch.back() - pomsch[pomsch.size() - 2]) < eps) //去除三点共线的中间点
			pomsch.pop_back();

		pomsch.push_back(p);
	}
	pomsch.pop_back();

	//Pick定理判断凸包B最左下角点是否在闵可夫斯基和中
	int flag = 1;
	for (int i = 0; i < pomsch.size(); i++)
		if (cross(minp - pomsch[i], pomsch[(i + 1) % pomsch.size()] - pomsch[i]) < eps)
		{
			flag = 0;
			break;
		}

	return flag;
}