近日恰好和同学谈到多边形之间怎么判断相交关系，便写下这篇博文。
由于非凸多边形的不确定性，这里就只谈论凸多边形间位置关系判断的优化。对于分别有 \(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;
}