计算几何基础 (Geometry Basics)

计算几何（Computational Geometry）是算法竞赛中逻辑最为严密、容错率最低的版块之一。其核心在于通过向量算子将欧几里得几何直观转化为代数运算，并利用鲁棒性策略屏蔽浮点数截断带来的逻辑崩塌。

---

1. 精度控制与误差收敛分析 (Numerical Precision & Convergence)

在计算机中，实数 $\mathbb{R}$ 被离散化为浮点数集。由于有限位数的限制，几何判定的不一致性是导致程序崩溃的主因。

1.1 机器精度与 $\epsilon$ 模型 (Static Epsilon)

通过引入一个小量 $\epsilon$ ($10^{-9} \sim 10^{-11}$ )，我们将连续判定转化为区间判定。

1.2 误差传播与收敛界证明 (Error Propagation)

浮点运算的相对误差收敛界

定理：设实数 $x, y$ 的机器表示为 $fl(x) = x(1+\delta)$，其中 $|\delta| < \epsilon_{mach}$。 对于二元运算 $\circ \in \{+, -, \times, \div\}$，存在 $\epsilon_{\circ}$ 使得： $fl(x \circ y) = (x \circ y)(1 + \epsilon_{\circ})$ 证明概要： 由 IEEE 754 标准，舍入误差满足 $\frac{|fl(x)-x|}{|x|} \le \frac{1}{2} B^{1-p}$。对于多步运算，误差按泰勒展开线性累积。

• 灾难性抵消 (Catastrophic Cancellation)：若 $x \approx y$ 且异号，则 $fl(x+y)$ 的相对误差会迅速发散。
• 收敛准则：在几何算法中，尽量使用低阶多项式（如叉积是坐标的二阶形式）而非超越函数（如 atan2, acos），因为后者的误差项包含更高阶的泰勒展开剩余项。

---

2. 拓扑原语一致性证明 (Topological Consistency)

几何算法的鲁棒性不仅取决于精度，更取决于代数一致性（Algebraic Consistency）。

2.1 全序关系保护 (Strict Weak Ordering)

精度陷阱：传递性失效证明

命题：在浮点运算中，$(a = b) \land (b = c) \centernot\implies (a = c)$。 证明： 设 $a-b = 0.6\epsilon$ 且 $b-c = 0.6\epsilon$。 按 sign 函数定义：

1. $|a-b| < \epsilon \implies a = b$
2. $|b-c| < \epsilon \implies b = c$ 然而 $a-c = (a-b) + (b-c) = 1.2\epsilon > \epsilon$，故 $a \neq c$。 后果：会导致 std::sort 崩溃（Segment Fault）或产生逻辑环。 准则：在排序算子中，必须强制使用 dcmp(a, b) < 0 而非 a <= b 以满足严格弱序。

2.2 几何原语判定 (Geometric Predicates)

算子	代数表达	鲁棒判定	几何意义
OnLine	$\vec{a} \times \vec{b} = 0$	sign(cross(a, b)) == 0	共线判定
LeftTurn	$\vec{a} \times \vec{b} > 0$	sign(cross(a, b)) > 0	逆时针旋转 (CCW)
InSegment	$(\vec{p}-\vec{a}) \cdot (\vec{p}-\vec{b}) \le 0$	sign(dot(a-p, b-p)) <= 0	点在线段投影内

---

3. 核心向量算子鲁棒性验证 (Robust Vector Operators)

3.1 叉积的有向面积特性

叉积的行列式几何意义

定理：对于向量 $\vec{a}=(x_1, y_1), \vec{b}=(x_2, y_2)$，$\vec{a} \times \vec{b} = x_1y_2 - x_2y_1$。 证明： 利用极坐标：$\vec{a} = (r_a\cos\alpha, r_a\sin\alpha), \vec{b} = (r_b\cos\beta, r_b\sin\beta)$。 $\vec{a} \times \vec{b} = r_a r_b (\cos\alpha\sin\beta - \sin\alpha\cos\beta) = r_a r_b \sin(\beta-\alpha)$。 由于 $|\vec{a}|=r_a, |\vec{b}|=r_b$，且 $\theta = \beta-\alpha$ 为 $\vec{a}$ 到 $\vec{b}$ 的转角， 故 $\vec{a} \times \vec{b} = |\vec{a}||\vec{b}|\sin\theta$。 由几何定义，平行四边形面积 $S = |\vec{a}| \cdot (|\vec{b}|\sin\theta)$。其正负号严格对应了转动方向。

---

4. 交点一致性校验 (Intersection Consistency)

在计算直线交点时，必须处理近乎平行的情况。

直线交点通用公式

设直线 $L_1: P_1 + t\vec{v_1}$，$L_2: P_2 + u\vec{v_2}$。 交点存在当且仅当 $\vec{v_1} \times \vec{v_2} \neq 0$。 $t = \frac{(P_2 - P_1) \times \vec{v_2}}{\vec{v_1} \times \vec{v_2}}$ 稳定性校验：若 $|\vec{v_1} \times \vec{v_2}| < \epsilon \cdot |\vec{v_1}||\vec{v_2}|$，应判定为平行，避免除以极小值导致的结果溢出。

---

5. 经典教材级例题与练习 (Exercises)

例题 1：点在线段上的充分必要条件证明

命题：点 $P$ 在线段 $AB$ 上当且仅当 $\vec{PA} \times \vec{PB} = 0$ 且 $\vec{PA} \cdot \vec{PB} \le 0$。 证明：

1. 必要性：若 $P \in AB$，则 $A, P, B$ 共线 $\implies \vec{PA} \parallel \vec{PB} \implies \text{cross} = 0$。且 $P$ 在 $A, B$ 之间，向量方向相反 $\implies \text{dot} \le 0$。
2. 充分性：$\text{cross}=0 \implies P$ 在直线 $AB$ 上。设 $P = A + \lambda(B-A)$，则 $\vec{PA} = -\lambda(B-A)$，$\vec{PB} = (1-\lambda)(B-A)$。 $\vec{PA} \cdot \vec{PB} = -\lambda(1-\lambda)|B-A|^2 \le 0 \implies \lambda(1-\lambda) \ge 0 \implies 0 \le \lambda \le 1$。 故 $P$ 在线段 $AB$ 上。

练习 1：多边形面积的有向性合并

题目描述：给定简单多边形顶点 $P_1, P_2, \dots, P_n$，证明其面积 $S = \frac{1}{2} \sum_{i=1}^n (P_i \times P_{i+1})$。 推导：利用格林公式的离散形式。每个对原点的三角形 $OP_iP_{i+1}$ 的有向面积为 $\frac{1}{2} P_i \times P_{i+1}$。若 $O$ 在多边形外，外部面积会在环绕过程中被正负抵消。

Check Solution

练习 2：最小圆覆盖 (Smallest Enclosing Circle)

题目描述：给定 $n$ 个点，求覆盖所有点的最小圆。 思路：随机增量法。期望复杂度 $O(n)$。证明核心在于圆的唯一性与三点确定圆。

Check Solution

---

🎯 模块导航

• 凸包算法 (Convex Hull) - 构建最小凸闭包与拓扑证明。
• 半平面交 (Half-plane Intersection) - 线性约束与鲁棒性优化。
• 扫描线技巧 (Scanning Line) - 降维打击与复杂度边界。
• 旋转卡壳 (Rotating Calipers) - 极值问题与对踵点维护。