circle-AABB containment test

Question

I'm currently in the throes of writing a system based on subdividing space (it's for a game), I need to be able to test if a circle completely contains a square.

For bonus points, I should point out that my system works in N dimensions, so if your algorithm works by looping through each dimension and doing something, present it as such ;)

Answer 1

// 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

You may want to store maxsq for the sphere rather than recomputing it every time (a very minor expense).

Answer 2

Of the 2^N corners, you only need to check that the furthest corner from the center of the hypersphere is inside the hypersphere.

So:

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.