数学大学
B. Slab Method
计算几何 · 06. Point Location
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
B. Slab Method
计算几何 · 06. Point Location
Slab Decomposition
Slab 方法：过每个顶点做竖直线，把平面切成竖直条带（slab）。
条带内
条带内无顶点，边贯穿左右边界
条带内排序
穿过的边按 y 顺序排好
Ordering Trapezoids
条带内按 y 排序的梯形：相邻边之间的每个空隙是一个梯形面片。
梯形
两条相邻边与条带边界围成的区域
定位
查询点先定条带，再在条带内二分梯形
Tree of Trees
树套树结构：外层按 x 二分找条带，内层按 y 二分找梯形。
外层树
条带的区间树或二分树
内层树
每个条带挂一棵 y 方向的平衡树
Example
例题：小规模细分上的条带分解与查询演示。
演示
标出竖直线、条带与条带内的梯形编号
查询走查
沿外层树到内层树的完整查询路径
Query Time
查询时间：外层 O(log n) + 内层 O(log n) = O(log n)。
两层对数
两个二分相加仍是对数级
Preprocessing Time
预处理时间：构造条带与排序，O(n log n) 或更高（视实现）。
排序主导
条带内边的排序是成本大头
Storage Cost
存储代价：条带内边表的总和可达 O(n²)——这是 Slab 法的痛点。
平方存储
一条长边横跨多个条带被重复记录
改进方向
持久化结构或梯形图法可压回线性
Worst Case
最坏情形：网格状细分让每条边横跨所有条带，存储与预处理爆炸。
构造
n/2 条横线与 n/2 条竖线交织
教训
理论查询 O(log n) 但空间不可接受
本节要点
- ✓竖直条带 + 条带内 y 排序梯形
- ✓树套树查询 O(log n)
- ✓痛点：存储最坏 O(n²)
延伸主题：实现小规模 Slab 结构思考空间优化方案
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1Slab 法「查询快但空间爆炸」的根源是什么？
参考答案根源是同一条边在多个条带中被重复记录：横跨 k 个条带的边存储 k 份。树套树的每一层都要完整复制边表信息，最坏时平方爆炸。持久化（只存差异）正是为解决这个复制问题而生。
2条带法把「平面定位」降为「两次一维二分」，这个降维思想还能用在哪？
参考答案区间树、线段树套平衡树、kd 树都是同构的降维手法：外层处理一个维度、内层处理剩余维度。多维查询问题的通用分解策略就是「逐维建立层级索引」。
3O(n²) 空间最坏情形在什么应用里可以接受？
参考答案细分小而查询极频繁的静态场景（如游戏小地图、CAD 单图纸）可以接受：一次平方空间的预处理换来永久 O(log n) 查询。数据大或动态变化就必须换持久化或梯形图法。