-
YAML 元数据 已设置 tags: [KACTL, 几何, 核心实体]。
-
核心概述 给定逆时针且无共线点的凸多边形，二分在 O(log n) 内判定并返回一条直线与其的相交类型与对应边索引。
-
原文引述
Line-convex polygon intersection. The polygon must be ccw and have no collinear points. lineHull(line, poly) returns a pair describing the intersection of a line with the polygon: Time: O(\log n)
- 展开阐述
-
定义与背景
- 问题：输入直线 ab 与凸多边形 poly（顶点逆时针、相邻边不共线），输出与凸包的相交情形。
- 典型场景：裁剪/可见性分析、路径与障碍的快速碰撞检测、与旋转卡壳/半平面交等模块组合做几何查询加速。
- 能力边界：仅适用于凸多边形且顶点 ccw、无边共线的前提；自交或含共线顶点的输入不在定义域内。
-
接口/字段说明（据实现）
- extrVertex(poly, dir)：在凸包上按方向向量 dir 的投影最大化点的索引（支持循环二分）。
- lineHull(a, b, poly)：返回 array<int,2> 索引对，描述交的“所在边”（以 (i,i+1) 表示），或特殊记号 (-1,-1)/(i,-1)/(i,i) 等。
- 返回语义：
- (-1, -1)：无交点（直线在凸包外且不相切）
- (i, -1)：直线仅接触顶点 i（切于顶点）
- (i, i)：直线与边 (i, i+1) 重合（沿边）
- (i, j)：直线穿过两条边 (i, i+1) 与 (j, j+1)，按从 a→b 的次序返回
- 多边形顶点索引按 0..n-1，边 (i, i+1) 的后一端取模 n。
-
核心流程/要点（极值顶点 + 二分）
- 方向极值：以 dir = (b−a).perp() 或与直线法向一致的方向，调用 extrVertex 定位两侧极值端点（endA/endB），用于快速判断“是否可能相交”。
- 粗判外离：若直线在两个极值端点投影上均处于同一侧，则可判为 (-1,-1)。
- 两次二分：在极值端点分割开的两段单调区间内，分别对“有向距离符号变化”的边索引做二分，定位入点与出点所处边。
- 特判顶点/沿边：若穿越恰在顶点处，约定落在哪条边由实现定义（通常计入 (i,i+1)）；若整段共线则返回 (i,i) 表示沿边。
-
复杂度与边界条件
- 时间：O(log n)
- 输入要求：poly 必须 ccw 且无 collinear points；否则极值与单调性不成立，二分失效。
- 数值稳健：距离/叉积的符号判定建议搭配 eps；顶点接触时需稳定地落入“触及顶点 i”的分支。
- 退化情形：
- 与凸包无交：(-1,-1)
- 切于顶点：返回 (i,-1)
- 沿边：返回 (i,i)
-
变体与扩展
- 线段与凸包交：在得到直线与凸包交的索引对后，再将交点按参数 t 与线段范围 [0,1] 裁剪；或直接改写为线段-多边形交。
- 射线与凸包交：仅取参数 t≥0 的部分；可用于“可见性/光线投射”。
- 多边形（非凸）版本：需改用扫描/射线计数或分段裁剪，复杂度增大且需处理自交。
- 支持共线点：需改写极值与判定逻辑，明确共线归属与去重策略。
-
正确性要点与不变式
- 凸性保证在任一方向上顶点投影为“单峰/双调”，从而可二分定位符号变化边界；
- 交点必发生在两条边上，或退化为顶点/沿边。
- 方向约定一致：以 a→b 决定交点输出顺序，保持与几何直觉一致。
-
与相邻技术的对比和取舍建议
- 与 025-几何-凸包：若输入为散点，先构造凸包；此处假设凸包已给定。
- 与 034-几何-直线相交：在得到两个“所在边”后，可与边直线进行精确交点计算。
- 与 039-几何-点：点与向量的基础操作（dot、cross、dist2）是本方法的基石。
-
工程实践注意
- 数据预处理：确保 poly 为 ccw 且去除共线中间点（如凸包构造中采用严格 <0 规则）。
- 索引取模：所有边 (i, i+1) 需对 n 取模，避免越界。
- eps 策略：对 cross 与投影比较使用统一阈值，稳定触点与沿边的分支。
- 关联节点