CODEWITHSUNDEEP
algorithmmathcollision-detectioncollision
Martin
Martin

Reputation: 12403

circle-AABB containment test

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

Upvotes: 0

Views: 1170

Answers (2)

Jonathan Graehl
Jonathan Graehl

Reputation: 9301

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

Upvotes: 1

jcd
jcd

Reputation: 174

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.

Upvotes: 6

Related Questions