如何查找距离指定点最近的Axis-Aligned Bounding Box（轴对齐包围盒）

你用曼哈顿距离作为排序依据得到的结果和暴力计算欧氏距离的结果不匹配是必然的：曼哈顿距离属于L1范数度量，计算逻辑是各轴偏移量的绝对值之和，等值线为菱形（2D）或正八面体（3D）；欧氏距离属于L2范数度量，计算逻辑是各轴偏移量平方和开根号，等值线为圆形（2D）或球形（3D），两者的排序逻辑没有严格的一致性，会出现曼哈顿距离更小但欧氏距离更大的情况，因此不能直接用曼哈顿距离作为欧氏距离的代理做最近邻检索。

先给出正确的单个AABB到点的距离计算逻辑，避免后续实现出错：
对于任意维度的轴对齐包围盒，首先将查询点的每个轴坐标*钳位（clamp）*到AABB对应轴的范围内，得到AABB上离查询点最近的点，两点之间的距离就是查询点到AABB的欧氏距离。

以3D场景为例，伪代码如下：

输入：查询点p (x, y, z)，AABB参数（min_x, max_x, min_y, max_y, min_z, max_z）
dx = max(min_x - p.x, 0, p.x - max_x)
dy = max(min_y - p.y, 0, p.y - max_y)
dz = max(min_z - p.z, 0, p.z - max_z)
euclidean_dist = sqrt(dx^2 + dy^2 + dz^2)

小优化：做距离比较时可直接用平方距离dx^2 + dy^2 + dz^2代替实际欧氏距离，省去开平方的计算开销，不影响大小排序结果。

根据你的AABB数组的更新频率、数据维度、数据量级可选择不同的实现方案：

• 静态AABB场景（AABB数组不会频繁增删改）：优先使用边界体积层次树（BVH），这是游戏、三维建模领域最常用的AABB最近邻检索结构，构建完成后单次查询的时间复杂度为O(logN)，远优于暴力遍历的O(N)。构建时将AABB逐层分组，每个父节点存储子节点的合并包围盒，查询时优先遍历和查询点距离更近的子树，直接剪枝距离更远的分支，无需遍历所有节点。
• 动态AABB场景（AABB数组会频繁增删改）：优先使用R树（或优化版R树）*，该结构对动态空间数据的增删查效率均衡，是GIS、地图引擎领域的通用空间索引结构，适配2D、3D场景的AABB检索。如果是2D场景且数据量级偏小，也可以选择k-d树实现，代码复杂度更低。
• 低维度小数据量场景：如果是2D场景且AABB量级在10^4以下，可使用网格空间划分：把整个空间切分为固定大小的网格，每个网格存储落在该网格范围内的AABB索引，查询时仅需遍历查询点所在网格及周边相邻网格内的AABB，即可过滤绝大多数无关AABB，实现成本极低且性能足够满足大多数业务需求。

内容的提问来源于stack exchange，提问作者Doofus