求和面积表(SAT)的3D变体

Question

根据维基百科:

甲积分图是用于快速和有效地生成的网格的矩形子集值的总和的数据结构和算法.

对于2D空间,可以通过迭代x,y所需范围来生成求和区域表,

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

而query对于一个矩形角功能A(top-left),B(top-right),C(bottom-right),D可以由下式给出: -

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

我想将上面的内容转换为3D.另请指出是否有任何其他方法/数据结构可用于计算3D空间中的部分和.

Answer 1

我不确定，但可以想到类似以下的内容。（我还没有浏览维基百科代码）

对于每个坐标 (x,y,z)，求从 (0,0,0) 到该元素的所有元素的总和。
将其称为 S(0,0,0 到 x,y,z) 或 S0(x,y,z)。
这可以通过遍历 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 )

（基本上元素值 + S0(x-1,y-1,z-1) + 3 个面 (xy,yz,zx) ）

现在，对于每个查询 (x1,y1,z1) 到 (x2,y2,z2)，首先转换坐标，使 x1,y1,z1 是最接近原点的长方体的角，x2,y2,z2 是最接近原点的角距离原点最远。

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 )

（有待更正）