「学习笔记」计算几何相关

走上计算几何的漫漫不归路（雾）。

基本概念

点积

$a\cdot b=|a||b|cos\theta$

令 $a=(x_1,y_1),b=(x_2,y_2)$ ，则它们的点积等于 $x_1x_2+y_1y_2$ 。

应用：两向量垂直，其点积为 $0$ 。

叉积

$a\times b=|a||b|sin\theta$

令 $a=(x_1,y_1),b=(x_2,y_2)$ ，则它们的点积等于 $x_1y_2-x_2y_1$ 。

应用：叉积的几何意义为两向量 $a,b$ 共起点时所构成平行四边形的面积。叉积 $=0$ ，两向量平行；叉积 $>0$ ，向量 $a$ 在向量 $b$ 的顺时针方向；叉积 $<0$ ，向量 $a$ 在向量 $b$ 的逆时针方向。

旋转向量

将向量 $a=(x,y)$ 旋转 $\theta $ 角度后，坐标为 $(x cos\theta - y sin\theta , x sin\theta + y cos\theta)$ 。

证明：令向量 $a$ 与 $x$ 轴夹角为 $\alpha $ ，则旋转之后夹角为 $\alpha + \theta $ 。利用 $x=|a|cos \alpha$ 与 $y=|a|sin \alpha$ 及和角公式可得证。

多边形的面积

若已知一个简单多边形的顶点按逆时针顺序依次为 $P_1,P_2,\cdots P_n$ ，则其面积为：

$S=\frac{P_n\times P_1+\sum _{i=1}^{n-1}P_i\times P_{i+1}}{2}$

极角排序

在平面上取一定点 $O$ ，从 $O$ 引一条水平射线 $Ox$ ，规定方向自左至右，再选定一个长度单位并规定角旋转的正方向，通常取逆时针方向，这样就构成了一个极坐标系。点 $O$ 叫作极点，射线 $Ox$ 叫作极轴。

常见的极角排序方法有四种，这里给出利用叉积进行排序的代码（以原点为极点）。

struct node{double x,y;};
double cross(double x1,double y1,double x2,double y2){return x1*y2-x2*y1;}
bool cmp(node a,node b)
{
	double cros=cross(a.x,a.y,b.x,b.y);
	if(fabs(cros)<eps)return a.x<b.x;
	return cros>0;
}

凸包

Graham扫描法

一个点集的凸包就是能包围给定点的最小的凸多边形。

构造出点集的凸包的方式为：以点集中纵坐标最小的点为极点（纵坐标相同则横坐标最小，易得这个点一定在凸包上），其他点做极角排序，然后按照极角序扫描，加入一个点时利用叉积判断之前的点是否合法即可。

旋转卡壳

对踵点

如果过凸包上的两个点可以画一对平行直线，使凸包上的所有点都夹在两条平行线之间或落在平行线上，那么这两个点叫做一对对踵点。使用旋转卡壳算法可以求出凸多边形的所有对踵点。

算法原理

我们只需要维护两条平行直线中至少有一条卡住了一条边的情况，即可求出所有的对踵点。

枚举凸包上的每一条边，当它被一条直线卡住时，另一条直线一定卡住了离该边最远的点，且该点与该边的两个端点构成了两对对踵点。因为凸包上的点距离固定边的距离是单峰的，改变枚举边时只需要直接移动到对应点即可，且移动过程中经过的点都能与这两条相邻边的交点构成对踵点。时间复杂度 $O(n)$ 。

应用

详见博客《计算几何之旋转卡壳算法》

半平面交

基本概念

半平面是指二维平面上一条直线的一侧的所有空间。通常使用点对 $(P,Q)$ 表示在向量 $PQ$ 左侧的半平面。

多个半平面的交是空集或非空凸集。

构造方法

首先对所有的半平面进行极角排序，对于极角相同的半平面有选择性地保留，并在双端队列中加入最开始的两个半平面。

考虑加入一个新的半平面：当队头的两个半平面的交点在该半平面外，删除队头的半平面；队尾同理；然后将新的半平面加入队尾。

添加完所有的半平面后，删除两端多余的半平面的方法为：若队头的两个半平面的交点在队尾半平面外，删除队头的半平面；队尾同理。

判断交点在半平面外可以利用叉积解决。

参考资料

《计算几何选讲》，dwjshift
极角 - 百度百科
半平面交 - 百度百科

基本概念

点积

叉积

旋转向量

多边形的面积

极角排序

凸包

Graham扫描法

相关应用

旋转卡壳

对踵点

算法原理

应用

半平面交

基本概念

构造方法

参考资料