-
YAML 元数据 已设置 tags: [KACTL, 几何, 核心实体]。
-
核心概述 给定直线 ab 与点 p，返回点到该直线的距离：二维为带符号距离（从 a 指向 b 观察左正右负），三维为无符号距离。
-
原文引述
Returns the signed distance between point p and the line containing points a and b. Positive value on left side and negative on right as seen from a towards b. a==b gives nan. Using Point3D will always give a non-negative distance. For Point3D, call .dist on the result of the cross product.
- 展开阐述
-
定义与背景
- 距离语义：
- 二维：直线由有向对 (a,b) 确定，dist(a,b,p) = cross(b−a, p−a)/|b−a|。符号表示 p 在有向直线左/右侧。
- 三维：直线仍由 (a,b) 确定，距离为 |(p−a) × (b−a)| / |b−a|，恒非负。
- 典型适用场景：点到直线/射线/线段的几何关系判定、带符号半平面判定（如半平面交、凸包旋转卡壳的方向测试）、最近距离计算与投影/反射的前置量。
- 距离语义：
-
接口/字段说明（据实现约定）
- 函数签名：template
double lineDist(const P& a, const P& b, const P& p) - 类型约束：
- P 可为 Point
（二维）或 Point3D （三维），T 常用 double/long long。
- P 可为 Point
- 几何量：
- 向量 v = b−a，w = p−a；二维 cross(v, w) 为标量，三维 cross(v, w) 为向量，三维需再取 .dist()（模长）。
- 返回值：
- 二维：带符号实数，单位与坐标同维度；
- 三维：非负实数。
- 函数签名：template
-
核心流程/要点
- 方向设定：以 a→b 为正向，后续符号以此为基准。
- 归一化：用 |b−a| 做分母，保证几何尺度正确。
- 二维实现：d = cross(b−a, p−a) / |b−a|；cross>0 表示 p 在左侧，<0 在右侧，=0 共线。
- 三维实现：d = |(p−a) × (b−a)| / |b−a|；注意 cross 的结果是向量，需取模长。
- 特例处理：若 a==b（退化“直线”），距离未定义，返回 NaN（文件注释已声明）。
-
复杂度与边界条件
- 复杂度：O(1)
- 退化：
- a==b：分母为 0，不定义（NaN）；调用侧应在建模阶段避免。
- 极小 |b−a|：数值不稳定，需 eps 判定。
- 数值与溢出：
- 若使用整型（如 ll），中间乘法（叉积、模长平方）可能溢出；建议使用 long double 或内置 128 位整数护航。
- 对 double：较大坐标会带来舍入误差；与判定阈值 eps 配合使用。
-
变体与扩展
- 点到射线/线段距离：在投影参数 t = dot(p−a, b−a)/|b−a|² 的基础上裁剪 t 到 [0, +∞) 或 [0,1]，见 047-几何-线段间距离 与 048-几何-线段相交 的相关技巧。
- 半平面与有向面积：二维 cross 的符号与有向面积一致，可直接用于“点在直线哪侧”的判定（见 049-几何-点在直线哪侧）。
- 与投影/反射联用：先通过带符号距离得到偏移量，再配合法向/切向构造投影与反射（见 035-几何-线的投影与反射）。
-
正确性要点与不变式
- 二维：cross(b−a, p−a) = |b−a|·|p−a|·sinθ，其几何意义是以底 |b−a| 的有向高，因此 d = 有向面积/底边长度。
- 三维：到直线距离等于平行四边形面积 |(p−a)×(b−a)| 除以底边 |b−a|，与向量几何公式一致。
- 方向不变式：改变 (a,b) 的顺序会反转二维距离符号，但三维距离保持不变（取模后）。
-
与相邻技术的对比和取舍
- 034-几何-直线相交：线线关系判定常用叉积与方向测试；点线距离提供量化度量与后续投影的尺度。
- 035-几何-线的投影与反射：以 lineDist 的分子/分母为基础，直接构造投影/反射点坐标，避免重复计算。
- 039-几何-点：作为基础几何实体的向量运算集合，建议统一封装 cross/dot/dist2 等。
-
工程实践注意
- 阈值策略：比较“是否在直线上/左侧/右侧”时，使用 eps（如 1e−9）对 cross 与距离做近零判断。
- 单位一致：确保输入坐标单位一致，避免混合尺度造成距离解释偏差。
- 批量计算：在大量调用场景缓存 |b−a| 与其倒数，可显著降低开销。
- 关联节点