2.4.3 空间索引与点位搜索

文档摘要

2.4.3 空间索引与点位搜索在地理信息系统、自动驾驶高精地图、城市三维建模、实时位置服务乃至游戏引擎的碰撞检测中，我们每天都在和“点”打交道——一个经纬度坐标、一个激光雷达扫描点、一个建筑角点、一个玩家角色的世界坐标。但当这些点的数量从千级跃升至亿级，甚至十亿级时，“遍历所有点并逐个计算欧氏距离”的朴素方法，就不再是算法，而是一场缓慢的自我惩罚。它像用算盘计算航天轨道：逻辑正确，效率致命。那么，如何在毫秒内从一亿个三维点中，精准定位出距离某查询点 $ \mathbf{q} = (xq, yq, zq) $ 不超过 $ r = 50\,\text{m} $ 的全部邻居？如何让地图APP在缩放拖拽时，不卡顿地渲染当前视野内的数万POI？