-
YAML 元数据 已设置 tags: [KACTL, 几何, 核心实体]。
-
核心概述 判定点 p 是否落在闭线段 s–e 上：整数几何使用“叉积为 0 且点积非正”的充要条件；浮点几何以 segDist(s,e,p) 与 eps 比较更稳健。
-
原文引述
Returns true iff p lies on the line segment from s to e. Use \texttt{(segDist(s,e,p⇐epsilon)} instead when using Point
.
- 展开阐述
-
定义与背景
- on-segment 判定用于多边形点包含、线段相交、最近距离等模块的边界判断。其核心是“共线 + 投影在端点之间”的联合条件。
- 统一语义为“闭线段”：端点 s、e 计入“在线段上”。
-
接口/字段（据实现约定）
- 模板原型：template
bool onSegment(P s, P e, P p) - 返回值：p 是否在闭线段 s–e 上（true/false）。
- P 可为 Point
或 Point 等；整型/浮点的判定策略不同。
- 模板原型：template
-
判定公式与要点
- 共线性（collinear）
- 使用三点叉积：p.cross(s, e) == 0
- 等价于 cross(e−s, p−s) == 0
- 整数几何可直接判等；浮点几何应使用 |cross| ≤ eps·|e−s|·|p−s| 或其他相容阈值。
- 使用三点叉积：p.cross(s, e) == 0
- 投影落段（between-ness）
- 使用点积：(s−p).dot(e−p) ≤ 0
- 几何含义：p 与 s、e 的向量夹角为钝角或 90°，即 p 位于以 s、e 为端的闭区间内（含端点时为 0）。
- 等价形式：min(s.x,e.x) ≤ p.x ≤ max(s.x,e.x) 且 min(s.y,e.y) ≤ p.y ≤ max(s.y,e.y)，但点积法更简洁且与旋转/变换无关。
- 使用点积：(s−p).dot(e−p) ≤ 0
- 组合判定
- 返回 共线 && 投影落段。
- 退化情形
- 当 se（零长度线段）：on-segment 等价于 ps（或 |p−s| ≤ eps）。
- 共线性（collinear）
-
浮点与 eps 策略
- 共线判断：|cross(e−s, p−s)| ≤ eps·|e−s|
- 段内判断：可用投影参数 t = dot(p−s, e−s)/|e−s|²，并判 0−eps ≤ t ≤ 1+eps
- 更稳健方案：直接以 segDist(s,e,p) ≤ eps 判定（与文件注释一致）
-
复杂度与边界条件
- 时间复杂度：O(1)
- 边界：端点必定返回 true；严格开区间需求可将 ≤ 改为 < 并在端点处排除
- 溢出与精度：
- 整型：cross 与 dot 为“三坐标乘积/平方和”，可能溢出 64 位；建议使用内置 128 位或切换到 long double 比较
- 浮点：统一 eps，避免在不同模块中阈值不一致导致判定冲突
-
实现细节与常见坑
- 坐标为负与混合大小写无影响，公式坐标无符号约束
- 注意与“点在直线哪侧”函数的符号一致性，避免 left/right 的误用
- 若后续还需最近距离/交点，prefer 使用统一的几何原语（如 047-几何-线段间距离、034-几何-直线相交）
-
对比与取舍
- 射线法与点在多边形内：on-segment 通常先行处理边界点，再做奇偶统计（见 029-几何-点在多边形内）
- 线段相交：线段相交需结合两端点分别对对方线段做“不同侧或在段上”的判定（见 048-几何-线段相交）
- 关联节点