1. 从“距离”说起一个看似简单却无处不在的几何概念在编程、游戏开发、图形处理乃至机器人路径规划中我们经常需要回答一些关于“远近”的问题。比如一个游戏角色离宝藏还有多远一个鼠标点击是否选中了屏幕上的一条线段一个自动驾驶的车辆如何判断与前方障碍物的距离以避免碰撞这些问题的背后都离不开几个基础但至关重要的几何计算两点间距离、点到直线距离、点到线段距离以及线段到线段距离。很多人第一次接触这些公式可能是在中学的数学课本上觉得无非就是套公式计算。但真正在代码里实现时你会发现坑一个接一个浮点数精度误差怎么处理点在直线延长线上怎么办两条线段平行或重合时距离怎么定义这些“边界情况”才是区分代码是否健壮、算法是否可靠的关键。今天我们就抛开纯数学推导从一个实践者的角度把这四种距离的计算方法、适用场景、代码实现中的坑以及如何优雅地处理各种特殊情况一次性讲清楚。无论你是正在学习图形学的学生还是需要解决实际几何问题的开发者这篇文章都能给你提供可以直接“抄作业”的解决方案和避坑指南。2. 基石两点间距离公式及其实现陷阱两点间距离计算是所有距离问题的基础公式distance sqrt((x2-x1)^2 (y2-y1)^2)几乎人人皆知。但在计算机中实现它远不止写一行代码那么简单。2.1 公式的直观理解与选择我们熟知的欧几里得距离公式来源于勾股定理。在二维平面中它衡量的是两点之间的“直线”长度是最符合我们直觉的距离定义。然而在特定场景下程序员可能会使用其他距离度量比如曼哈顿距离|x2-x1| |y2-y1|或切比雪夫距离max(|x2-x1|, |y2-y1|)。曼哈顿距离模拟了在网格状道路如城市街区上行走的路径长度在寻路算法中很常见切比雪夫距离则适用于国王在国际象棋棋盘上的移动。对于绝大多数需要几何真实感的场景如物理引擎、图形渲染、空间查询欧几里得距离是唯一正确的选择。因为它具有旋转不变性——无论坐标系如何旋转两点间的距离保持不变这是其他度量不具备的关键性质。2.2 浮点数精度与数值稳定性直接套用公式实现一个典型的C代码可能如下#include cmath struct Point { double x, y; }; double distanceBetweenPoints(const Point a, const Point b) { double dx b.x - a.x; double dy b.y - a.y; return std::sqrt(dx*dx dy*dy); }这段代码在大多数情况下工作良好但存在两个潜在的数值问题。第一开方运算std::sqrt是相对昂贵的操作。在需要频繁计算距离且不需要精确距离值只需要比较远近时例如寻找最近的点一个常见的优化是计算距离的平方进行比较避免开方。将上面的函数改为返回dx*dx dy*dy可以显著提升性能。第二更隐蔽的问题是数值下溢。当dx和dy非常小时例如接近1e-154的双精度数它们的平方可能低于双精度浮点数能表示的最小正规数导致下溢为0。虽然这种情况罕见但在高可靠性要求的系统中需要考虑。一个更稳健的写法是使用std::hypot函数double distanceBetweenPointsRobust(const Point a, const Point b) { return std::hypot(b.x - a.x, b.y - a.y); }std::hypot函数在计算平方和开方时会采用一些数值方法避免中间结果的溢出或下溢是更专业的选择。2.3 距离计算在空间索引中的应用在实际项目中单纯计算两个点的距离往往不够。更常见的需求是“给定一个点P从10万个点中找出离它最近的5个”。暴力计算所有距离的复杂度是O(N)不可接受。这时就需要引入空间索引结构如四叉树、KD树或网格索引。以KD树为例其构建和查询过程本身就频繁依赖两点间距离的计算。在查询时我们不仅需要计算点到目标点的距离还需要计算点到某个“分割超平面”的距离这本质上是点到一条无限延伸的直线的距离我们下一节会讲以决定搜索剪枝的方向。因此一个高效且正确的距离计算函数是构建高性能空间查询系统的基石。我曾在一个地理信息系统中将基于暴力搜索的最近邻查询改用KD树实现查询速度提升了数百倍而其中距离比较函数的正确性和效率至关重要。3. 点到直线距离理解“垂直”的几何意义点到直线的距离定义为该点到直线上任意一点距离的最小值而这个最小值恰好出现在连接该点与直线的线段垂直于直线时。这是理解许多高级算法如线性回归、支持向量机的几何基础。3.1 直线的一般式与距离公式给定直线L的一般式方程Ax By C 0和点P(x0, y0)则点P到直线L的距离公式为d |A*x0 B*y0 C| / sqrt(A^2 B^2)这个公式非常简洁但它的推导和理解是关键。分母sqrt(A^2 B^2)实际上是向量(A, B)的模长这个向量是直线的法向量与直线垂直。分子|A*x0 B*y0 C|的绝对值几何意义是点P代入直线方程后的“代数值”的绝对值。这个“代数值”的正负可以判断点位于直线的哪一侧。在实现时一个常见的错误是忘记对A和B进行归一化即除以模长或直接使用错误的系数。例如如果你从直线上的两个点(x1, y1)和(x2, y2)推导一般式需要先计算A y2 - y1,B x1 - x2注意顺序然后C -A*x1 - B*y1。验证公式正确性的一个好方法是将直线上的两个点代入公式结果应该为0。3.2 从两点式推导与代码实现更多时候我们手头有的是直线上的两个点P1(x1, y1)和P2(x2, y2)而不是一般式系数。我们可以直接推导出距离公式避免中间转换的精度损失。向量P1P2 (x2-x1, y2-y1)是直线的方向向量。点P到直线L的距离等于向量P1P即(x0-x1, y0-y1)与方向向量P1P2的叉积的绝对值除以方向向量的模长。 在二维中叉积的模|(P1P) × (P1P2)| |(x0-x1)*(y2-y1) - (y0-y1)*(x2-x1)|。 方向向量的模长就是sqrt((x2-x1)^2 (y2-y1)^2)。因此公式为d |(x0-x1)*(y2-y1) - (y0-y1)*(x2-x1)| / sqrt((x2-x1)^2 (y2-y1)^2)这个形式在几何上非常直观分子是向量P1P和P1P2张成的平行四边形的面积绝对值分母是底边P1P2的长度。面积除以底边得到的就是高也就是点到直线的距离。代码实现如下double distancePointToLine(const Point p, const Point lineStart, const Point lineEnd) { double lineLengthSquared (lineEnd.x - lineStart.x)*(lineEnd.x - lineStart.x) (lineEnd.y - lineStart.y)*(lineEnd.y - lineStart.y); // 处理直线退化为点的情况 if (lineLengthSquared 1e-12) { // 使用一个极小的阈值 return distanceBetweenPoints(p, lineStart); } // 计算叉积的绝对值 double crossProduct std::abs((p.x - lineStart.x)*(lineEnd.y - lineStart.y) - (p.y - lineStart.y)*(lineEnd.x - lineStart.x)); return crossProduct / std::sqrt(lineLengthSquared); }注意我们首先计算了线段长度的平方并检查它是否接近零。这是至关重要的边界情况处理如果线段的两个端点重合那么“直线”其实是一个点此时点到直线的距离应退化为两点间距离。如果不做这个检查除数可能为零导致除零错误或得到无意义的NaN/Inf值。这里的1e-12是一个根据应用场景选择的阈值用于判断浮点数是否“足够接近”零。4. 点到线段距离从无限直线到有限段落的约束点到直线的距离假设直线是无限延伸的。但在现实中我们遇到的更多是“线段”——有起点和终点的有限部分。点到线段的距离定义是点到线段上任意一点距离的最小值。这个最小值可能出现在线段的内部也可能在线段的某个端点上。4.1 核心算法投影点参数化计算点到线段距离的核心思路是先找到点在线段所在直线上的投影点然后判断这个投影点是否落在线段的区间内。参数化线段将线段S端点A, B表示为A t * (B - A)其中t是参数。当t0时对应点At1时对应点Bt在[0, 1]之间时对应线段AB上的点。计算投影参数对于点P计算向量AP在向量AB上的投影长度点积与AB长度的平方的比值这个比值就是投影点对应的参数t。t dot(AP, AB) / dot(AB, AB)其中dot表示向量点积。钳制参数如果t 0说明投影点位于A点之外更靠近A此时最近点就是A距离为|PA|。如果t 1说明投影点位于B点之外更靠近B最近点是B距离为|PB|。如果0 t 1则投影点在线段上最近点就是投影点距离可用上一节点到直线的公式计算也可以用|AP| * sinθ计算θ为AP与AB的夹角。计算距离根据钳制后的t值计算最近点坐标然后求该点与P的欧氏距离。4.2 代码实现与细节剖析以下是完整的实现代码包含了所有边界情况的处理double distancePointToSegment(const Point p, const Point segStart, const Point segEnd) { Point ab {segEnd.x - segStart.x, segEnd.y - segStart.y}; Point ap {p.x - segStart.x, p.y - segStart.y}; double abLengthSquared ab.x*ab.x ab.y*ab.y; // 情况1线段退化为点 if (abLengthSquared 1e-12) { return std::hypot(ap.x, ap.y); // 退化为两点距离 } // 计算投影参数 t (AP · AB) / |AB|^2 double t (ap.x * ab.x ap.y * ab.y) / abLengthSquared; // 钳制 t 到区间 [0, 1] if (t 0.0) { // 情况2投影点在A的左侧最近点为A return std::hypot(ap.x, ap.y); } else if (t 1.0) { // 情况3投影点在B的右侧最近点为B Point bp {p.x - segEnd.x, p.y - segEnd.y}; return std::hypot(bp.x, bp.y); } else { // 情况4投影点在线段AB内部 // 计算投影点坐标 Point projection { segStart.x t * ab.x, segStart.y t * ab.y }; // 返回P到投影点的距离 return std::hypot(p.x - projection.x, p.y - projection.y); } }这个实现清晰地将四种情况分开处理。在实际调试中我曾因为忘记处理“线段退化为点”的情况导致在某些极端输入数据下程序崩溃。另一个容易忽略的细节是当t非常接近0或1时比如t 1e-15或t 1 - 1e-15由于浮点数精度直接判断t 0或t 1可能不可靠。但在大多数应用中直接比较是可行的。如果对鲁棒性要求极高可以考虑使用一个微小的容差例如判断t -1e-12或t 1 1e-12。4.3 应用场景碰撞检测与交互点到线段距离算法是许多交互功能的基础。例如在图形编辑器中判断鼠标是否点击选中了一条线段可以将鼠标点击点与线段距离与一个视觉阈值如5个像素进行比较。在游戏开发中它可以用于简单的碰撞检测比如判断一个球体近似为点是否与一段墙壁线段发生碰撞。在路径规划中它可以计算智能体当前位置与预定路径由一系列线段组成的偏离距离。5. 线段到线段距离几何问题复杂度的跃升两条线段之间的距离定义为两条线段上任意两点之间距离的最小值。这个问题比前三种都要复杂因为最近点对可能出现在端点-端点、端点-线段内部、线段内部-线段内部等多种组合上。5.1 问题分析与算法思路计算两条线段S1(A1B1)和S2(A2B2)间距离的暴力方法是枚举所有可能性计算四个端点分别到另一条线段的距离然后取最小值。即min( dist(A1, S2), dist(B1, S2), dist(A2, S1), dist(B2, S1) )其中dist(P, S)是上一节实现的点到线段距离函数。这个方法是正确的吗在大多数情况下是但存在一个反例。当两条线段在空间中交叉但不相交时在三维空间中常见二维中两条不平行线段必然相交于一点或不相交最近点可能同时位于两条线段的内部而不是任何端点。此时暴力枚举端点会得到一个偏大的距离值。因此一个完备的算法必须额外检查一种情况两条线段所在直线的最近点即公垂线与两条直线的交点是否同时落在线段内部。在二维空间中如果两条线段不平行它们所在的直线总会相交。所以在二维中两条线段间距离的最小值要么出现在端点-线段上要么出现在端点-端点上。对于二维空间暴力枚举四个端点到另一条线段的距离然后取最小值这个算法是完备且正确的。注意这是二维空间的一个重要简化。在三维空间中情况要复杂得多必须考虑线段内部-内部的情况通常需要用到更复杂的基于参数化求最小值的算法。5.2 二维空间中的实现与优化基于以上分析二维空间线段距距离的算法可以高效实现double distanceSegmentToSegment2D(const Point a1, const Point b1, const Point a2, const Point b2) { // 计算四种端点-线段距离 double d1 distancePointToSegment(a1, a2, b2); double d2 distancePointToSegment(b1, a2, b2); double d3 distancePointToSegment(a2, a1, b1); double d4 distancePointToSegment(b2, a1, b1); // 返回最小值 return std::min({d1, d2, d3, d4}); }这个实现直接复用了之前写好的distancePointToSegment函数清晰且不易出错。性能上它计算了4次点到线段距离每次计算包含若干次乘加、比较和一次开方在最近点为端点时。如果非常关注性能可以尝试在distancePointToSegment内部返回距离平方最后再统一开方减少开方次数。但现代CPU上这种优化收益可能不大代码清晰度更重要。5.3 相交线段的特殊处理上面的算法对于不相交的线段给出了距离。但如果两条线段相交呢按照定义两条相交线段的距离应该是0。我们的distancePointToSegment函数能处理这种情况吗答案是部分能。考虑两条线段相交于点P。那么P必然同时位于两条线段上。当我们计算dist(A1, S2)时如果A1不是交点P那么距离大于0。但是当我们计算dist(P, S2)时因为P在线段S2上距离为0。然而我们的算法只枚举了四个端点没有枚举交点P。所以如果交点P不是任何一条线段的端点我们的算法将无法得到0距离。因此一个工业级的实现在计算线段距离前应该先进行线段相交性检测。如果检测到两条线段相交包括端点处相交则直接返回0。相交检测本身是一个经典问题可以通过计算向量叉积进行快速排斥和跨立实验来完成这里不展开。增加相交检测后算法的鲁棒性会大大增强。5.4 从二维到三维的挑战正如之前提到的三维空间中的线段距距离问题才是真正的挑战。因为两条异面直线线段所在的直线不相交其最近点位于两条线段内部的可能性大大增加。此时暴力枚举端点法失效。三维空间的通用算法通常基于以下思路将两条线段分别参数化P(s) A1 s*(B1-A1)和Q(t) A2 t*(B2-A2)其中s, t ∈ [0,1]。距离函数D(s,t) |P(s) - Q(t)|^2是一个关于s和t的二次函数。我们需要在单位正方形[0,1]×[0,1]上寻找这个函数的最小值。这可以通过分析梯度、检查边界s0, s1, t0, t1和可能的内部驻点如果两条线段所在直线不平行来实现。著名的“几何工具”库Geometric Tools中有非常高效且稳健的实现。在三维项目中遇到此问题时强烈建议直接使用经过充分测试的库而不是自己从头实现因为其中涉及大量的数值稳定性处理。
