n 维中两个轴对齐框之间的最小距离

Question

问题：如何有效计算 n 维中两个轴对齐框之间的最小距离？

框格式：框 A 和 B 由它们的最小点和最大点 A_min、A_max、B_min、B_max 给出，每个点都是一个 n 维向量。也就是说，这些框可以在数学上写为以下区间的笛卡尔积：

A = [A_min(1), A_max(1)] x [A_min(2), A_max(2)] x ... x [A_min(n), A_max(n)]

B = [B_min(1), B_max(1)] x [B_min(2), B_max(2)] x ... x [B_min(n), B_max(n)]

图片：这是一张以 2D 形式展示这个想法的图片：

---

注意：注意：我问这个问题，并自己回答，因为即使过了这么多年，这个问题（通常是 n 维形式）似乎也没有出现在 stackoverflow 中。一般而言，在互联网上很难找到这个问题的良好答案。经过谷歌搜索后，我最终不得不自己解决这个问题，并在这里发帖以避免未来的人遇到同样的麻烦。

Answer 1

盒子之间的最小距离由下式给出：

dist = sqrt(||u||^2 + ||v||^2)

在哪里

u = max(0, A_min - B_max) 
v = max(0, B_min - A_max)

最大化是在向量上按条目进行的（即，max(0, w) 意味着用零替换向量 w 的所有负条目，但保持正条目不变）。符号||w|| 表示向量 w 的欧几里得范数（条目平方和的平方根）。

这不需要任何具体情况分析，并且适用于任何维度，无论盒子相对于彼此的位置。

蟒蛇代码：

import numpy as np

def boxes_distance(A_min, A_max, B_min, B_max):
    delta1 = A_min - B_max
    delta2 = B_min - A_max
    u = np.max(np.array([np.zeros(len(delta1)), delta1]), axis=0)
    v = np.max(np.array([np.zeros(len(delta2)), delta2]), axis=0)
    dist = np.linalg.norm(np.concatenate([u, v]))
    return dist