递归拆分3D二进制数组,为每个等于1的条目创建比特流

Question

我正在尝试将二进制(仅元素0和1)动态分配的3D阵列拆分成单独的和更小的3D阵列.下图使人们更清楚地理解:

http://img521.imageshack.us/img521/4296/splittingsteps.png

它是10.000个元素的稀疏3D数组.对于每个1是我的数组的元素,我想创建一个唯一的比特流.获得的子域返回相应块中的多个1.然后将该数字转换为二进制数并添加到比特流中.

由于这种分裂操作每次都是相同的,首先在i方向上分裂,然后在j方向上然后在k方向上(3级)我想要递归地进行分割.此外,由于我在ANSI C中工作,非递归工作会导致大量重复代码.

拆分应终止于空的子域,因此只包含0(number_x = 0)或大小为[0..1] x [0..1] x [0].这些子域由霍夫曼代码处理.

更具体地说,它是一个具有起始尺寸的3D阵列:

I = [0 .. 511] x [0 .. 511] x [0 .. 31] 

我目前的前三个级别的代码可以在http://codepad.org/zGbAhKrC找到

拆分级别#1会产生两个维度的3D数组:

I_w = [0 .. 255] x [0 .. 511] x [0 .. 31]
I_e = [256 .. 511] x [0 .. 511] x [0 .. 31]

number_w = 6505,number_e = 3495表示两个部分中的1的数量.

拆分级别#2产生四个3D维度数组:

I_sw = [0 .. 255] x [0 .. 255] x [0 .. 31]
I_nw = [0 .. 255] x [256 .. 511] x [0 .. 31]
I_se = [256 .. 511] x [0 .. 255] x [0 .. 31]
I_ne = [256 .. 511] x [256 .. 511] x [0 .. 31]

number_sw = 2141并number_nw = 4364表示相应块中的1的数量. number_se = 1745并number_ne = 1750表示相应块中的1的数量.

拆分级别#3产生八个3D维度数组:

I_swm = [0 .. 255] x [0 .. 255] x [0 .. 15]
I_nwm = [0 .. 255] x [256 .. 511] x [0 .. 15]
I_swp = [0 .. 255] x [0 .. 255] x [16 .. 31]
I_nwp = [0 .. 255] x [256 .. 511] x [16 .. 31]
I_sem = [256 .. 511] x [0 .. 255] x [0 .. 15]
I_nem = [256 .. 511] x [256 .. 511] x [0 .. 15]
I_sep = [256 .. 511] x [0 .. 255] x [16 .. 31]
I_nep = [256 .. 511] x [256 .. 511] x [16 .. 31]

number_swm = 2141并number_swp = 0表示1相应块中的s 数. number_nwm = 4364并number_nwp = 0表示1相应块中的s 数. number_sem = 1745并number_sep = 0表示1相应块中的s 数. number_nem = 1750并number_nep = 0表示1相应块中的s 数.

有谁可以根据我当前的代码帮助我处理一些伪代码？

提前致谢!

Answer 1

看看 kd-tree维基百科中的例子。