3D-Variante für summierten Bereichstabelle (SAT)

Question

Wie pro Wikipedia:

summed area table A ist eine Datenstruktur und einen Algorithmus, um schnell und effizient die Summe der Werte in einem rechteckigen Teilmenge eines Gitters zu erzeugen.

für einen 2D-Raum eines Integralbild durch Iterieren x,y über den gewünschten Bereich erzeugt werden kann,

I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1) 

Und die query Funktion für ein Rechteck Ecke A(top-left), B(top-right), C(bottom-right) kann D gegeben sein 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.

Answer 1

Ich bin mir nicht sicher, aber so etwas wie das folgende kann gedacht werden. (Ich bin nicht durch den Wikipedia-Code gegangen)

Für jede Koordinate (x, y, z) finden Sie die Summe aller Elemente von (0,0,0) zu diesem Element.
Nennen Sie es S (0,0,0 bis x, y, z) oder S0 (x, y, z).
Dies kann leicht durch einmaliges Überfahren der 3D-Matrix erstellt werden.

S0(x,y,z) = value[x,y,z] + S0(x-1,y-1,z-1) + 
       S0(x,y,z-1) + S0(x, y-1, z) + S0(x-1, y, z) 
       - S0(x-1, y-1, z) - S0(x, y-1, z-1) - S0(x-1, y, z-1) 

(grundsätzlich Elementwert + S0 (x1, y1, z-1) + 3 Flächen (xy, yz, zx))

nun für jede Abfrage (x1, y1, z1) to (x2, y2, z2), wandeln Sie zunächst die Koordinaten so um, dass x1, y1, z1 die Ecke des Quaders ist, die dem Ursprung am nächsten liegt, und x2, y2, z2 die Ecke ist, die am weitesten vom Ursprung entfernt ist.

S((x1,y1,z1) to (x2,y2,z2)) = S0(x2,y2,z2) - S0(x2, y2, z1) 
           - S0(x2, y1, z2) - S0(x1, y2, z2) 
           + S0(x1, y1, z2) + S0(x1, y2, z1) + S0(x2, y1, z1) 
           - S0(x1, y1, z1) 

(vorbehaltlich Korrekturen)