平面点定位问题

形式陈述 ​

模型 ​

在计算几何公理库计算几何问题Computational geometry problem以点、线段、多边形等几何对象为输入并要求组合或数值几何输出的问题族。中，输入是平面图公理库平面图Planar graph · Plane graph可把顶点与边嵌入平面且除公共端点外没有交叉的抽象图。的直线细分：边只在共享端点相交，面由几何嵌入而非抽象图单独决定。预处理后，查询点 $q$ 返回包含它的面。若 $q$ 落在边或顶点上，本文返回所有相邻面；实现也可固定优先规则，但构建与查询必须采用同一约定。

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

Kirkpatrick 预处理 ​

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

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

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

查询状态演化 ​

查询从最粗层唯一外三角形开始。假设当前三角形为 ${\tau }_i$，只测试它指向的细层候选，找到包含 $q$ 的 ${\tau }_{i-1}$，直到原始 subdivision。每层做常数次三角形包含测试，定位时间为 $O(\log n)$；若接口要返回边界点的全部 $k$ 个相邻面，总时间为 $O(\log n+k)$。

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

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

直觉

Kirkpatrick 层级反复删去一批互不相邻的低度顶点，把细分压成几何级缩小的粗图。低度与独立性保证一个粗三角形只覆盖常数个下一层候选，因此查询只携带当前三角形逐层下降，而不用在每层重新搜索整张平面图。

例子与边界

边界谓词 ​

三角形包含测试由方向测试公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。组成。查询点恰在行政边界时，$\mathrm{orientation}(a,b,q)=0$ 必须进入专门分支：落在边内部时记录两侧候选；落在顶点时枚举完整 incident-face 列表。若浮点把零误算为正，后续细层没有全局校验替它纠正。

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

推论与应用

结构边界 ​

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

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

参考资料

• David Kirkpatrick, “Optimal Search in Planar Subdivisions,” SIAM J. Comput., 1983.
• de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008, point location.