数学大学
A. Introduction
计算几何 · 06. Point Location
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
A. Introduction
计算几何 · 06. Point Location
Where Am I
点定位问题：给定平面细分与查询点，回答「我在哪个面里」。
输入
平面细分结构 + 查询点坐标
输出
包含查询点的面（或边/顶点）
Assumptions For Clarity
为清晰起见的假设：查询点不在边上、细分是连通的。
不在边上
边界情形可先做局部检验
连通
非连通细分拆成多个子图分别处理
Input Size
输入规模：细分的边数 n 决定预处理与查询的复杂度量级。
规模 n
边数（近似等于顶点数 + 面数）
量级目标
查询 O(log n)、空间 O(n) 是理想目标
Performance Measurements
性能度量三件套：查询时间、预处理时间、存储空间。
查询
单次点定位的时间
预处理
建数据结构的一次性成本
空间
数据结构占用的存储
A Global View
全局视角：点定位是一切「先定位再操作」几何算法的前置组件。
前置组件
地图导航、CAD 拾取、游戏命中检测都靠它
目标结构
静态用最优结构，动态用适应性结构
本节要点
- ✓点定位：回答「我在哪个面」
- ✓三度量为纲：查询、预处理、空间
- ✓理想目标：O(log n) 查询、O(n) 空间
延伸主题：明确自己场景的度量优先级复习平面细分结构
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1点定位为什么是「前置组件」而不是独立问题？
参考答案绝大多数几何应用（地图拾取、网格插值、碰撞检测）都要先知道「查询点落在哪个单元」才能取出对应数据做后续计算。定位质量与速度直接决定上层算法的体验。
2「查询点恰在边上」的边界情形怎么处理？
参考答案三种约定：任选一侧、两侧都返回、或单独返回边本身。实现上在定位结构的比较中用严格/非严格不等式控制走左还是走右，最后加一个点在边上的显式检查即可。
3非连通细分为什么能「拆成子图」处理？
参考答案不同连通分量之间没有任何邻接关系，查询点只会落在其中一个分量里。对每个分量独立建定位结构，查询时依次尝试（或用外层索引跳到候选分量），正确性与单分量一致。