3D-Variante für summierte Flächentabelle (SAT)
Gemäß Wikipedia:
A summierte Flächentabelle ist eine Datenstruktur und ein Algorithmus zum schnellen und effizienten Erzeugen der Summe von Werten in einer rechteckigen Teilmenge eines Gitters.
Für einen 2D-Raum kann eine summierte Flächentabelle durch Iteration erzeugt werdenx,y
über dem gewünschten Bereich,
I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)
Und dasquery
Funktion für ein Rechteck EckenA(top-left)
, B(top-right)
, C(bottom-right)
, D
kann gegeben werden durch: -
I(C) + I(A) - I(B) - I(D)
Ich möchte das obige in 3D konvertieren. Bitte geben Sie auch an, ob eine andere Methode / Datenstruktur für die Berechnung von Teilsummen im 3D-Raum verfügbar ist.