第15章：计算几何
本章目标
读完本章你会：
- 用叉积判断线段是否相交、点是否在多边形内
- 手写 Graham Scan 和 Jarvis March 求凸包
- 实现扫掠线算法求线段交点
- 理解计算几何中退化情况的处理（共线、重合）
知识讲解
从一个生活例子开始
你有 n 根钉子在木板上，用一根橡皮筋把它们全包起来——橡皮筋形成的轮廓就是凸包。凸包是这些点的"外轮廓"。
现在你把一张纸撕成两半——两半的边缘能不能拼回去？判断两条线段是否相交就是解决这个问题的关键。
计算几何的核心工具是叉积——它能告诉你一个点在线段的左侧还是右侧，这就是大多数几何算法的基础。
工作原理
15.1 叉积：计算几何的基本运算
cross(A, B) = A.x·B.y - A.y·B.x = |A|·|B|·sin(θ)叉积 > 0：B 在 A 的逆时针方向（左侧）
叉积 < 0：B 在 A 的顺时针方向（右侧）
叉积 = 0：A 和 B 共线
判断线段相交： 线段 AB 和 CD。如果 A 和 B 在 CD 的两侧，且 C 和 D 在 AB 的两侧，则相交。
点在线段上： 叉积为 0 且点在线段的包围盒内。
15.2 凸包算法
Graham Scan（O(n log n)）：
1. 找最低最左的点作为起点 p₀
2. 按极角排序其余点（相对于 p₀）
3. 用栈维护凸包：- 栈中始终是部分凸包的点- 对每个新点：while 最近三个点形成"右转"（非左转）→ 弹出中间点- 入栈新点
Jarvis March（O(nh)，h 是凸包点数）：
从最左点开始，每次找"相对于当前点最右转（或最左转）的邻居"。
类似于"包裹礼物"——用纸一圈圈包。
当 n 很大但凸包点很少时，Jarvis 更快（O(nh) < O(n log n)）。
15.3 扫掠线算法
找所有线段交点（Bentley-Ottmann）：
扫掠线从左到右扫描平面。维护两个数据结构：
- 事件队列： 按 x 坐标排序——线段左端点、线段右端点、交点
- 扫掠线状态： 当前垂直线穿过的线段，按 y 坐标排序
当两条线段在扫掠线状态中相邻且变为相交 → 新增交点事件。
复杂度 O((n+k) log n)，其中 k 是交点数。
代码实战
include/algo/geometry.h
#ifndef ALGO_GEOMETRY_H_
#define ALGO_GEOMETRY_H_#include <vector>namespace algo {struct Point {double x, y;Point operator-(const Point& other) const;bool operator<(const Point& other) const; // 字典序（用于排序/去重）
};// 叉积：OA × OB
double Cross(const Point& O, const Point& A, const Point& B);// 判断线段 AB 和 CD 是否相交
bool SegmentsIntersect(const Point& A, const Point& B,const Point& C, const Point& D);// Graham Scan 凸包——返回逆时针的凸包点序列
std::vector<Point> GrahamScan(const std::vector<Point>& points);// 判断点是否在凸多边形内（顶点逆时针）
bool PointInConvexPolygon(const Point& p,const std::vector<Point>& polygon);// 最近点对——返回最近距离，O(n log n)
double ClosestPair(const std::vector<Point>& points);} // namespace algo#endif // ALGO_GEOMETRY_H_
include/algo/geometry_impl.h（Graham Scan 核心）
namespace algo {inline double Cross(const Point& O, const Point& A, const Point& B) {return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}inline bool SegmentsIntersect(const Point& A, const Point& B,const Point& C, const Point& D) {auto d1 = Cross(C, D, A);auto d2 = Cross(C, D, B);auto d3 = Cross(A, B, C);auto d4 = Cross(A, B, D);if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {return true;}// 退化情况：端点在另一线段上auto on_segment = [](const Point& p, const Point& q, const Point& r) {return std::min(p.x, r.x) <= q.x && q.x <= std::max(p.x, r.x) &&std::min(p.y, r.y) <= q.y && q.y <= std::max(p.y, r.y);};if (d1 == 0 && on_segment(C, A, D)) return true;if (d2 == 0 && on_segment(C, B, D)) return true;if (d3 == 0 && on_segment(A, C, B)) return true;if (d4 == 0 && on_segment(A, D, B)) return true;return false;
}inline std::vector<Point> GrahamScan(const std::vector<Point>& points) {if (points.size() <= 2) return points;auto pts = points;// 找最低最左的点作为起点std::swap(pts[0], *std::min_element(pts.begin(), pts.end(),[](const Point& a, const Point& b) {return std::tie(a.y, a.x) < std::tie(b.y, b.x);}));const Point& p0 = pts[0];// 按极角排序（叉积判断）std::sort(pts.begin() + 1, pts.end(),[&](const Point& a, const Point& b) {double c = Cross(p0, a, b);if (c != 0) return c > 0; // 逆时针在前// 共线时，距离近的在前double da = (a.x - p0.x)*(a.x - p0.x) + (a.y - p0.y)*(a.y - p0.y);double db = (b.x - p0.x)*(b.x - p0.x) + (b.y - p0.y)*(b.y - p0.y);return da < db;});std::vector<Point> hull;for (auto& p : pts) {// 注意：Cross ≤ 0 会弹出共线的中间点，确保凸包只保留端点// 如果需要保留共线的所有顶点，改用 Cross < 0while (hull.size() >= 2 &&Cross(hull[hull.size() - 2], hull.back(), p) <= 0) {hull.pop_back(); // 右转或共线 → 弹出}hull.push_back(p);}return hull;
}} // namespace algo
本章小结
- 叉积是计算几何的核心——判断左/右/共线
- Graham Scan O(n log n) 通过极角排序 + 栈扫描求凸包
- Jarvis March O(nh) 适合凸包点数很少的稀疏情况
- 线段相交用叉积判断两侧性
- 处理退化情况（共线、点在线段上）是计算几何的重要工程细节
关键术语
| 术语 | 释义 |
|---|---|
| 叉积(Cross Product) | 二维向量 OA×OB = xA·yB - yA·xB，符号表示方向 |
| 凸包(Convex Hull) | 包含所有点的最小凸多边形 |
| Graham Scan | 基于极角排序和栈扫描的凸包算法，O(n log n) |
| 扫掠线 | 从左到右扫描平面，维护事件队列和扫掠线状态 |