计算几何入门：点、直线、线段位置关系与向量运算实战-平芜编程栈

1. 项目概述：从“点”开始，构建你的空间思维框架

在编程和算法领域，尤其是涉及到图形、游戏开发、机器人导航、地理信息系统（GIS）乃至计算机视觉时，我们常常需要处理一些最基础却又至关重要的元素：点、直线和线段。这些元素构成了我们理解和操作二维乃至三维空间的基石。你可能会觉得，这些不是初中几何就学过的概念吗？没错，但计算几何这门学问，正是将这些基础的几何概念，用计算机能够理解和高效处理的方式重新定义和实现。它不关心完美的理论证明，更关注如何用代码稳定、精确且高效地解决“位置关系”这类实际问题。

想象一下这些场景：在自动驾驶中，判断传感器检测到的障碍物点是否在车辆规划的行车路径（线段）范围内；在游戏里，检测子弹的射线（直线）是否击中了敌人的模型（由无数线段构成的边界）；在地图应用中，快速查询某个地理位置（点）位于哪个行政区划（多边形，由线段首尾相连构成）内。所有这些问题的核心，都绕不开对点、直线、线段之间位置关系的计算。

很多人初次接触时，会试图用直观的数学公式直接硬编码，结果往往陷入浮点数精度误差的泥潭，或者写出冗长且脆弱的判断逻辑。计算几何提供了一套基于向量运算的健壮方法论，它将几何问题转化为代数问题，通过计算叉积、点积等运算，可以优雅地处理包括相交、平行、垂直、距离、投影等在内的各种关系。掌握这套方法，意味着你获得了一把解决众多空间计算问题的万能钥匙。无论你是算法竞赛选手、图形学开发者，还是任何需要处理空间数据的工程师，深入理解点、线、段的位置关系及其计算，都是不可或缺的基本功。

2. 核心基石：向量——连接几何与代数的桥梁

在进入具体的位置关系判断之前，我们必须先统一“语言”。在计算几何中，这个语言就是向量。点可以用坐标表示，而向量则代表了方向和大小。从点A到点B的向量，记作 $\vec{AB}$，在二维中其坐标就是 $(B.x - A.x, B.y - A.y)$。选择向量作为核心工具，有两大不可替代的优势：一是它能天然地处理平移（向量本身与起点无关），二是为后续的叉积和点积运算铺平了道路。

2.1 向量的基本运算：点积与叉积

这是计算几何中最重要的两种运算，它们的几何意义远比代数形式更有用。

点积，也叫数量积。对于二维向量 $\vec{a}=(x_1, y_1)$ 和 $\vec{b}=(x_2, y_2)$，其点积定义为 $\vec{a} \cdot \vec{b} = x_1x_2 + y_1y_2$。它的核心几何意义是：

投影长度：$\vec{a} \cdot \vec{b} = |\vec{a}| |\vec{b}| \cos\theta$，其中 $\theta$ 是两向量夹角。这常用于计算一个向量在另一个向量方向上的“影子”有多长。
夹角判断：如果 $\vec{a} \cdot \vec{b} > 0$，则夹角为锐角；等于0则为直角（垂直）；小于0则为钝角。这是判断垂直关系的直接依据。
求向量长度：向量与自身的点积开平方，即 $|\vec{a}| = \sqrt{\vec{a} \cdot \vec{a}}$。

叉积，也叫向量积或外积。在二维中，对于向量 $\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} \times \vec{b}$ 的值表示由 $\vec{a}$ 和 $\vec{b}$ 所张成的平行四边形的有向面积。如果结果为正，说明 $\vec{b}$ 在 $\vec{a}$ 的逆时针方向（左侧）；结果为负，则在顺时针方向（右侧）；结果为0，则两向量共线（平行）。这个性质是判断点在线段哪一侧、线段是否相交的核心。
面积计算：取绝对值 $|\vec{a} \times \vec{b}|$ 即为平行四边形面积。三角形面积是其一半。

注意：叉积的“方向”定义依赖于坐标系是左手系还是右手系。在常见的屏幕坐标系（Y轴向下）和数学坐标系（Y轴向上）中，结论是相反的。绝大多数算法竞赛和图形学库默认使用数学坐标系（Y轴向上），此时叉积正负与“左转”、“右转”直观对应。编码时务必明确你所在的坐标系。

2.2 浮点数精度处理：一个无法回避的坑

几何计算大量使用浮点数（double），而浮点数的存储和运算存在固有的精度误差。直接使用==比较两个浮点数是否相等是极其危险的。我们必须引入一个极小的误差容忍值epsilon（通常取 $10^{-9}$ 或 $10^{-12}$）。

const double EPS = 1e-9; // 判断浮点数a和b是否“相等” bool eq(double a, double b) { return fabs(a - b) < EPS; } // 判断浮点数a是否大于b bool gt(double a, double b) { return a - b > EPS; } // 判断浮点数a是否小于b bool lt(double a, double b) { return a - b < -EPS; }

所有涉及浮点数比较的操作（判断是否为0、比较大小），都必须通过上述函数进行。例如，判断叉积是否为0（共线），应写为eq(cross(v1, v2), 0)。

3. 点、直线、线段的位置关系判定

有了向量的武器和精度处理的护甲，我们现在可以系统地解决各类位置关系问题。我们将从简单到复杂，逐一拆解。

3.1 点与点的关系

最基本的关系就是重合。判断两点 $P$ 和 $Q$ 是否重合，就是判断其坐标差是否在误差范围内。

struct Point { double x, y; Point(double x=0, double y=0): x(x), y(y) {} }; bool point_eq(Point p, Point q) { return eq(p.x, q.x) && eq(p.y, q.y); }

3.2 点与直线的关系

直线可以用一般式 $Ax + By + C = 0$ 表示，也可以用点向式（一个点 $P$ 和一个方向向量 $\vec{v}$）表示。后者在计算几何中更常用。判断点 $Q$ 到直线的距离，可以利用叉积。距离 $d = \frac{|\vec{PQ} \times \vec{v}|}{|\vec{v}|}$。如果 $d < EPS$，则可以认为点在直线上。更常见的是判断点在直线的哪一侧（适用于射线、线段判断的前置条件）。对于直线 $PQ$，判断点 $R$ 的位置：

double cross = (Q.x - P.x) * (R.y - P.y) - (Q.y - P.y) * (R.x - P.x); // 向量PQ与PR的叉积 if (eq(cross, 0)) { // 点R在直线PQ上（共线） } else if (cross > 0) { // 点R在直线PQ的左侧（假设坐标系Y轴向上） } else { // 点R在直线PQ的右侧 }

3.3 点与线段的关系

这是比点与直线关系更常见也稍复杂的问题。判断点 $R$ 是否在线段 $PQ$ 上，需要满足两个条件：

共线：点 $R$ 与线段 $PQ$ 共线，即 $\vec{PR} \times \vec{PQ} = 0$。
在线段范围内：点 $R$ 在以 $P$ 和 $Q$ 为对角顶点的矩形框内。这可以通过比较坐标来实现，但更优雅的方式是利用点积。点 $R$ 在线段 $PQ$ 上当且仅当 $\vec{PR} \cdot \vec{PQ} \ge 0$ 且 $\vec{QR} \cdot \vec{QP} \ge 0$。其几何意义是，$R$ 在 $P$ 和 $Q$ 之间的充要条件是，$R$ 到 $P$ 的向量与 $P$ 到 $Q$ 的向量同向或为零，且 $R$ 到 $Q$ 的向量与 $Q$ 到 $P$ 的向量同向或为零。

bool on_segment(Point p, Point q, Point r) { // 判断点r是否在线段pq上 if (!eq(cross(p, q, r), 0)) return false; // 不共线 // 使用点积判断是否在端点之间 return le(dot(p, q, r, p), 0) && le(dot(q, p, r, q), 0); // 辅助函数：向量(p->q)与(p->r)的点积 // le 是 “小于等于” 的精度判断函数 }

3.4 线段与线段的关系

判断两条线段 $AB$ 和 $CD$ 是否相交，是计算几何的经典问题。一个健壮且高效的方法是跨立实验。核心思想是：如果线段 $AB$ 和 $CD$ 相交，那么点 $A$ 和点 $B$ 必须位于直线 $CD$ 的两侧，并且点 $C$ 和点 $D$ 必须位于直线 $AB$ 的两侧。用叉积表示“两侧”：判断点 $P$ 和点 $Q$ 是否在直线 $RS$ 的两侧，只需计算 $( \vec{RS} \times \vec{RP} ) * ( \vec{RS} \times \vec{RQ} ) < 0$。如果乘积为负，说明两点分居两侧；如果乘积为0，说明至少有一点在直线上。

因此，线段相交的完整判断逻辑为：

快速排斥实验（可选但高效）：如果两条线段的外接矩形（以端点坐标为边界）都不相交，那么线段肯定不相交。这是一个快速的预筛选。
跨立实验：检查 $A$、$B$ 是否在 $CD$ 两侧，且 $C$、$D$ 是否在 $AB$ 两侧。
处理边界情况：如果任意叉积为0，说明存在端点共线的情况。此时需要额外判断点是否在线段上（调用on_segment函数）。

bool segments_intersect(Point A, Point B, Point C, Point D) { 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); // 跨立实验 if (lt(c1 * c2, 0) && lt(c3 * c4, 0)) return true; // 处理边界情况：端点在线段上 if (eq(c1, 0) && on_segment(A, B, C)) return true; if (eq(c2, 0) && on_segment(A, B, D)) return true; if (eq(c3, 0) && on_segment(C, D, A)) return true; if (eq(c4, 0) && on_segment(C, D, B)) return true; return false; }

3.5 直线与直线的关系

两条直线的关系无非平行、重合或相交。

平行：方向向量的叉积为0。
重合：平行且直线上任意一点（如已知点）在另一条直线上。
相交：计算交点。设直线 $P_1 + t\vec{v_1}$ 和 $P_2 + s\vec{v_2}$，联立方程可解得参数 $t = \frac{\vec{P_2P_1} \times \vec{v_2}}{\vec{v_1} \times \vec{v_2}}$，然后代入第一条直线方程即可求得交点坐标。注意分母（两方向向量的叉积）为0时，两直线平行或重合。

4. 其它重要关系的计算与应用

除了判断位置，我们经常需要计算一些度量值。

4.1 距离计算

点到直线的距离：如前所述，$d = \frac{|\vec{PQ} \times \vec{v}|}{|\vec{v}|}$。
点到线段的距离：比到直线复杂。需要计算点到线段所在直线的距离，但还要判断垂足是否落在线段内。如果垂足在线段内，距离即点到直线的距离；否则，距离为点到两个端点距离的较小值。这可以通过点积来判断垂足位置。
线段到线段的距离：如果两线段相交，距离为0。否则，距离是以下四个距离的最小值：线段1两端点到线段2的距离，线段2两端点到线段1的距离。

4.2 投影与对称

点在直线上的投影点：即垂足。设直线为 $P + t\vec{v}$，点 $Q$ 到直线的投影参数 $t_0 = \frac{\vec{PQ} \cdot \vec{v}}{\vec{v} \cdot \vec{v}}$，投影点坐标为 $P + t_0 \vec{v}$。
点关于直线的对称点：先求投影点 $Q‘$，则对称点 $Q'' = Q + 2 * (Q' - Q)$。

4.3 多边形相关的基础

点、线、段的关系是构建更复杂几何算法（如多边形）的基础。

判断点是否在多边形内：常用射线法。从该点引一条水平向右的射线，统计其与多边形各边的交点数。如果交点数为奇数，点在多边形内；偶数，则在多边形外。需要特别注意射线穿过顶点、与边重合等边界情况。
多边形的面积：对于顶点按顺序排列的多边形，其面积可以通过所有相邻顶点与原点（或第一个顶点）构成的向量的叉积和来计算：$Area = \frac{1}{2} |\sum_{i=0}^{n-1} (P_i \times P_{i+1})|$。这是一个非常优雅且高效的公式。

5. 实战演练与代码模板

理论需要结合实践。下面提供一个包含上述核心功能的C++代码模板框架。这个模板经过了大量竞赛和工程实践的检验，注重健壮性和易用性。

#include <bits/stdc++.h> using namespace std; const double EPS = 1e-9; const double PI = acos(-1.0); // 精度比较函数 inline int dcmp(double x) { if (fabs(x) < EPS) return 0; return x < 0 ? -1 : 1; } // 点与向量类 (合一) struct Point { double x, y; Point(double x=0, double y=0): x(x), y(y) {} // 向量加法、减法、数乘 Point operator+(const Point& b) const { return Point(x+b.x, y+b.y); } Point operator-(const Point& b) const { return Point(x-b.x, y-b.y); } Point operator*(double k) const { return Point(x*k, y*k); } // 点积 double dot(const Point& b) const { return x*b.x + y*b.y; } // 叉积 double cross(const Point& b) const { return x*b.y - y*b.x; } // 长度平方 double len2() const { return this->dot(*this); } // 长度 double len() const { return sqrt(len2()); } // 单位化 Point normalize() const { double l = len(); return Point(x/l, y/l); } // 逆时针旋转90度 Point rotate90() const { return Point(-y, x); } // 判断两点是否相等（精度） bool operator==(const Point& b) const { return dcmp(x-b.x) == 0 && dcmp(y-b.y) == 0; } }; typedef Point Vector; // 直线类，使用点向式 struct Line { Point p; // 直线上一点 Vector v; // 方向向量 Line() {} Line(Point p, Vector v): p(p), v(v) {} // 由两点确定直线 Line(Point a, Point b): p(a), v(b-a) {} }; // 判断点p是否在线段ab上（含端点） bool onSegment(Point p, Point a, Point b) { // 先判断共线 if (dcmp((a-p).cross(b-p)) != 0) return false; // 再判断点积 return dcmp((a-p).dot(b-p)) <= 0; } // 判断线段a1a2与b1b2是否相交（含端点） bool segmentIntersect(Point a1, Point a2, Point b1, Point b2) { double c1 = (a2-a1).cross(b1-a1); double c2 = (a2-a1).cross(b2-a1); double c3 = (b2-b1).cross(a1-b1); double c4 = (b2-b1).cross(a2-b1); // 跨立实验 if (dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0) return true; // 处理端点情况 if (dcmp(c1) == 0 && onSegment(b1, a1, a2)) return true; if (dcmp(c2) == 0 && onSegment(b2, a1, a2)) return true; if (dcmp(c3) == 0 && onSegment(a1, b1, b2)) return true; if (dcmp(c4) == 0 && onSegment(a2, b1, b2)) return true; return false; } // 计算直线交点，需确保直线不平行 Point lineIntersection(Line l1, Line l2) { Vector u = l1.p - l2.p; double t = (l2.v.cross(u)) / (l1.v.cross(l2.v)); return l1.p + l1.v * t; } // 点到直线的距离 double distancePointToLine(Point p, Line l) { return fabs((p - l.p).cross(l.v)) / l.v.len(); } // 点到线段的距离 double distancePointToSegment(Point p, Point a, Point b) { if (a == b) return (p - a).len(); // 线段退化为点 Vector v1 = b - a, v2 = p - a, v3 = p - b; if (dcmp(v1.dot(v2)) < 0) return v2.len(); // 垂足在a点外侧 if (dcmp(v1.dot(v3)) > 0) return v3.len(); // 垂足在b点外侧 return distancePointToLine(p, Line(a, b)); // 垂足在线段上 } // 判断点是否在多边形内（射线法），多边形点集pts按顺序给出 int pointInPolygon(Point p, const vector<Point>& pts) { int wn = 0; // winding number int n = pts.size(); for (int i = 0; i < n; ++i) { int j = (i+1) % n; if (onSegment(p, pts[i], pts[j])) return 0; // 在边界上 int k = dcmp((pts[j] - pts[i]).cross(p - pts[i])); int d1 = dcmp(pts[i].y - p.y); int d2 = dcmp(pts[j].y - p.y); if (k > 0 && d1 <= 0 && d2 > 0) wn++; // 向上穿过 if (k < 0 && d2 <= 0 && d1 > 0) wn--; // 向下穿过 } return wn == 0 ? -1 : 1; // -1: 外部， 1: 内部 } // 计算多边形有向面积（点集按逆时针顺序） double polygonArea(const vector<Point>& pts) { double area = 0; int n = pts.size(); for (int i = 0; i < n; ++i) { int j = (i+1) % n; area += pts[i].cross(pts[j]); } return fabs(area) / 2.0; }

6. 常见陷阱、调试技巧与性能优化

即使理解了原理，实现时仍会踩坑。下面分享一些血泪教训。

6.1 浮点数精度：不仅仅是EPS

EPS的选择：$10^{-9}$ 对于大多数情况足够。但如果坐标值或运算中间结果非常大（如超过 $10^6$），可能需要适当调大EPS。反之，如果要求极高精度，可能需要 $10^{-12}$ 甚至更高。一个经验法则是，EPS可以取为 $10^{-(有效位数+2)}$。
避免直接比较：永远不要写if (a == b)，要写if (dcmp(a-b) == 0)。不要写if (a > b)，要写if (dcmp(a-b) > 0)。
平方与开方：比较距离时，优先比较距离的平方，避免不必要的sqrt调用，既能提高性能，也能减少精度损失。例如，判断两点距离是否小于R，应比较(p-q).len2() < R*R + EPS。
误差累积：在复杂的几何构造中（如多次求交点再计算），误差会累积。对于关键判断，有时需要更高的精度（如使用long double）或采用有理数/整数计算（如果输入是整数且只涉及线性运算）。

6.2 特殊情况的处理

共线点：这是许多算法的“杀手”。在判断线段相交、点在线段上、求凸包时，必须仔细处理三点共线的情况。你的代码应该明确定义共线时的行为（例如，在凸包算法中，是保留离原点更远的点还是更近的点？）。
退化图形：线段退化为点，多边形退化为线段或点。你的函数是否能正确处理？例如，distancePointToSegment中就需要判断线段两端点是否重合。
平行与重合：判断直线相交时，必须先检查方向向量是否平行（叉积为0）。如果平行，再判断是否重合（检查一点是否在另一直线上）。

6.3 调试技巧

可视化：这是最有效的调试手段。将你的点、线、多边形画出来。可以用简单的图形库（如Python的matplotlib），甚至直接输出到文本文件，用绘图软件查看。肉眼能立刻发现很多逻辑错误。
小数据测试：构造一些边界情况的小例子手动计算，与程序输出对比。例如：两条线段端点重合、线段完全重叠、点在延长线上等。
对拍：写一个暴力但正确的算法（例如，对于点是否在多边形内，可以用极其简单的角度和法），与你的高效算法在随机生成的数据上对比结果。

6.4 性能优化考量

对于算法竞赛或处理大规模点云数据，性能很重要。

避免浮点除法和开方：如前所述，用平方比较代替距离比较。
使用整数坐标：如果问题允许（输入坐标是整数，且只涉及加减乘和叉积点积），尽量使用整数（long long）进行计算，可以彻底避免精度问题，且速度更快。
空间索引：当需要处理海量点与线段的关系查询时（如判断成千上万个点是否在一个多边形内），朴素算法是O(n)每次查询。可以考虑使用空间索引结构加速，如网格索引、四叉树、R树等，将查询复杂度降至接近O(log n)。

7. 从基础到应用：场景延伸

掌握了这些基础，你可以解锁众多应用场景：

计算机图形学：碰撞检测（线段/射线与三角形网格求交）、裁剪（如Cohen-Sutherland线段裁剪算法）、光栅化（判断像素中心是否在三角形内）。
地理信息系统：点是否在行政区域内（多边形包含判断）、道路（线段）是否相交、计算地理围栏。
游戏开发：视线判断（从A点到B点是否有障碍物，可转化为线段与障碍物多边形的相交测试）、攻击范围判定、运动轨迹预测。
机器人学：路径规划中的障碍物避让（需要计算机器人与障碍物的最近距离）、SLAM中的特征点匹配与位姿估算。
算法竞赛：这是计算几何题目的直接来源，涉及凸包、旋转卡壳、半平面交、最近点对等更高级的算法，但无一不是建立在点、线、段的基本操作之上。

我个人在开发和竞赛中最大的体会是，计算几何的代码要像数学公式一样严谨，对边界情况的处理必须滴水不漏。最初我写的线段相交函数没有处理好端点共线的情况，导致在一个地图渲染项目中，边界道路在拐角处偶尔会出现断裂，排查了整整一天才找到这个bug。从那以后，我养成了为每一个几何函数编写单元测试的习惯，专门测试共线、退化、精度临界这些边缘案例。把基础打牢，后续构建复杂的几何算法时才会稳如磐石。当你能够熟练运用向量叉积判断左右、用点积判断投影，你会发现许多看似复杂的空间问题，其内核都变得清晰而简单。