平面点定位问题 | Codeboy's Blog

模型

输入是平面图的直线细分：边只在共享端点相交，面由几何嵌入而非抽象图单独决定。预处理后，查询点 (q) 返回包含它的面。若 (q) 落在边或顶点上，本文返回所有相邻面；实现也可固定优先规则，但构建与查询必须采用同一约定。

地图行政区落点是典型实例。Point-in-polygon 只对一个多边形判断内外；point location 对共享边的全部面统一预处理。三角剖分、单调细分和一般细分可采用不同结构，复杂度不能只写一个“二分搜索”概括。

先把 subdivision 三角剖分，并包在一个固定外三角形内。每轮在当前平面图中选择一组互不相邻的低度顶点，删除它们，再把留下的多边形洞重新三角化。被删顶点互不相邻，使各重三角化区域不会互相干扰；低度则限制新旧三角形之间的覆盖数。

平面图总能找到线性数量的有界度顶点，再从中取常数比例的独立集，所以每轮删除常数比例顶点。层数因此为 (O(\log n))；各层规模形成几何级数，总三角形与跨层指针为 (O(n))。

每个粗层三角形记录与下一细层相交的常数个三角形。这个常数候选性质来自低度删除及局部重三角化，不是“递归层级”四个字自动带来的。

查询从最粗层唯一外三角形开始。假设当前三角形为 (\tau_i)，只测试它指向的细层候选，找到包含 (q) 的 (\tau_{i-1})，直到原始 subdivision。每层做常数次三角形包含测试，故查询时间为 (O(\log n))。

例如地图点先落在覆盖整个城区的粗三角形；下一层候选只来自该三角形覆盖的几个街区三角形；继续下降后定位到两条道路与河岸围成的原始面。查询不会在每层重新扫描整张地图，状态只有当前三角形及其候选表。

预处理接口应保存原三角形到 subdivision 面的映射，因为输入面可能被对角线拆成多个三角形。最后一步返回的是原面标识，而非任意一个内部三角形编号。

三角形包含测试由方向测试组成。查询点恰在行政边界时，(\operatorname{orientation}(a,b,q)=0) 必须进入专门分支：记录两侧候选并最终返回相邻面集合。若浮点把零误算为正，后续细层没有全局校验替它纠正。

实现可用精确整数谓词、自适应精度算术或一致的 symbolic perturbation。应同时报告构建时间、空间、查询时间和计算模型；“线性空间、对数查询”不表示任意退化坐标在普通浮点上都安全。

若删除集不是独立，两个重三角化洞可能重叠，跨层关系不再局部；若允许无界度顶点进入删除集，一个粗三角形可能对应过多细候选。动态插边或移动顶点会改变多层三角剖分，静态 Kirkpatrick 结构不直接支持这种更新。

Voronoi 最近邻可以先构造 Voronoi subdivision，再用点定位查询所在面；距离语义来自 Voronoi 图，而不是点定位结构本身。

参考资料

David Kirkpatrick, “Optimal Search in Planar Subdivisions,” SIAM J. Comput., 1983.
de Berg et al., Computational Geometry, 3rd ed., point location.