平面点定位问题

形式陈述 ​

模型 ​

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

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

Kirkpatrick 预处理 ​

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

具体地，由平面图 Euler 边数界理路平面图欧拉公式Euler's formula for planar graphs连通平面图的顶点数、边数与面数满足 V−E+F=2。与握手引理理路握手引理Handshaking lemma有限无向图中所有顶点度数之和等于边数的两倍。，含 $N$ 个顶点的简单平面三角网满足度数和小于 $6N$，故度数至少 $12$ 的顶点少于一半。去掉三个外顶点后，在 $N\ge 12$ 时仍有至少 $N/4$ 个度数至多 $11$ 的候选。反复选一个候选，并从候选表中删去它及其邻居，每次至多删去 $12$ 个，因而可选至少 $N/48$ 个互不相邻顶点。规模小于 $12$ 后，余下处理是常数工作。这证明每轮可删去常数比例顶点。层数因此为 $O(\log n)$；各层规模形成几何级数，总三角形与跨层指针为 $O(n)$。

每个粗层三角形只记录与下一细层具有二维内部重叠的三角形；相同未改变的三角形也保留一条对应链接。不能把只在边或顶点接触也算进候选，否则一个未删的高阶顶点就可能带来许多无关三角形。每份局部洞至多涉及常数个旧三角形，所以这些候选数量有统一常数界。这个常数候选性质来自低度删除及局部重三角化，不是“递归层级”四个字自动带来的。

查询状态演化 ​

若查询点在外三角形之外，直接返回原细分的唯一无界面；其余查询从最粗层外三角形开始。假设当前三角形为 ${\tau }_i$，只测试它指向的细层候选，任选一个闭三角形包含 $q$ 的 ${\tau }_{i-1}$，直到最细三角网。粗三角形由这些候选的闭包覆盖，因此即使 $q$ 在边界上也能继续；无需沿所有并列候选分叉。每层做常数次三角形包含测试，定位时间为 $O(\log n)$；若接口要返回边界点的全部 $k$ 个相邻面，总时间为 $O(\log n+k)$。

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

预处理接口应保存原三角形到 subdivision 面的映射，因为输入面可能被对角线拆成多个三角形。最后一步返回的是原面标识，而非任意一个内部三角形编号。若查询点恰为最细三角形的原顶点，则读取该顶点预存的、去重后的 incident-face 列表；若在原边内部，则读取其一侧或两侧的不同原面。辅助对角线与新增外框不应被误报成原细分边界。全部去重列表的总长度为 $O(n)$，输出的 $k$ 个不同面另花 $O(k)$，即使许多桥都邻接同一个面也不必重复扫描它们。