计算几何初步

wjyyy · 2018-12-20 19:41:45 · 个人记录

我的计算几何做题记录 可供参考

引言

计算几何对于很多刚接触OI的同学们是不会涉及的，当逐步进入省选范畴之后，计算几何的应用就非常广了。

你需要知道？

在学习计算几何（至少是这篇文章）之前，你需要了解以下这些东西：

• 平面直角坐标系
• 向量及其运算

平面直角坐标系

平面直角坐标系就是笛卡尔坐标系，这一部分会在人教版七年级数学中系统地学习。

在这篇文章中，我们会经常用到坐标表示，包括下面的向量。同时，我们的点和向量都是通过坐标来保存的。

向量及其运算

向量

向量是既有大小又有方向的量，可以用一个带有箭头的线段表示。

如果一个向量的起点是点A，终点是点B，那么这个向量可以被表示为\overrightarrow{AB}，或者用一个小写英文字母表示为\vec{a}或\mathbf{a}（教科书上加粗时也是斜体）。

向量具有平移不变性，对于任意一个向量，都可以把它的起点平移到原点。因此我们可以在坐标系中用一对有序实数对来表示向量，也就是这个向量起点为原点时终点的坐标(x,y)。

向量的模

模就是模长，向量的模就是向量的长度。表示为|\vec{a}|，对于\vec{a}=(x,y),|\vec{a}|=\sqrt{x^2+y^2}。

相反向量

如果两个向量大小相等，方向相反，那么这两个向量互为相反向量，\vec{a}的相反向量表示为-\vec{a}，|\vec{a}|=-\vec{a}。对于\vec{a}=(x,y),-\vec{a}=(-x,-y)。

垂直向量

如果两个向量所在的直线互相垂直，那么这两个向量互称垂直向量，表示为\vec{a}\bot\vec{b}。

共线向量

如果两个向量所在的直线互相平行，那么这两个向量互为共线向量，表示为\vec{a}\|\vec{b}。因为两向量平行，所以平移其中一个向量，总能和另一个向量共线。

向量的加减

前面提到了向量具有平移不变性，那么\vec{a}+\vec{b}就相当于把向量\vec{a},\vec{b}首尾相接（假设\vec{a}的首接在\vec{b}的尾），此时\vec{a}的尾指向\vec{b}的首就是相加后的向量。对于\vec{a}=(x_1,y_1),\vec{b}=(x_2,y_2)，\vec{a}+\vec{b}=(x_1+x_2,y_1+y_2)。

向量的减法实际上是一个向量加上另一个向量的相反向量，也就是\vec{a}-\vec{b}=\vec{a}+(-\vec{b})，可以先把\vec{b}向量变成-\vec{b}，然后再进行加法计算。\vec{a}-\vec{b}=(x_1-x_2,y_1-y_2)。

向量的加减法具有交换律。

零向量

零向量的模长为0，方向任意，它与任何一个向量都共线，但在高中数学中不认为它与任何一个向量都垂直。坐标为(0,0)。

向量的数乘

向量的数乘实际上是对向量进行放缩。数乘的形式是\lambda\vec{a}，其中常数\lambda\in\mathbb{R}是对向量放缩的程度，可正可负可为零。数乘不改变向量的方向，因此\vec{a}\|\lambda\vec{a}。对于\vec{a}=(x,y),\lambda\vec{a}=(\lambda x,\lambda y)。

向量的数量积

向量的数量积，也叫点积、内积，几何意义为一个向量在另一个向量上的投影再乘上第二个向量的模长。\vec{a}与\vec{b}的数量积表示为\vec{a}\cdot\vec{b}，是一个实数。计算式为\vec{a}\cdot\vec{b}=|\vec{a}||\vec{b}|\cos\theta(\theta=<\vec{a},\vec{b}>)（\theta表示\vec{a},\vec{b}的夹角）。引入坐标后，通过三角恒等变换的推导，对于\vec{a}=(x_1,y_1),\vec{b}=(x_2,y_2)，\vec{a}\cdot\vec{b}=x_1x_2+y_1y_2。

• 如果两个向量同向（共线），那么它们的数量积为他们的模长之积。
• 如果两个向量夹角<90^\circ，那么它们的数量积为正。
• 如果两个向量夹角=90^\circ，那么他们的数量积为0，因为\cos 90^\circ=0。
• 如果两个向量夹角>90^\circ，那么它们的数量积为负。
• 如果两个向量反向（共线），那么它们的数量积为他们的模长之积的相反数。

由向量的数量积可以判断它们的夹角和投影。向量的数量积具有交换律。

向量的外积

向量的外积，也叫叉积，几何意义是两向量由平行四边形法则围成的面积。外积是一个向量，垂直于原来两个向量所在的平面。对于\vec{a}=(x_1,y_1),\vec{b}=(x_2,y_2)，\vec{a}\times\vec{b}的方向就要用右手从\vec{a}沿着不大于平角的方向旋转，大拇指的方向就是外积的方向。如果外积方向朝外，那么值为正，否则值为负。计算式为\vec{a}\times\vec{b}=|\vec{a}||\vec{b}|\sin\theta=x_1y_2-x_2y_1。因为有谁转向谁的区别，所以外积没有交换律。

• 如果\vec{a}\|\vec{b}，那么由\sin 0^\circ=\sin 180^\circ=0,\vec{a}\times\vec{b}=\vec{0}，得到的数字结果也是0。
• 如果\vec{b}的终点在\vec{a}的左侧（假设已经共起点），那么\vec{a}\times \vec{b}>0，\vec{a}握向\vec{b}转过的角逆时针不超过180^\circ，结果为正。
• 如果\vec{b}的终点在\vec{a}的右侧，那么\vec{a}\times \vec{b}<0，\vec{a}握向\vec{b}转过的角逆时针超过了180^\circ，或者说顺时针不超过180^\circ，大拇指朝内，结果为负。

由向量外积可以判断两向量的旋转关系，同时可以方便地求出点到直线的距离。分别会用于下面的凸包和旋转卡壳。

一般情况下我们储存点就会把它放在向量中，用向量\overrightarrow{OA}来表示A这个点。因此下文的A\times B就表示向量\overrightarrow{OA}与向量\overrightarrow{OB}的叉积。

三角剖分求面积

三角剖分可以用来求任意多边形的面积。

我们只需要知道一个多边形的各个连续顶点分别在哪里即可。

上面提到了向量的叉积是表示的是有向面积，方向用正负表示，此时正负就派上用场了。

我们如果把相邻每两个顶点与原点构成的向量的叉积的数值的一半依次累加起来，就能得到多边形的面积。如下图：红色面积表示负的，蓝色面积表示正的。

首先计算\overrightarrow{OA}\times \overrightarrow{OB}，得到负的面积-S_{\triangle OAB}，在图上表示为红色部分；然后计算S_{\triangle OBC}，此时在图上表示为抵消-S_{\triangle OBP}，并额外加上正的S_{\triangle PBC}。

然后依次进行下去

可以看出，多边形外部出现过的红色总会被消掉，因为多边形是闭合的。当出现了一条相对原点向右的边时，则之后必然会出现一条相对原点向左的边来封闭这个多边形。

如果原点在多边形内部就更好理解了。多边形凹的部分会被”拐回来的部分“给减掉，剩下的部分都可以直接相加。

最终对于n多边形A_1A_2\dots A_n，面积计算公式就是S=x_ny_1-y_nx_1+\sum_{i=1}^{n-1}(x_iy_{i+1}-y_ix_{i+1})。

当用向量存点时，计算可以用相邻向量叉积之和，S=A_n\times A_1+\sum_{i=1}^{n-1}A_i\times A_{i+1}。

凸包

定义

凸包就是求一个周长最小的，并且能包围所有给定点的多边形。当多边形表面存在凹陷时，根据三角不等式\left\{\begin{matrix}a+b>c\\ b+c>a\\ a+c>b\end{matrix}\right.，一定没有直接把最短那条边连起来优。

性质

如果按逆时针方向看，凸包上每两条相邻的边都是向左拐的。比如说，与边\vec{a}_i顺时针方向相邻的是边\vec{a}_{i+1}，那么对于任意i\in[1,n)（n为凸包上点的个数）有\vec{a}_i\times \vec{a}_{i+1}>0,\vec{a}_n\times \vec{a}_1>0。因为用右手从\vec{a}_i的方向顺小于平角的一边握向\vec{a}_{i+1}，大拇指总会指向外边。

求法

首先把所有点以横坐标为第一关键字，纵坐标为第二关键字排序。

显然排序后最小的元素和最大的元素一定在凸包上。而且因为是凸多边形，我们如果从一个点出发逆时针走，轨迹总是 “左拐” 的，一旦出现右拐，就说明这一段不在凸包上。因此我们可以用一个单调栈来维护上下凸壳。

因为从左向右看，上下凸壳所旋转的方向不同，为了让单调栈起作用，我们首先升序枚举求出下凸壳，然后降序求出上凸壳。

求凸壳时，一旦发现即将进栈的点（P）和栈顶的两个点（S_1,S_2，其中 S_1 为栈顶 ）行进的方向向右旋转，即叉积小于 0：\overrightarrow{S_2S_1}\times \overrightarrow{S_1P}<0，则弹出栈顶，回到上一步，继续检测，直到 \overrightarrow{S_2S_1}\times \overrightarrow{S_1P}\ge 0 或者栈内仅剩一个元素为止。

通常情况下不需要保留位于凸包边上的点，因此上面一段中 \overrightarrow{S_2S_1}\times \overrightarrow{S_1P}<0 这个条件中的 “<” 可以视情况改为 \le，同时后面一个条件应改为>。

最后不要忘了把最小的元素与栈顶进行比较，以保证最后一段也是凸壳。

代码

std::sort(p+1,p+1+n);
stk[++tp]=1;
for(int i=2;i<=n;++i)
{
    while(tp>1&&(p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp]])<=0)
        used[stk[tp--]]=0;
    used[i]=1;
    stk[++tp]=i;
}
int qaq=tp;
for(int i=n-1;i>0;--i)
    if(!used[i])
    {
        while(tp>qaq&&(p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp]])<=0)
            used[stk[tp--]]=0;
        used[i]=1;
        stk[++tp]=i;
    }
for(int i=1;i<=tp;++i)
    h[i]=p[stk[i]];

最后h数组中存的就是凸包了。（下标1和tp存的是同一个点）

练习

UVA 11626 Convex Hull

洛谷 P2742 圈奶牛

洛谷P3829 [SHOI2012] 信用卡凸包

旋转卡壳

跟我一起读

我也不知道该怎么读。这个词一共有2^4=16种读法。

前言

刚学旋转卡壳时，是看到了一句话：“同时旋转两条平行线直到其中一条和多边形的一条边重合”。那不就是旋转到夹角较小的那一条边上去吗？