计算几何学习笔记

zhoumurui · 2026-09-20 12:15:23 · 算法·理论

AI 使用声明：我在学习这些算法和理解这些证明的时候大量借用了 AI 进行辅助，因此 AI 显然对这篇文章有着较大的贡献。但保证文章内容全部是我手打的。

前言

说三件事。

第一件事，笔者在学习计算几何做法的时候费了非常多的功夫，期间也阅读了很多难以在可接受的时间内理解的笔记。因此，为初学者提供可能有助于理解的内容是写作此笔记的一大目的。

第二件事，虽然该笔记在很多地方添加了比较详细的证明，但是计算几何的很多直觉实际上来自于画图。对一些细节不理解的读者可以试着在草稿纸上画一下。

• 如果一种图画不出来，可能你想要描述的情况并不存在。
• 你可能漏掉了一些情况。大分讨是计算几何的一环。

第三件事，长文警告。本文两万多字（含代码）。

本文覆盖的算法：

• 凸包。
• 旋转卡壳。
• 半平面交。

计算几何基本功

弧度制

定义 1 \pi rad = 180\degree。

推论 圆心角为 1rad 的扇形，弧长和半径相等。

之后描述角度的时候，如果不使用 \degree 标注，一律视为使用弧度制。如 \frac \pi 2 表示直角。

平面向量

向量的定义

定义 2 向量是既有大小又有方向的量。

向量的表示示例：\bm a，\bm b，……

如何表示平面向量：

• 平面向量 \bm a 的方向可以这样表示：一个方向等同于 x 轴正方向的向量，想要与 \bm a 同向，需要逆时针旋转的最小正角度。

  例如：方向等同于 y 轴正方向的向量，方向记为 \frac{\pi}{2}；方向等同于 y 轴负方向的向量，方向记为 \frac{3\pi}{2}。

  大小直接记就可以了。于是向量用模长 \left| \bm a\right| \ge 0 和方向角 \theta \in [0,2\pi) 表示了。

• 注意到平面上一个点指向另一个点的有向线段就是一个向量。向量也可以用有向线段表示。

  从 O(0,0) 指向 P(x,y) 的有向线段，大小和方向与从 A(x_0,y_0) 指向 B(x_0+x,y_0+y) 的有向线段相同。

  因此一个向量如果和从 O(0,0) 指向 P(x,y) 的有向线段大小和方向都相同，就可以记为 (x,y)。

  于是向量用横坐标 x \in \mathbb R 和纵坐标 y \in \mathbb R 表示了。

两种记法的换算：

向量 \bm a=(x,y) 的大小为 \sqrt{x^2+y^2}。

当 x \not = 0 时，方向角 \theta 满足 \tan \theta = \frac{y}{x}。然后你判断一下 (x,y) 在哪个象限就可以求出 \theta。x=0 是平凡的。

特别地，\bm a=(0,0) 称为零向量，记作 \bm 0。它的大小为 0，方向不存在。

向量的加减法运算

定义 3 定义向量 \bm a=(x_1,y_1) 和 \bm b=(x_2,y_2) 的和 \bm a+\bm b 等于 (x_1+x_2,y_1+y_2)。

定义 4 定义向量 \bm a=(x_1,y_1) 和 \bm b=(x_2,y_2) 的差 \bm a-\bm b 等于 (x_1-x_2,y_1-y_2)。

如果用模长和方向角表示向量，加减法计算遵守平行四边形定则和三角形定则。

具体地：

（这里的描述中，\bm {AB} 表示从 A 点到 B 点的有向线段对应的向量。以后可能也会使用类似的表述。）

• 三角形定则：对平面上三个点 A,B,C，\bm {AC} = \bm {AB} + \bm {BC}。
• 平行四边形定则：对平面上的平行四边形 ABCD，\bm{AB}+\bm{AD} = \bm{AC}。

前者的证明：

令 A(a_x,a_y),B(b_x,b_y),C(c_x,c_y)，则 \bm {AB}= (b_x - a_x,b_y - a_y)，\bm {BC}= (c_x-b_x,c_y-b_y)，\bm {AC} = (c_x - a_x,c_y - a_y)。

带入原式发现左边等于右边。

后者的证明：

注意到 \bm {AD} 和 \bm {BC} 同向且相等。

向量的数乘

定义 5 定义向量 \bm a=(x,y) 和实数 k 的乘积 k\bm a 等于 (kx,ky)。

如果用模长和方向角表示向量，对于 k>0，直接将模长乘上 k 即可。方向不变。对于 k=0，是 \bm 0。对于 k<0，方向会反。

向量的共线

定义 6 定义向量 \bm a，\bm b 共线，当且仅当存在不全为 0 的 \lambda_1,\lambda_2 \in \mathbb R，使得 \lambda_1 \bm a = \lambda_2 \bm b。记为 \bm a \parallel \bm b。

推论 1 对于任意向量 \bm a，\bm 0 \parallel \bm a。

推论 2 对于任意一对非零共线向量 \bm a 和 \bm b，\left| \theta_{\bm a} - \theta_{\bm b}\right| \in \{0,\pi\}。

也即方向相同或相反。

平面向量基本定理

定义 7 形如 \lambda_1\bm e_1+\lambda_2\bm e_2 的式子称为 \bm e_1,\bm e_2 的线性组合。

定理 1（平面向量基本定理）若 \bm e_1,\bm e_2 是同一平面内两个不共线的向量，则对任意向量 \bm a，存在唯一实数对 (\lambda_1,\lambda_2)，使得 \bm a=\lambda_1\bm e_1+\lambda_2\bm e_2。

本定理的结论比较直观，不做证明。

这就是坐标记法的来历：坐标本质是向量在 \bm e_1 = (1,0) 和 \bm e_2 = (0,1) 下的分解系数。

向量的点积

定义 8 定义向量 \bm a=(x_1,y_1) 和 \bm b=(x_2,y_2) 的点积 \bm a \cdot \bm b 等于 x_1x_2 + y_1y_2。

性质 1 \bm a \cdot \bm b = \bm b \cdot \bm a。

性质 2 (\bm a + \bm b) \cdot \bm c = \bm a \cdot \bm c + \bm b \cdot \bm c。

性质 3 (k \bm a) \cdot \bm b = k(\bm a \cdot \bm b)。

如果用模长和方向角表示向量，如何计算点积？

定义 9 定义非零向量 \bm a 和 \bm b 的夹角 \langle\bm a,\bm b\rangle 为 \min\{|\theta_{\bm a}-\theta_{\bm b}|,\ 2\pi-|\theta_{\bm a}-\theta_{\bm b}|\}。

两个向量不平行时，也就是对应的两条直线的夹角中小的那个。

定理 2 设 \bm a,\bm b 为非零向量，夹角为 \theta=\langle\bm a,\bm b\rangle，则

证明 原式等价于：

旋转坐标系，归约到证明当 \bm a = (1,0) 且 \bm b = (\cos \theta,\sin \theta) 且 \theta \in [0,\pi] 时，\bm a \cdot \bm b = \cos \theta。

直接带入定义发现这是对的。

向量的叉积

定义 10 定义向量 \bm a=(x_1,y_1) 和 \bm b=(x_2,y_2) 的叉积 \bm a \times \bm b 等于 x_1y_2 - y_1x_2。

性质 1 \bm a \times \bm b + \bm b \times \bm a = 0。

性质 2 (\bm a + \bm b) \times \bm c = \bm a \times \bm c + \bm b \times \bm c。

性质 3 (k \bm a) \times \bm b = k(\bm a \times \bm b)。

如果用模长和方向角表示向量，如何计算叉积？

定义 11 设 \bm a,\bm b 为非零向量，从 \bm a 到 \bm b 的有向角 \theta 满足 \theta \equiv \theta_{\bm b} - \theta_{\bm a} \pmod {2\pi}，取值为 (-\pi,\pi]。

就是从 \bm a 的方向到 \bm b 的方向要旋转的逆时针度数。

定理 3 设 \bm a,\bm b 为非零向量，从 \bm a 到 \bm b 的有向角为 \theta，则：

证明 原式等价于：

旋转坐标系，归约到证明当 \bm a = (1,0) 且 \bm b = (\cos \theta,\sin \theta) 且 \theta \in (-\pi,\pi] 时，\bm a \times \bm b = \sin \theta。

直接带入定义发现这是对的。

注意到 S_{ABC} = \frac{1}{2} AB \cdot AC\sin A，于是有：

推论 1 三角形 ABC 的面积为 S= \frac{1}{2}|\bm {AB} \times \bm {AC}|。

推论 2 若从 \bm a 到 \bm b 的有向角为 \theta，则 \theta >0 当且仅当 \bm a \times \bm b >0。

这个推论可以用于极角排序（将若干个非零向量按照方向角从小到大排序）。如果 \bm a 和 \bm b 都在上平面或都在下平面，就可以利用这个性质进行极角排序。

::::info[极角排序板子]

struct point{
    int x,y;
}A[50];
point operator - (point a,point b){
    return {a.x-b.x,a.y-b.y};
}
int operator *(point a,point b){
    return a.x*b.y-a.y*b.x;
}
struct line{
    point a,b;
}B[500];
int N;
bool cmp(line a,line b){
    point A=a.b-a.a,B=b.b-b.a;
    //根据数据实际情况，A 和 B 都不会是零向量。
    int flag1=0,flag2=0;
    if (A.y>0||(A.y==0&&A.x>0))flag1=1;
    if (B.y>0||(B.y==0&&B.x>0))flag2=1;
    if (flag1!=flag2)return flag1>flag2;
    else return (A*B)>0;
}

点和直线的性质

方向为 \bm a 的有向直线的左侧半平面，指其逆时针旋转 180\degree 扫过的半平面。右侧类似。

我们可以用一个有向直线来表示一个半平面。表示的就是该有向直线的左侧半平面。

定理 4 考虑点 A,B,P 所在的平面，以下命题成立：

证明 考虑到叉积的符号实际上就对应着从 \bm {AB} 到 \bm {AP} 有向角的范围。

定理 5 直线 AB 和 CD 相交于 P 点，满足：

证明

当 \bm {AP} 和 \bm {AB} 同向时：

当 \bm {AP} 和 \bm {AB} 反向时：

定理 6 过 P 做直线 AB 的垂线，垂足为 H，则：

即点到直线的距离。

证明 考虑右侧的部分。它等于 AP \sin \angle PAB。

因为 \angle PAB 和 \angle PAH 要么相等要么互补，所以也等于 AP \sin \angle PAH。

然后观察到 \triangle APH 上 \sin \angle PAH = \frac{PH}{AP}，做完。

点和线段的性质

定理 7 点 P 在线段 AB 上，当且仅当以下全部成立：

证明 前者使得 P 在直线 AB 上。后者使得 A 和 B 分居 P 的两侧（或与 P 重合）。合起来就是 P 在线段 AB 上的充要条件。

定理 8 P 到线段 AB 的距离为：

• 过 P 做直线 AB 的垂线，垂足为 H，若 H 在线段 AB 上，则答案为：

• 否则为：

证明 前者使用定理 6 的结论。后者直观。

判断两线段是否相交

定理 9 线段 AB 和 CD 相交，当且仅当以下至少一项成立：

证明 必要性：考虑交点 P 的位置。

• 若 P 与 C,D 其中之一重合，满足第二项。
• 若 P 与 A,B 其中之一重合，满足第三项。
• 其他情况，直观地，满足第一项。

充分性：

• 第二项和第三项的充分性显然。
• 对于第一项，可以得出直线 AB 和线段 CD 相交，且线段 AB 与直线 CD 相交。由于可以看出两条直线并不平行（如果平行显然不会满足分居两侧的条件），这两个交点显然是同一个，从而线段 AB 和线段 CD 都通过这个点。

多边形

定义 12 给定平面上 n 个点 P_0(x_0,y_0),P_1(x_1,y_1),\dots,P_{n-1}(x_{n-1},y_{n-1}) 依次相连，称为多边形。

推论 n 边形有 n 个点和 n 条边。

定义 13 若一个多边形的所有 n 条边除相邻边公共端点外两两不相交，称为简单多边形。

定义 14 设简单多边形 P 顶点逆时针排列，令 P_n = P_0，则称它为一个凸多边形，当且仅当对于任意 i \in [0,n)，所有 P_i 和 P_{i+1} 以外的顶点都位于有向直线 \bm {P_i P_{i+1}} 的左侧。

引理 简单多边形外角和为 2\pi。

非常地不显然，也并不直观，但反正初中大家都对这个结论非常了解了那就不再解释了。

定理 10 设简单多边形 P 顶点逆时针排列，令 P_n = P_0，P_{n+1} = P_1，P 是凸多边形当且仅当，对于任意整数 i \in [0,n)：

证明 必要性由定理 4 显然。

充分性，考虑用反证法，存在某个点落在某条有向边的右侧。不妨设这个有向边是 P_0P_1。

你沿着多边形的边逆时针转动，那么你没走到一个端点你就会左转 \theta \in (0,\pi)，然后接着走。

如果你跑到了 \bm{P_0 P_1} 的右侧，说明你总共旋转了超过 \pi！

然后你要想办法试图回到 P_0，但是因为 \bm{P_{n-1}P_0} \times \bm{P_0P_1}>0，所以 P_{n-1} 必然在 \bm{P_0 P_1} 的左侧。

所以你要先从左侧转到右侧再转回左侧，这时你必然累计旋转了超过 2\pi，因此你不是简单多边形，矛盾。因此充分性得证。

定义 15 设 A 为平面上一点，P 为顶点逆时针排列的凸多边形。

• 若 A 在 P 的某条边上，则称 A 在 P 的边界上。
• 否则，若对于多边形的任意一条边 P_iP_{i+1}，A 都在有向边 \bm {P_iP_{i+1}} 的左侧，则称 A 在 P 内侧。
• 否则，称 A 在 P 外侧。

以后若提到多边形，默认讨论凸多边形。

定理 11 在凸多边形内侧或边界上任取两点 A,B，线段 AB 上任意的一点 C 都在该凸多边形的内侧或边界上。

证明 考虑一条有向边 \bm {P_iP_{i+1}}。A 在其左侧（或边界上），B 在其左侧（或边界上），所以整条线段都在其左侧（或边界上）。证毕。

定理 12（鞋带公式的凸多边形情况） 设凸多边形 P 顶点逆时针排列，令 P_n = P_0，则多边形的面积 S 满足

证明 指定凸多边形内的一个点 A。

然后全部加起来之后就发现所有的第一项全都消掉了（\sum_{i=0}^{n-1} \bm {P_iP_{i+1}} = 0）。所以总和就是面积 S。

定理 13 设凸多边形 P 顶点逆时针排列，令 P_n = P_0，则多边形的重心 G 满足

仅做了解，不进行证明。

考这玩意不给公式的出题人保护好自己的母亲。

皮克定理

定理 14（皮克定理） 顶点均为整点的简单多边形内部格点数为 I，边界格点数为 B，则面积为：

仅做了解，不进行证明。

曼哈顿距离和切比雪夫距离

定理 15 令 u=x+y，v=x-y，则：

仅做了解，不进行证明。

凸包

定义 16 给定平面上 n 个点，如果某个凸多边形满足这 n 个点都在它的内部或边界上，并且在所有满足这一条件的凸多边形中面积最小，就称这个凸多边形为这 n 个点的凸包。

（注意：凸包可能退化成线段或点。）

观察一个凸包。

观察 凸包的每个顶点都来自给定的 n 个点。

理解 考虑如果多边形一个角上没有给定的点，把这个角切掉一点点。切了之后，多边形就会变小，而且由于给定的点数量有限，一定存在切法不会把点切出去，所以它不是凸包。

让我们从给定的 n 个点中，选出一个横坐标最小的点 A 和一个横坐标最大的点 B。

考虑沿着多边形的边逆时针走，你会先在直线 AB 的下方从 A 走到 B，然后再在直线 AB 的上方从 B 走回 A。

（注意定理 11，线段 AB 被包括在凸包内。所以这一观察是直观的。）

我们声称在下方从 A 走到 B 的路径为凸包的下凸壳，在上方从 B 走回 A 的路径为凸包的上凸壳。

这两个拼起来就是整个凸包。

结论 1 在下凸壳上从左往右走，斜率单调递增；在上凸壳上从左往右走，斜率单调递减。

因为，在下凸壳上走的时候一直左转，左转斜率会变大。在上凸壳上走的时候一直右转，右转斜率会变小。

结论 2 在上 / 下凸壳上从左往右走，横坐标单调不减。

以上凸壳为例，下凸壳类似。

每一步都要右转。如果 P_i 的横坐标小于 P_{i-1}，那么你发现当前的前进方向已经是向左而不是向右了。根据结论 1，斜率单减，不可能从负的再变回正的，所以你不可能再向右了。

因为 P_i 的横坐标小于 P_{i-1} 所以 P_i 不是 B。而且之后你的横坐标不能再增大，想从 P_i 到达 B 已经不可能了，矛盾。

我们尝试分别求出上凸壳和下凸壳。以上凸壳为例。

将所有点按横坐标排序。

作为上凸壳，根据先前的结论，它一定选取了这 n 个点中的一部分，然后按照横坐标从小到大的顺序依次相连。

考虑这样一个问题：

在什么情况下，一个点 P_i 会出现在上凸壳的端点上？

答案是：

P_i 在上凸壳的端点上，当且仅当不存在 <i 的整数 j 和 >i 的整数 k，满足直线 P_jP_k 在 P_i 的上方（或者也可以说成，P_i 在 \bm {P_jP_k} 的右侧。另外，三点共线也不允许存在）。

对于必要性，如果存在这样的 (j,k)，则 P_i 被其他点构成的上凸壳盖住了，就算去掉也不会影响上凸壳，与 P_i 在上凸壳的端点上矛盾。

对于充分性，注意到如果删除 P_i，其他点都无法覆盖 P_i 这个点，所以 P_i 是重要的，因此它在上凸壳的端点上。

接下来我将描述算法流程，随后证明它求出的是正确的上凸壳。

开一个栈，首先加入 P_0 = A 和 P_1。

对于 P_2 \sim P_{n-1}，加入 P_i 前，先取出栈顶的两个点，设分别是 C 和 D。其中 D 是栈顶。

• 若 D 在 \bm{CP_i} 的右侧（或在直线 CP_i 上），弹出栈顶（即 D）。

重复此操作，直到 D 在 \bm{CP_i} 的左侧。然后再将 P_i 入栈。