3D变种积分图（SAT） [英] 3D variant for summed area table (SAT)

问题描述

根据维基百科：

一个积分图是数据结构和算法，快速有效地生成的总和在网格的矩形子集的值。

A summed area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid.

对于二维空间可以通过迭代生成一个积分图 X，Y 在所需范围内，

For a 2D space a summed area table can be generated by iterating x,y over the desired range,

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

而查询函数的矩形角 A（左上）， B（右上）， C（右下）， D 可由下式给出： -

And the query function for a rectangle corners A(top-left), B(top-right), C(bottom-right), D can be given by:-

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

我要转换的上面3D。也请告诉我们，如果任何其他方法/数据结构，可用于计算在三维空间中的部分款项。

I want to convert the above to 3D. Also please tell if any other method/data structure available for calculating partial sums in 3D space.

推荐答案

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

I'm not sure but something like the following can be thought of. ( I haven't gone through the Wikipedia code )

对于每一个坐标（X，Y，Z）发现，从（0,0,0）到该元素的所有元素的总和。
说它是S（0,0,0到的x，y，z）或S0（X，Y，Z）。
这可以通过遍历三维矩阵一次容易地建造。

For every coordinate (x,y,z) find the sum of all elements from (0,0,0) to this element.
Call it S(0,0,0 to x,y,z) or S0(x,y,z).
This can be easily built by traversing the 3D matrix once.

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 )

（基本上元素值+ S o（X-1，Y-1和z-1）+ 3面（XY，YZ，ZX））

(basically element value + S0(x-1,y-1,z-1) + 3 faces (xy,yz,zx) )

现在为每个查询（X1，Y1，Z1）到（X2，Y2，Z2），第一转换坐标以便X1，Y1，Z1是的长方体最靠近原点和X2，Y2的拐角处，Z 2是角落最远的起源。

Now for every query (x1,y1,z1) to (x2,y2,z2), first convert the coordinates so that x1,y1,z1 is the corner of the cuboid closest to origin and x2,y2,z2 is the corner that is farthest from origin.

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 )

（如有勘误的内容）

这篇关于3D变种积分图（SAT）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！