KACTL 算法笔记

041-几何-点在凸包内

6 min read

核心概述：给定按逆时针且无共线点的凸多边形，判定点是否在其内部（可选含/不含边界），支持 O(log n) 查询。

Determine whether a point t lies inside a convex hull (CCW order, with no collinear points). Returns true if point lies within the hull. If strict is true, points on the boundary aren’t included. Time: O(\log N) Status: stress-tested

展开阐述

  • 定义与背景
    • 问题对象：输入为凸多边形（凸包）顶点序列 l，要求严格 ccw 且相邻点不共线；查询点为 p。
    • 判定目标：判断 p 是否在凸包内部；strict 控制边界点是否计入内部。
    • 典型场景：大量点对同一凸包的包含查询；作为033-几何-直线与凸包交、路径碰撞、可见性等模块的基础判定。
  • 接口/数据结构（据实现）
    • 函数签名：bool inHull(const vector

      & l, P p, bool strict = true)，P 可为 Point/Point。

    • 语义：返回 p 是否位于 l 的内部；当 strict=false 时，边界与顶点也视为内部。
    • 先决条件：sz(l) ≥ 3 且 ccw 且无 collinear points（若存在共线中点，应在构造凸包时按 <0 规则去除，见025-几何-凸包）。
  • 核心流程/要点（O(log n) 二分定位 + 边界预判）
    1. 退化提前：若 sz(l) < 3，则退化为线段/点包含判定，调用 onSegment/等价逻辑（见038-几何-点在线段上）。
    2. 扇形包围粗判：用 sideOf(l[0], l[1], p) 与 sideOf(l[0], l.back(), p) 先排除位于扇形外侧的点；若落在外，则直接返回 false。
    3. 二分找扇区：在顶点区间 [1, n-1) 上对“与 l[0] 形成的三角扇”做二分，定位唯一使得 p 位于三角形 △(l[0], l[m], l[m+1]) 可能为内的 m。
    4. 边界判定：最终以 sgn(l[m].cross(l[m+1], p)) 与阈值 r = strict ? 1 : 0 比较，决定是否计入；若允许边界，等于 0 时也算内。
    5. 方向一致性：确保三角形顺序为 ccw；若二分得到的 (a,b) 与 l[0] 形成 cw，则交换以保持符号一致。
  • 复杂度与边界条件
    • 时间复杂度：二分查找 O(log n)；退化到线性判定为 O(n)。
    • 边界情形：
      • p 在顶点/边上：strict=false 返回 true；strict=true 返回 false。
      • l 含共线中间点：不满足前提，二分“单峰/双调”被破坏，结果未定义；应预处理去除。
      • 重复点或顺序非 ccw：需先规范化输入，否则符号判定不一致。
    • 数值与精度：
      • 整数几何：叉积/比较稳健，但注意 64 位溢出风险（可用内建 128 位过渡）。
      • 浮点几何：统一 eps 做零判，sideOf/sgn 使用近零阈值保持跨模块一致。
  • 变体/扩展
    • O(n) 线性扫描：当仅一次查询或 n 很小，可直接用029-几何-点在多边形内的射线法，减少预处理与实现复杂度。
    • 多点批量查询：预先构建凸包并维持 ccw 顺序后，可对多个 p 重复使用二分，摊薄常数开销。
    • 三分/极角：若维护极角有序，可按角度定位扇区；但与离散顶点索引二分相比收益有限。
  • 正确性要点与不变式
    • 凸性保证“以 l[0] 为扇心”的扇区序列单调可二分；任何内部点必落在某个相邻顶点扇区中。
    • 符号一致性：以 ccw 顺序定义的 cross 符号与“左侧为正”的 sideOf 约定一致。
    • 边界先行：在 strict=false 时，边界点通过 cross==0 被纳入，不影响扇区二分的正确性。
  • 与相邻技术的对比与取舍

关联节点

Graph View

Backlinks