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)]

图片： 这是一张二维图片，展示了这个想法：

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

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 的欧几里德范数（条目平方和的平方根）。

这不需要任何个案分析，并且适用于任何维度，无论框相对于彼此的位置如何。

python代码：

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

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

Minimum distance between two axis-aligned boxes in n-dimensions

box

euclidean-distance