دائرة 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 للتجارة والخدمات بدلا من إعادة حساب في كل مرة (أ حساب بسيط جدا).