тест сдерживания круга 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 для сферы, а не пересчитывать ее каждый раз (очень незначительные затраты).