3维求和面积表(SAT)
根据维基百科：
总和面积表是一种用于快速高效地生成网格矩形子集中值和的数据结构和算法。
对于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空间中的部分和。
回答 2
Stack Overflow用户
发布于 2013-12-07 19:07:09
我不确定，但可以想到以下几点。(我还没看过维基百科的代码)
对于每个坐标(x，y，z)，找出从(0，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 )(需更正)
Stack Overflow用户
发布于 2021-11-19 11:34:24
派对有点晚了，但不管怎样。在维基百科中有一个通用的n维空间公式，用本论文给出.按照该表示法，我们假设您对带有角(x0、y0、z0)和(x1、y1、z1)的矩形框指定的卷感兴趣。然后，有一个积分图像(体积)，系数为: S((x0，y0，z0) to(x1，y1，z1)) = S(x1，y1，z1) - S(x1，y1，z0) - S(x1，y0，z1) + S(x1，y0，z1) +S(x1，y0，z1) -S(z1，，)+S(，，)+S(，，)-S(，，)
这是我用来计算它们的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:1https://stackoverflow.com/questions/20445084
复制相似问题
腾讯云开发者
