总面积表 (SAT) 的 3D 变体 [英] 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)

和query函数用于矩形角A(top-left), B(top-right), 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.另请说明是否有任何其他方法/数据结构可用于计算 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.

推荐答案

我不确定，但可以想到以下类似的东西.(我没有浏览过维基百科代码)

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 to x,y,z) 或 S0(x,y,z).
这可以通过一次遍历 3D 矩阵轻松构建.

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 )

(基本元素值 + S0(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,z2 是离原点最远的角落.

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 )

(有待更正)

这篇关于总面积表 (SAT) 的 3D 变体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！