计算几何 Geometry 知识Preview

本文章不追求彻底搞懂计算几何，只追求先把计算几何最基础的知识点和工具大致过一遍，建好知识体系与知识框架

向量 Vector

外积 Product

仅在三维向量空间中适用，记为 $a\times b$ ，其定义如下：

$|a\times b|=|a||b|\sin\left<a,b\right>$
$a\times b$ 与 $a,b$ 均垂直，满足右手法则

接下来我们对于二维向量讨论：

坐标运算

$a\times b= x_1y_2-x_2y_1$

正负号 = 旋转方向

对于 $a\times b$ ：

线性变换

对向量进行变换，相当于乘上一个矩阵

放缩变换

构造对角矩阵：

二维旋转变换

方法：先把原向量的 $x,y$ 分解，然后分别投影到选择后的新坐标轴上，再求出新坐标

通用公式：

平移变换

对于二维向量，因为增加常数 $t$ 非线性，所以我们引入齐次坐标，变成三维，最后一列是平移量。

二维计算几何 2d

极坐标 Coordinate

极坐标是以一点为中心，以 $(x,\alpha)$ 记录位置的坐标表示方法。其中 $\alpha$ 代表旋转的弧度。

直线的表示

在计算几何中，表示直线一般使用直线上的一个点+方向向量来表示。

判断线段是否有交点

对于线段 $AB$ 和 $CD$ ，若二者有交点，必然满足：

$C,D$ 在直线 $AB$ 的异侧
$A,B$ 在直线 $CD$ 的异侧

判断是否在异侧有向量的叉积即可

线段交点求解

先判断一下平行的情况

取点 $B,C$ 。我们要求 $A$ ，只需要知道 $l$ 的长度，然后用 $B$ 平移过去即可。

显然 $\alpha,\beta,s$ 都是好求的，然后上正弦定理即可。

多边形面积

多边形的存储我们一般用逆时针的顺序来存点。

考虑向量外积的几何意义，我们只需要求每条相邻边外积和的绝对值即可。

三维计算几何 3d

平面的表示

我们一般使用平面上的一个点 $A$ 和平面的法向量 $\vec{n}$ 来表示一个平面。

那么平面上的所有点 $B$ 均满足：

$\vec{AB}\cdot \vec{n} = 0$

且充要。

三余弦定理

我们有 $\cos\angle BOC=\cos\angle BOA\cdot\cos \angle AOC$

三正弦定理

我们有 $\sin \gamma=\sin\alpha\cdot\sin \beta$

Pick 定理

适用：网格图、顶点均为整点

定义：对于简单多边形，其面积 $A$ ，内部格点数 $i$ ，边上格点数目 $b$ 满足：

$A=i+\frac{b}{2}-1$

判断边上的格点数目的方法：

因为线段长度均为整点，设一条线段两点差为 $(dx,dy)$ ，则线段上点的数量为 $\gcd(dx,dy)+1$ 。但注意，两端点会被计算两次。

三角剖分 Triangulation

我们设法求完美三角剖分，我们使用 Delaunay 三角剖分 法。

这种剖分有两个性质：

任意一个三角剖分的外接圆不含其它任何的点
在所有剖分中，这种剖分的最小角最大

分治构造法

我们先把所有点按 $x$ 升序排列，然后不断分治，直到子点集大小不超过3。

我们现在开始回溯，考虑把所有左右两部分的三角剖分合并。

合并的操作：

第一步：插入 base L-R edge，即最底下一条不与左右任何边交叉的边。
第二步：左右各自筛选可能的点

可能的点满足

是 LR-edge 中其中一个点原来的连边（这个是3中可能点的定义）
与 LR-edge 的夹角小于180度
这三点构成的圆内不包含任何的可能点

图中的7号点满足条件。于是我们连接 2-7 为我们下一条 L-R edge，并删除 6-8 点。

以此进行下去。当左右均不存在可行点时，我们就完成了合并。

Voronoi 图

Delaunay三角剖分和Voronoi图是对偶关系。

定义：把平面切成一块块多边形，这个多边形里所有点，到内部种子点的距离，比到别的点的种子点的距离近。

转化：对种子点进行Delaunay三角剖分后，连接每个三角形取外接圆的圆心连在一起即为Voronoi图。

凸包

包含所有点的最小凸多边形（用橡皮筋捆钉子理解）

性质：任意相邻两条边的叉积必然大于0（左拐）（我们点是逆时针存放）

Andrew 单调链法

排序：把所有点按 $x$ 坐标从小到大排序
建下凸壳：从左往右扫，用栈维护，只要新加入的点和栈顶的两个点发生右拐，就弹出当前栈顶的点
建上凸壳：从右往左扫，过程如上
合并上下凸壳

复杂度 $O(n\log n)$

Craham 扫描法

先找出纵坐标最小的一个点 $P$ ，然后按到这个点的极角大小来排序。

然后维护一个栈，过程和Andrew法同理。

闵可夫斯基和

把 $A$ 中每个点加上 $B$ 中每个点的坐标得到的图形就是闵可夫斯基和。

而且这样合并完后也是一个凸包。

重要性质：对于原凸包 $P,Q$ ，闵可夫斯基和合并后的凸包 $P+Q$ 的边集是 $P,Q$ 中每条边按极角排序后的边集

若 $P,Q$ 中的边本身已经按极角排好序，我们只需要 $O(n+m)$ 的时间即可求出闵可夫斯基和。起点为 $P_1+Q_1$ 。

扫描线

要求：离线

方法：

离散化
把横着的边按纵坐标排序
线段树维护

二维数点问题

长为 $n$ 序列， $m$ 次询问，每次询问在 $[l,r]$ 内值域为 $[x,y]$ 的数的个数

对询问离散化，从左往右扫序列，树状数组维护值域。 $l-1$ 时统计一下， $r$ 时再统计一下。

旋转卡壳 Rotating Calipers

通过两条平行的线，整体绕凸包逆时旋转，同时维护卡尺顶点，在线性时间内求解凸包极值问题。

求凸包直径

凸包中每条边对应一组平行卡尺，一条边贴着当前边，另一条平行线在离该边最远的顶点，且必然逆时针旋转。

于是我们每次移动边的时候不断判断下一个点是否离该边更远。

判断的过程可以用叉积计算三角形面积来。

最小面积矩形覆盖

最优的矩形必然其中一条边贴合，另外三条边经过凸包上的点。

因为我们维护三个指针即可，而且这三个指针相互独立。

求对面点的方法同理。求两侧点可以使用点积，因为点积的本质是投影长度。

如图中所示，我们可以通过用点积求 $m,n$ 进行判断。

半平面交

半平面：一个直线一侧的所有区域（由于我们直线是用向量定义，所以可以统一约定直线的左侧或右侧）
半平面交：多个半平面的交集
多边形的核：多边形内部的一篇区域，此区域内任意一点可以看见多边形的所有边界

多边形的核求法：把多边形每条边视为向内的有向直线，所有半平面的交集就是核

S&1 算法

第一步：极角排序（同极角只保留最内侧）
第二步：单调队列维护线段

哪些边会被pop掉？队尾的边 + 队首的边（在最后封闭的时候会被pop）

pop判断标准：上一个交点在当前这条向量表示的半平面的异侧

如图所示，插入 $\vec{c}$ 边，D点在 $\vec{c}$ 右侧，故 $\vec{b}$ 被pop掉。

队首也会被pop，如图，加入 $\vec{f}$ ，则 $\vec{a}$ 会被pop掉。

注意先pop队尾再pop队首。

平面最近点对

求二维平面最近的点对（欧氏距离）

分治法

按 $x$ 排序，随后分治。

考虑左侧最小为 $h_1$ ，右侧最小为 $h_2$ ，我们令 $h=\min(h_1,h_2)$ 。

此时我们只需要考虑里中线差值小于 $h$ 的点。我们对这些点对 $y$ 排序（这个过程两边可以本身就按 $y$ 排好，然后two-pointer合并即可）

此时对于每个点，我们只和它下方、纵向差小于 $h$ 的点计算距离。

关键性质：这个点最多只和下方7个点比对

感性证明：若超过，则之前的答案必然小于 $h$

复杂度 $O(n\log n)$

有序扫描 + 平衡树

这里的平衡树我们可以用 multiset 代替。

按 $x$ 排序
建立平衡树，按 $y$ 坐标来维护
对于每个点，假设之前的答案为 $d$ $d$
1. 先删除横向距离 $\Delta x\ge d$ 的点
2. 在平衡树中逐个遍历 $[y-d,y+d]$ 的点
3. 将当前点插入平衡树

同样可以由每个点仅少量候选实现常数保证。

复杂度 $O(n\log n)$

随机网格哈希法

随机打乱所有点
假设前 $i-1$ 个点的答案为 $s$ ，我们按 $s$ 为边长划分网格
对于当前第 $i$ 个点，我们只检查自身和周围9个网格的点。这些点的数量受到 $s$ 的限制，是 $O(1)$ 个的。
若 $s$ 被更新，我们就重构网格。由于我们已随机打乱，所以重构次数均摊下来仍为 $O(n)$

复杂度期望为 $O(n)$ 。

随机增量法

我们先对输入数据随机，然后每次增加一个来更新答案。

最小圆覆盖

平面上 $n$ 个点，求最小的圆覆盖所有点。

我们先把所有点打乱：

第一层：我们遍历 $i$

假设我们已有前 $i-1$ 个点组成的最小圆，如果 $i$ 在当前的圆里，跳过。

否则说明 $i$ 一定在最小圆中。我们把 $i$ 作为当前圆一点，半径设为0，并进入第二层。

第二层：我们在 $1\sim i-1$ 中遍历 $j$

若 $j$ 点在前 $j-1$ 构成的最小圆中，跳过。

否则建立以 $i,j$ 为直径的圆，进入第三层。

如果 $j$ 全部遍历完，回到第一层。

第三层：我们在 $1\sim j-1$ 中遍历 $k$

若 $k$ 点在前 $k-1$ 构成的最小圆中，跳过。

否则建立以 $i,j,k$ 为直径的圆。

如果 $k$ 全部遍历完，回到第二层。

伪代码：

函数 求最小覆盖圆(所有点):
    shuffle(所有点)          // 第一步：先把点随机打乱顺序
    当前圆 = circle_1点(所有点[0])   // 初始圆：只有第一个点

    // 第一层：逐个往里加第 i 个点
    遍历 i 从 1 到 最后一个点:
        第i个点 = 所有点[i]
        如果 is_inside(第i个点, 当前圆) 为真:
            跳过   // 点本来就在圆里，圈子不用改
        否则:
            // 点在圆外 → 新圆必须经过这个点，重置圆
            当前圆 = circle_1点(第i个点)

            // 第二层：找第二个必须贴在圆边上的点 j
            遍历 j 从 0 到 i-1:
                第j个点 = 所有点[j]
                如果 is_inside(第j个点, 当前圆) 为真:
                    跳过
                否则:
                    // j也在圆外 → 圆必须同时过 i 和 j
                    当前圆 = circle_2点(第i个点, 第j个点)

                    // 第三层：找第三个必须贴在圆边上的点 k
                    遍历 k 从 0 到 j-1:
                        第k个点 = 所有点[k]
                        如果 is_inside(第k个点, 当前圆) 为真:
                            跳过
                        否则:
                            // k也在圆外 → 三点定一个圆
                            当前圆 = circle_3点(第i个点, 第j个点, 第k个点)

    返回 当前圆