test di contenimento circle-AABB

Question

Al momento sto scrivendo un sistema basato sulla suddivisione dello spazio (è per un gioco), devo essere in grado di verificare se un cerchio contiene completamente un quadrato.

Per i punti bonus, dovrei sottolineare che il mio sistema funziona in N dimensioni, quindi se il tuo algoritmo funziona facendo il ciclo attraverso ogni dimensione e facendo qualcosa, presentalo come tale;)

Answer 1

Degli angoli 2 ^ N, devi solo verificare che l'angolo più lontano dal centro dell'ipersfera sia all'interno dell'ipersfera.

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

Potresti voler conservare maxsq per la sfera piuttosto che ricalcolarlo ogni volta (una spesa molto piccola).