圈-AABB遏制测试

Question

我目前正在编写一个基于细分空间的系统（用于游戏），我需要能够测试一个圆是否完全包含一个正方形。

为了加分，我应该指出我的系统在 N 维上工作，所以如果你的算法通过循环每个维度并做一些事情来工作，那么就这样呈现它;)

Answer 1

在 2^N 个角点中，只需检查距超球面中心最远的角点是否在超球面内部。

所以：

distance = 0
for each dimension D:
    a = abs(coordinate of sphere center in D - min coordinate of cube in D)
    b = abs(coordinate of sphere center in D - max coordinate of cube in D)
    distance += max(a,b)^2
if distance <= radius*radius then cube is in sphere.

Answer 2

// lower and upper are opposite corners (e.g. min and max for each dimension)
within(center,radius,lower,upper):
  maxsq<-radius^2
  sumsq<-0
  for c<-0 to N-1
     dl=(center[c]-lower[c])^2
     du=(center[c]-upper[c])^2
     sumsq<-sumsq+max(dl,du)
     if sumsq > maxsq return false
  return true

您可能想要存储球体的 maxsq 而不是每次都重新计算它（这是一个非常小的费用）。