二维计算几何从入门到入门

· · 算法·理论

前言

驻波在某场模拟赛被计算几何创死了，发现一点都不会计算几何。

恶补了一下简单的内容，不知道有没有用。

简介

接触了一些较为基础的计算几何知识。

本文重点讨论于二维平面内的计算几何。

部分题目来源于百练OJ，但是我都替换成 POJ 了。

语言表述可能并不是十分标准严格，见谅。

基本元素

点

一般用 (x,y) 来表示一个二维平面的点。

向量

日常接触的是标量，即只有数值大小的量，而向量则是具有方向和大小的量（注意和位置无关）。

一般可以用二维平面内的一个点表示向量 \overrightarrow{a}，原点到点的距离是向量大小，点相对于原点的方向就是向量的方向。

向量有若干基础运算，对于两个向量 \overrightarrow{a}=(x_a,y_a),\overrightarrow{b}=(x_b,y_b)，有：

在坐标系中，对于 A,B 两点，一般有：\overrightarrow{OA}=\overrightarrow{OB}+\overrightarrow{BA},\overrightarrow{AB}=\overrightarrow{OB}-\overrightarrow{OA}。

向量一般用点来表示。

点乘

基础定义不多阐述，一个特变的地方在于点乘的结果正负和两个向量的夹角有关。

无精度误差：\overrightarrow{a}·\overrightarrow{b}=x_ax_b+y_ay_b。

实际含义为第二个向量在第一个向量的投影长度与第一个向量模长之积。

叉乘

基础定义不多阐述，一个特别的地方在于差乘结果正负和两个向量的相对关系有关。

无精度误差：\overrightarrow{a}\times \overrightarrow{b}=x_ay_b-y_ax_b。

如果为正，说明第二个向量在第一个向量逆时针方向，如果为负，说明在顺时针，为零则贡献。

实际含义为两个向量形成的平行四边形面积，注意是可负的，正负形可以用右手定则判断。

直线

两点确定一条直线。

判断点线关系：用叉积，直线上任选两个点构造共起点向量算叉积即可判断向量位置关系，其实正负号就反应点线关系了。

判断直线关系：在直线 l_1 上取两点 A,B，在直线 l_2 上取两点 C,D。

找交点坐标：如果不共线，则：\overrightarrow{OA}+k_1\overrightarrow{AB}=\overrightarrow{OC}+k_2\overrightarrow{CD}。

两边叉乘 \overrightarrow{CD}，则 \overrightarrow{OA}\times \overrightarrow{CD}+k_1\overrightarrow{AB}\times \overrightarrow{CD}=\overrightarrow{OC}\times \overrightarrow{CD}。注意到只剩下一个变量，解方程即可。

点到直线距离：平行四边形面积为底成高，已知底（两点长）和面积（叉积算），直接求高。

线段

判断点在线段上：一种方法是先判断在直线上，然后在看 x 是否在线段 x 坐标范围内。另一种做法是，对于线段 A,B，C 在 A,B 上，首先要在直线上，然后判断 \overrightarrow{CA},\overrightarrow{CB} 的夹角为 180 度还是 0 度，可以用点积判断。

判断线段相交：好像叫跨立试验，具体的，线段 AB,CD 相交，当且仅当 A,B 在直线 CD 异侧，C,D 在直线 AB 异侧。

多边型

面积：三角剖分，三角形面积是平行四边形一半，用叉积。

点和多边形关系：

特殊的，如果判断在一个凸包内：

题目 1

入门难度的题。

POJ1269

直接判断即可。

POJ2318

注意到线段不想交，可以二分最后一个在点左侧的线段，时间复杂度为 O(n\log n)。

P1335

先特判掉顶点和边上的情况。

如果在三角形内部，按照逆时针或者顺时针方向给三角形的边变成有向的线段，如果这个点相对于三个向量的关系一样，则在三角形内部。

POJ1039

线一定可以经过两个端点，不然可以旋转调整到对应状态。

枚举两个端点，得到穿过的射线，然后直接能穿过几段管道，算交点即可。

基础算法

极角排序

其实就是选择一个点建立极坐标系，然后让其他点按照极角排序。

其实极角排序可以通过角度范围映射到数轴上的范围，解决一些别的题目。

方法一：用 C++ 自带的 atan2 实现。

方法二：同一象限的点用叉积判断关系，不同象限的则比较象限。

题目 2

极角排序的简单题。

P14428

对于两个不重叠的三角形，一定可以通过一条直线将整个坐标系分开成两个平面。

通过旋转，可以让直线严格经过两个端点。所以枚举两个端点，得到一条直线。

计算直线两侧能得到的合法三角形，乘起来即可。

具体是选择一个基准点，然后极角排序，枚举另一个直线端点，双指针维护半个平面里各个颜色点的数量。

复杂度为 O(n^2\log n)。

P1691

可以证明最优解一定经过两个端点。枚举一个基准点。

先极角排序，然后一条线段两个端点对应的极角，得到一个范围，另外一个端点选择的极角在这个范围就会产生一些贡献。

问题变成一些区间，区间有权值，选择一个点权值最大，随便做就行。

复杂度为 O(n^2\log n)。

P3699

枚举一个基准点，然后计算这个基准点能向外连出的线。

一个三角形会让一个极角范围内的点可能被阻挠。把这个三角形拆成两次操作，一次加入一次删除做扫描线。

需要求出某个极角时距离基准点最近的三角形，实际上，两个三角形加入后，因为不相交，他们任意时刻到基准点的距离远近相对关系和刚加入的关系一样，直到某一个被删除。

所以问题变成单点修改全局最大，用 set 或者可删堆即可，复杂度为 O(n^2\log n)。

凸包

给定平面内的 n 个点，求最小的能把所有点覆盖的多边形，就是凸包。

凸包由上凸壳和下凸壳构成，特点是边的斜率递增或递减，在优化 dp 或者数据结构中有用途。

Andrew 算法

求凸壳的算法。

先找到以 x,y 为一二关键字排序后最小点，一定在凸包上。

先构建下凸壳，维护一个栈表示当前凸包边上的点，每加入一个点就判断栈顶三个点是否满足向内收的趋势（具体特征是相邻两点向量的位置关系是否呈逆时针）。用叉积可以快速判断。

然后同理构建上凸壳（这个顺序无所谓），时间复杂度为 O(n\log n)，瓶颈在于排序。

闵可夫斯基和（凸包）

凸包其实可以看成一个点集，对于两个凸包 P,Q，则集合 \{p+q|p\in P,q\in Q\} 就是两者的闵可夫斯基和。

具体求法是先拆凸包的边，然后按照斜率去归并排序，最后就能合并出新的凸包，时间复杂度为 O(n)。

在一些特殊条件下，序列的 (\max,+) 卷积可以用闵可夫斯基和优化到 O(n)。

习题 3

凸包的简单题。

P2742

凸包模板题。

P3829

先求出每个圆的圆心，整个凸包的形状大概就是圆心的凸包的形状。

先忽略圆弧的边，剩下的边通过平移可以发现和原来凸包的周长是一样的。

因为是一个凸多边形，所有圆弧所对圆心角之和为 360 度，半径均一样，所以这部分长度之和就是一个整圆。

直接算就行。

P2116

注意到凹下去的部分一定不优，不如不凹。

所以转化成凸包距离为定值的图形周长，和上面就是一样的。

P4557

若存在 p\in P,q\in Q，满足 p+r=q，则 r=q-p，即 r\in \{q-p|p\in P,q\in Q\}。

把 P 集合集合所有向量取反，然后求出凸包后闵可夫斯基和去合并，问题变成点和多边形的关系。

找出基准点后极角排序然后三角剖分，可以快速查询，复杂度为 O(n\log n)。

POJ1696

每层剥掉最外层的凸包点。从最外层任意选一个点断开，然后往里面螺旋一定有合法解。

旋转卡壳

前面忘了，但是十六种读法。

可以用来解决一些最远点对的题目。在一个凸包上，维护两根平行线，把整个凸包夹住。

当一个平行线和边重合时，另外一个平行线可能会交一个点或者一个边，这个时候用两部分算贡献即可。

习题 4

旋转卡壳简单题目。

P1452

模版题。

维护另外一个平行线交的点时可以用叉积求和当前平行线交的边最大面积的点，因为底一定，只和高有关，而凸包的结构决定高是个单峰函数。

直接双指针即可，复杂度为 O(n\log n)，瓶颈在于排序。

P3187

在上面基础上，同时维护一个最右和最左点即可，判断方法用点积（本质是投影长度乘积）。

先求出一交点，然后顺时针求出另外四个点即可。

注意最左最右的投影长度可能是多峰。复杂度为 O(n\log n)，瓶颈在于排序。

P4357

每次求出最远点对 (a,b) 后，把所有和 a,b 相关的决策都列为可能的决策，然后删掉 a,b。跑 k 次旋转卡壳后，求出所有可能决策的第 k 大。

对于第 k 大的点对，最坏情况下也会被第 k 次旋转卡壳跑出来，而比他大的所有点对也一定在他之前跑出，所以不会漏决策也不会多不合法的决策。

其实这个题可以做到 O(n\log n+nk) 的。旋转卡壳部分，可以提前将所有点排好序，然后直接顺序读入还没有被删掉的点。求答案 nth_element 随便做一下。

POJ3851

减一下，然后得到差向量的集合。

其实是个凸包合并，用闵可夫斯基和做一些就行。

当然也有旋转卡壳做法，需要维护有向线段的最长最短。

半平面交

定义满足 ax+by+c<0 或者 >/\le/\ge 0 的所有点 (x,y) 为一个半平面。

半平面交就是给定若干 ax+by+c<0 的约束，然后求一个点集的交，感觉很像线性规划。

半平面交最终形态在一般情况下会类似一个凸包（当然有很多特判的情况，非常复杂，不过大部分题目会简化掉一些情况）

一个求出半平面交的算法是增量法，让所有半平面按照极角排序，维护一个不完整的凸壳，内部就是当前的半平面的交，然后依次加入新的半平面。

具体的，维护一个双端队列，表示对当前半平面交有约束的半平面。此时要新加入一个半平面。

如果队列维护的凸壳的最后一个点不在当前加入的半平面，弹出队尾元素。

当半平面交形成一个凸包时，凸壳的第一个点也可能不在半平面内，需要弹出队首元素。。

因为队首元素在不断变化，所以最后需要用队首更新队尾多余的部分。

有时，半平面交不一定是封闭的，但是题目会给定边界，可以手动加入边界。

这种算法只能处理大部分的半平面交情况，复杂度为 O(n\log n)。

题目 5

半平面交的板子题。

P4196

真板子，把凸包的边拆成半平面跑即可。

P3256

去重，用单调栈处理掉绝对不可能成为第一的车，剩下的按照初始位置排序。

建模：初始位置当做截距，速度当做斜率，得到一条直线，求出所有直线上半部分的半平面交，则只有存在在最终半平面交上的直线才有可能成为第一。

最终答案一定是下凸壳，可以简化半平面交的很多步骤。

P2600

把下面的多边形拆边，能看到这条边的范围是一条边。

求出半平面交，即为能看到所有边的位置集合。

最小距离一定在顶点所在的 x 坐标处产生，否则可以移动到线段两端，一定更优秀。

P4250

可以感受到合法的站位一定是一个区域。可以求出这个区域比整个多边形的面积。

实际上，枚举 i\ne 0，考虑 (i,i+1),(0,1) 这两个线段之间对合法区域的约束，满足 (0,1,p),(i,i+1,p) 这两个三角形面积相等的点 p 的轨迹是一条直线，则直线一半就是半平面。

求出半平面交即可，可以用三角函数算一下夹角，也能直接用向量推。

P3297

考虑什么时候答案会增加，就是当从一个人的监视区域移动到另一个人的监视区域。

每个人监视区域其实可以通过其他人对他的约束，最终是一个半平面交。

可以发现只可能从两个边相交的半平面之间移动，连边然后 bfs 即可，复杂度为 O(Tn^2\log n)。

POJ3464/P3799

建模后会发现都是要求多边形内是否存在一个点能看到其他店，其实等价于 P2600。

P5328

首先排名为 1 的就是半平面交板子。

考虑排名为 2 的 i，即存在某一个 x，使得只存在一个 j 满足 a_jx+b_j<a_ix+b_i。

具体的，可以先求出来一个半平面交，然后将当前半平面交上这个选手位于第一名的 x 范围求出，并区间打上一个覆盖标记。

然后将上面的点删掉，然后再求半平面，此时第一个点能成为第二必须满足：

  1. 他此时在半平面交上。

  2. 他在平面交上的支配范围内，存在一个 x 使得这个位置只有一个标记。

然后依次类推做就行了。

复杂度大概是 O(nm\log V) 的。

后记

其实看了才会发现，大部分题目都是难度虚高。主要难度在于应对大粪般的特判。

参考资料：OI-wiki，算法竞赛，其他文章。