跳到主要内容

四叉树

四叉树如何递归划分二维空间？​

  • 四叉树: 每个内部节点划分为四个子区域，叶子保存该范围内的数据，三维对应思想常见于八叉树;
  • 自适应细分: 只有节点数据量超过阈值才继续划分，稠密区域更细、稀疏区域更粗;
  • 查询路径: 从根开始，只访问与查询范围相交的区域，跳过明显不可能包含结果的子树;
  • 适用条件: 范围搜索、地图、图像处理、网格生成与稀疏数据组织;
  • 类型: 原文列出点四叉树、PR 四叉树、PM 四叉树、压缩四叉树和边四叉树，具体划分规则随数据类型变化;

空间索引怎样减少最近邻搜索的计算？​

  • 基线问题: 对每个司机都计算距离需要扫描全部候选，规模增长后成本高;
  • 筛选收益: 空间索引先缩小候选，再计算实际距离；经纬度角度不能直接当作米制平面距离;
  • Hilbert 曲线: 可将空间区域映射成保持一定局部性的顺序，辅助数据布局或范围访问，但不是四叉树查询的必需步骤;
  • 动态代价: 高频位置更新涉及删除旧位置、插入新位置与并发读取，需要在精度、刷新率和吞吐间取舍;

如何在一个矩形范围内找到候选点？​

查询区域与当前节点不相交 → 跳过
相交且是内部节点 → 检查四个子区域
相交且是叶子 → 对叶子内点做精确范围判断
  • 阈值作用: 过早细分会增加节点与维护开销，过晚细分会让叶子扫描过多;
  • 对比: 分层编码网格与四叉树都需处理区域边界并做精确距离过滤;