计算几何基础与向量代数 (Primitives & Vector Algebra)¶

计算几何（Computational Geometry） 是算法竞赛与计算机图形学中最具数学美感与工程挑战性的领域之一。

在处理几何问题时，最常见的两个痛点是：浮点数精度误差（Floating-point Inaccuracy） 与 复杂的分类讨论（Corner Cases）。现代计算几何通过引入向量代数（Vector Algebra）与符号判定（Sign Testing），将复杂的角、线、面关系转化为简洁纯粹的代数点积与叉积运算，从而大幅减少浮点计算，极大提高程序的鲁棒性与运行效率。

1. 浮点精度控制与基础几何原语¶

1.1 浮点数误差与 `eps` 比较¶

计算机中浮点数（double）存在固有的舍入误差。直接使用 == 判断浮点数相等会导致致命的误判。通常定义一个微小量 $\epsilon$（如 const double eps = 1e-9;）：

#include <cmath>

const double eps = 1e-9;

// 符号函数: 判正负与零
int sgn(double x) {
    if (std::fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

// 浮点数比较
int dcmp(double x, double y) {
    if (std::fabs(x - y) < eps) return 0;
    return x < y ? -1 : 1;
}

整数坐标优先原则

若输入坐标均为整数（如 LeetCode 绝大多数题目），在进行共线、转向、相交判定时，绝对优先使用整数十字相乘，彻底避免除法和浮点数运算，实现 100% 精确判定！

1.2 点与二维向量结构体设计¶

二维平面中的点和向量均可用有序实数对 $(x, y)$ 表示。我们在 C++ 中将其统一封装：

#include <cmath>

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

using Vector = Point; // 向量是点的一体两面

// 向量基本运算
Vector operator+(const Vector& A, const Vector& B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator-(const Point& A, const Point& B)   { return Vector(A.x - B.x, A.y - B.y); }
Vector operator*(const Vector& A, double p)        { return Vector(A.x * p, A.y * p); }
Vector operator/(const Vector& A, double p)        { return Vector(A.x / p, A.y / p); }

bool operator==(const Point& a, const Point& b) {
    return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
}

2. 向量两大核心运算：点积与叉积¶

2.1 点积 (Dot Product)¶

两个向量 $\vec{A} = (x_1, y_1)$ 与 $\vec{B} = (x_2, y_2)$ 的点积定义为：

\[ \vec{A} \cdot \vec{B} = x_1 x_2 + y_1 y_2 = |\vec{A}| |\vec{B}| \cos\theta \]

其中 $\theta$ 是 $\vec{A}$ 与 $\vec{B}$ 的夹角。

点积的四大几何意义：¶

计算模长：$|\vec{A}| = \sqrt{\vec{A} \cdot \vec{A}}$；
正交性判定（垂直）：$\vec{A} \perp \vec{B} \iff \vec{A} \cdot \vec{B} = 0$；
夹角类型判定：
$\vec{A} \cdot \vec{B} > 0 \iff \theta \in [0, \pi/2)$（锐角）；
$\vec{A} \cdot \vec{B} = 0 \iff \theta = \pi/2$（直角）；
$\vec{A} \cdot \vec{B} < 0 \iff \theta \in (\pi/2, \pi]$（钝角）；
投影长度：$\vec{A}$ 在 $\vec{B}$ 上的有向投影长度为 $\frac{\vec{A} \cdot \vec{B}}{|\vec{B}|}$。

2.2 叉积 (Cross Product)¶

二维向量的叉积定义为外积在 Z 轴上的标量投影：

\[ \vec{A} \times \vec{B} = x_1 y_2 - x_2 y_1 = |\vec{A}| |\vec{B}| \sin\theta \]

叉积的三大几何意义：¶

有向面积：$|\vec{A} \times \vec{B}|$ 等于以 $\vec{A}$ 和 $\vec{B}$ 为两邻边的平行四边形的面积。三角形 $OAB$ 的有向面积为 $\frac{1}{2} (\vec{A} \times \vec{B})$；
左右相对位置 / 转向判定（CCW - Counter-Clockwise）：
$\vec{A} \times \vec{B} > 0 \iff \vec{B}$ 在 $\vec{A}$ 的逆时针方向（左侧）；
$\vec{A} \times \vec{B} = 0 \iff \vec{A}$ 与 $\vec{B}$ 共线（同向或反向）；
$\vec{A} \times \vec{B} < 0 \iff \vec{B}$ 在 $\vec{A}$ 的顺时针方向（右侧）；
三点共线判定：三点 $P_1, P_2, P_3$ 共线 $\iff (P_2 - P_1) \times (P_3 - P_1) = 0$。

// 点积
double dot(const Vector& A, const Vector& B) {
    return A.x * B.x + A.y * B.y;
}

// 叉积
double cross(const Vector& A, const Vector& B) {
    return A.x * B.y - A.y * B.x;
}

// 三点有向面积 (两倍): 向量 AB 叉乘 向量 AC
double cross(const Point& A, const Point& B, const Point& C) {
    return cross(B - A, C - A);
}

3. 线段相交与几何关系判定¶

3.1 线段相交判定：快速排斥实验 + 跨立实验¶

给定两条线段 $AB$ 与 $CD$，判断它们是否相交是计算几何的经典算法。

1. 快速排斥实验 (Bounding Box Check)¶

若两线段的外接矩形（Bounding Box）互不相交，则线段绝对不可能相交：

\[ \begin{aligned} \min(A.x, B.x) \le \max(C.x, D.x) &\land \min(C.x, D.x) \le \max(A.x, B.x) \\ \min(A.y, B.y) \le \max(C.y, D.y) &\land \min(C.y, D.y) \le \max(A.y, B.y) \end{aligned} \]

2. 跨立实验 (Straddle Check)¶

若两线段相交，则线段 $CD$ 的两个端点必须分别位于线段 $AB$ 的两侧（或在线上），反之亦然：

\[ ((\vec{AB} \times \vec{AC}) \cdot (\vec{AB} \times \vec{AD}) \le 0) \land ((\vec{CD} \times \vec{CA}) \cdot (\vec{CD} \times \vec{CB}) \le 0) \]

bool onSegment(const Point& P, const Point& A, const Point& B) {
    // P 在直线 AB 上且在 A, B 矩形范围内
    return sgn(cross(B - A, P - A)) == 0 &&
           sgn(dot(A - P, B - P)) <= 0;
}

bool segmentIntersection(const Point& A, const Point& B, const Point& C, const Point& D) {
    // 快速排斥实验
    if (std::max(A.x, B.x) < std::min(C.x, D.x) ||
        std::max(C.x, D.x) < std::min(A.x, B.x) ||
        std::max(A.y, B.y) < std::min(C.y, D.y) ||
        std::max(C.y, D.y) < std::min(A.y, B.y)) {
        return false;
    }
    // 跨立实验
    double c1 = cross(B - A, C - A), c2 = cross(B - A, D - A);
    double c3 = cross(D - C, A - C), c4 = cross(D - C, B - C);
    return sgn(c1) * sgn(c2) <= 0 && sgn(c3) * sgn(c4) <= 0;
}

3.2 点是否在多边形内部¶

射线法 (Ray Casting Algorithm)：
从待测点 $P$ 向任意方向（通常沿水平正向 $+X$）引一条射线；
统计射线与多边形各边的交点个数：
- 若交点数为奇数，点在多边形内部；
- 若交点数为偶数，点在多边形外部；
需特别处理射线穿过顶点或重合于边的边界退化情况。
凸多边形叉积同号法：
对于凸多边形 $P_1 P_2 \dots P_n$（按逆时针排列），若点 $P$ 位于多边形内部，则对于每一条有向边 $P_i P_{i+1}$，点 $P$ 必须全部位于其左侧：

\[ \forall i, \quad (P_{i+1} - P_i) \times (P - P_i) \ge 0 \]

4. LeetCode 经典真题精选与深度精析¶

LeetCode 1232 - 缀点成线 (Check If It Is a Straight Line) 简单
提示

叉积十字相乘判定三点共线。
- 避免使用斜率除法 $\frac{\Delta y}{\Delta x}$（防止除以 0 导致浮点溢出）。
- 以前两个点作为基准向量 $\vec{v_0} = (x_1 - x_0, y_1 - y_0)$。
- 遍历后续每个点 $i \ge 2$，计算 $\vec{v_i} = (x_i - x_0, y_i - y_0)$，验证叉积是否恒为 0：
\[ (x_1 - x_0)(y_i - y_0) - (y_1 - y_0)(x_i - x_0) = 0 \]
```
- 时间复杂度 $\mathcal{O}(N)$，空间复杂度 $\mathcal{O}(1)$。
```
LeetCode 469 - 凸多边形 (Convex Polygon) 中等
提示

相邻边叉积严格同号判定。
- 一个简单多边形是凸多边形，当且仅当沿着多边形边界遍历时，每次转弯的方向必须始终朝向同一侧（全部逆时针转或全部顺时针转，允许共线不转弯）。
- 遍历连续三点 $P_{i-1}, P_i, P_{i+1}$，计算叉积 $cross = (P_i - P_{i-1}) \times (P_{i+1} - P_i)$。
- 若 $cross \ne 0$，记录其符号；一旦后续出现符号相反的叉积，立即判定为非凸多边形返回 false。
- 时间复杂度 $\mathcal{O}(N)$，空间复杂度 $\mathcal{O}(1)$。
LeetCode 223 - 矩形面积 (Rectangle Area) 中等
提示

一维投影重叠长度与容斥原理。
- 两矩形的总覆盖面积 = 矩形 A 面积 + 矩形 B 面积 - 重叠矩形面积。
- 重叠矩形在 X 轴的投影区间为 $[\max(ax_1, bx_1), \min(ax_2, bx_2)]$，长度为 $\max(0, \min(ax_2, bx_2) - \max(ax_1, bx_1))$；
- 同理计算 Y 轴重叠长度，两投影长度相乘即为重叠面积。严格 $\mathcal{O}(1)$ 时间与空间。