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