求和面积表(SAT)的三维变体

Question

根据维基百科：

求和面积表是一种用于快速有效地生成网格的矩形子集中的值的和的数据结构和算法。

对于2D空间，可以通过在所需范围上迭代x,y来生成求和面积表

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

矩形角A(top-left)、B(top-right)、C(bottom-right)、D的query函数可以由以下公式给出：-

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

我想把上面的转换成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 )

（可更正）

Answer 2

派对有点晚了，但无论如何。维基百科中有一个关于n维空间的通用公式。根据该符号，我们假设您对一个带角（x0，y0，z0）和（x1，y1，z1）的矩形框指定的体积感兴趣。然后，对于积分图像（体积），系数将为：S（（x0，y0，z0）到（x1，y1，z1））=S（x1，y1，z1）-S（x1，y1，z0）-S（x1，y0，z1

这是我用来计算它们的matlab代码（可以指定维度）

%number of dimensions
nDim = 3;
for i=1:2^nDim
        str=dec2bin(i-1,nDim);
        strout='index combo (';
        sum=0;
        for n=1:nDim
            strout = strcat(strout,str(n));
            sum=sum + str2num(str(n));
        end
        strout = strcat(strout,') sign: ',num2str((-1)^(nDim-sum)));
        disp(strout);
end

输出：

(000) sign:-1
(001) sign:1
(010) sign:1
(011) sign:-1
(100) sign:1
(101) sign:-1
(110) sign:-1
(111) sign:1