049-几何-点在直线哪侧

判定点 p 相对于有向直线 s→e 的侧别：返回 1/0/-1 分别表示左侧/在线上/右侧，支持带 eps 的浮点容差版本。

Returns where $p$ is as seen from $s$ towards $e$. 1/0/-1 $\iff$ left/on line/right. If the optional argument $eps$ is given 0 is returned if $p$ is within distance $eps$ from the line.

展开阐述

• 定义与背景

  • 有向直线与侧别：以 s→e 定义方向，利用有向面积（叉积）符号判断点 p 在其左/右侧或共线。
  • 应用场景：半平面裁剪与判定、凸包与旋转卡壳方向测试、线段相交“跨立实验”、多边形方向一致性校验等。
  • 数据类型：P 通常为 Point（见 039-几何-点），T 可为 double/long long；整型零误差但注意乘法溢出，浮点需 eps。

• 接口/数据结构（据实现）

  • 基础版：int sideOf(P s, P e, P p) —— 返回 1/0/-1
  • 带容差：int sideOf(const P& s, const P& e, const P& p, double eps)
  • 几何量：
    • a = (e−s).cross(p−s) 为 s-e-p 的有向面积（底边 |e−s|），与 032-几何-点线距离 的分子一致
    • 对带容差版，再计算 l = |e−s|·eps 作为“近线”阈值

• 核心流程/要点（方向测试 + 容差带）

  1. 方向与符号
     • 基础版直接返回 sgn(a)；a>0 视为左侧，<0 右侧，=0 共线
  2. 容差策略
     • 带 eps 时在区间 [−l, +l] 内视为在线上，返回 0；超出区间再比较正负
  3. 方向一致性
     • s,e 交换将反转符号；需在全局保持一致的“左正右负”约定，便于与 044-几何-多边形切割 等模块协同
  4. 与线性代数关系
     • 二维叉积等价于有向面积；a/|e−s| 即带符号的点线距离（见 032-几何-点线距离）

• 复杂度与边界条件

  • 时间复杂度：O(1)
  • 边界：
    • s==e：直线未定义，应在上游规避
    • 共线：基础版返回 0；带 eps 版在“近线带”内亦返回 0
  • 数值与溢出：
    • 整数几何：叉积/点积可能溢出 64 位，必要时用内建 128 位中间量
    • 浮点几何：统一 eps；l = |e−s|·eps 随尺度变化，避免远距离上过严的阈值

• 变体/扩展

  • 半平面包含：以 sideOf≥0 或 ≤0 定义“保留侧”，即 044-几何-多边形切割 的保留规则
  • 多点批量：预先缓存方向向量 v=e−s 及其长度，批量查询时可降常数
  • 三维推广：可转化为点到有向平面的侧别（以法向点积符号判断）

• 正确性要点与不变式

  • 叉积符号与“左正右负”约定必须与全局保持一致
  • 带 eps 的零带必须随 |e−s| 伸缩，以维持几何量纲一致性
  • 对 collinear 情况，结果与 038-几何-点在线段上 的距离阈值应一致，避免边界冲突

• 与相邻技术的对比与取舍

  • 032-几何-点线距离：提供带符号/无符号量化距离；本函数只返回三值判定，常作前置过滤
  • 034-几何-直线相交 与 048-几何-线段相交：均以方向测试为基础再做参数/区间裁剪
  • 041-几何-点在凸包内：二分/旋转卡壳依赖稳定的侧别判定

关联节点

• 039-几何-点
• 032-几何-点线距离
• 038-几何-点在线段上
• 044-几何-多边形切割
• 034-几何-直线相交