variante 3D per la tavola zona sommati (SAT)

Question

Secondo Wikipedia:

Un summed area table è una struttura di dati e l'algoritmo per generare rapidamente ed efficientemente la somma dei valori in un sottoinsieme rettangolare di una griglia.

Per uno spazio 2D una tabella un'area sintetizzato può essere generato iterando x,y nell'intervallo desiderato,

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

E la funzione query per rettangolo angoli A(top-left), B(top-right), C(bottom-right), D può essere data da: -

I(C) + I(A) - I(B) - I(D) 

Voglio convertire in 3D. Indica inoltre se esistono altri metodi/strutture dati disponibili per il calcolo di somme parziali nello spazio 3D.

Answer 1

Non sono sicuro ma si può pensare a qualcosa come il seguente. (Non ho letto il codice di Wikipedia)

Per ogni coordinata (x, y, z) trovare la somma di tutti gli elementi da (0,0,0) a questo elemento.
Chiamalo S (da 0,0,0 a x, y, z) o S0 (x, y, z).
Questo può essere facilmente costruito attraversando una volta la matrice 3D.

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) 

(fondamentalmente valore dell'elemento + S0 (x1, y1, z-1) + 3 facce (xy, yz, zx))

Subito per ogni query (x1, y1, z1) a (x2, y2, z2), convertire prima le coordinate in modo che x1, y1, z1 sia l'angolo del cuboide più vicino all'origine e x2, y2, z2 sia l'angolo più lontano dall'origine.

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) 

(soggetto a correzioni)