3D变体为积分图（SAT）

2013-12-07 52 views 6 likes

甲summed area table为快速和有效地生成的网格的矩形子集值的总和的数据结构和算法。

对于可以通过在期望的范围内进行迭代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空间中的部分总和。

来源

2013-12-07 Ninja420

不与维基百科条目回答部分这一问题标记为“扩展名？”我相信它给出了底部高维空间的公式。 – templatetypedef

是的，我尝试了解，但不能完全掌握它。你能解释一下吗？ – Ninja420

回答

我不知道，但像下面这样可以想到的。（我还没有通过维基百科代码消失）

对于每一个坐标（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（X1，Y1，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)

（如有更正）

来源

2013-12-07 19:07:09

和你将如何制作S0矩阵？ – Ninja420

@ Ninja420看我的更新。这将需要3D可视化，但我认为如果你有这个想法，这不会很困难。 –

S0（x1，y1，z1）出现两次，其中一个应该是x1，y2，z2我猜 – Ninja420

3D变体为积分图（SAT）

回答

相关问题