algorithm - サークル-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 を保存することをお勧めします (わずかな費用です)。