circle-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，而不是每次都重新计算（非常小的费用）。