【基于坐标的八叉树数据结构设计案例分析6900字】

基于坐标的八叉树数据结构设计案例分析目录TOC\o"1-3"\h\u11584基于坐标的八叉树数据结构设计案例分析 1102711.1设计基于坐标的八叉树数据结构的必要性 1171231.2任意维度坐标空间的定义与实现 2192951.2.1任意维度坐标空间的定义 2303971.2.2固定某个维度坐标空间的实现 5308781.3基于三维坐标的八叉树的定义、实现与应用 11122211.3.1基于三维坐标的八叉树的定义 11148601.3.2基于三维坐标的八叉树的基本操作实现 12设计基于坐标的八叉树数据结构的必要性点云空间不是线性空间，而是三维空间。但点云的主流文件格式，如PLY、PCD、OBJ等（引用上述例子）均为顺序列出所有点、边和面等信息。点云中每个点属性在文件中或内存中的出现位置并不影响点云的表示，此属性位置无关特性称为点云的“无序性”。因此，直接在线性空间中依序寻找目标点的时间复杂度非常高。以PLY文件格式为例，PLY文件在指定区段内紧凑保存着所有点的坐标信息。由于PLY文件并未规定点的出现顺序。因此，点出现在任意序号均为合法表示，也即PLY文件中若干点之间的坐标值可以不按照坐标大小单调排列。在此状态下，我们无法借助单调性实现二分查找。如果要对所有点按三维坐标字典序排列，则不仅要重排点，还会影响后续的面、边的定义。因为PLY文件对于面、边的定义是依据点出现的序号。因此，重排PLY文件中点的顺序，还需要重构面、边的定义。此举会导致预处理计算量偏大。综上所述，对所有点按三维坐标进行字典序排序后理论上只能做到O(log2n)的时间复杂度，且前期还需要大量的准备工作。因此有必要提出一种数据结构，能够实现不重排点的前提下，尽可能高效地查找三维空间中的某个点。本文借助八叉树[1]的设计思想，即将三维点云空间逐级八等分化，把每个子空间称为“体素（VolumePixel，简称Voxel）”。再将访问点操作分为“检索点所在空间（体素）”和“检索空间（体素）内点”两个部分，以期通过“模块化”思想先将访问点的时间代价缩小到查找所在空间（体素），然后再在所在空间（体素）内逐个遍历每个点。O-CNN[1]是将点云三维空间沿每个坐标轴等分为两份，即将一个完整的三维空间等分为八份。如果将细分后的每个子空间继续按照上述标准细分，则又会细分出下级八个子空间。由于每次细分都是固定一分为八，且为逐级向下细分，故可以将此细分过程以“八叉树”表示。因此，原始的完整空间即为八叉树的“根（root）”，每次细分都是八叉树的“层（level）”。在现实情况中，三维空间每个维度的上下界宽度可能并不相同，即原始三维空间并非正立方体。O-CNN[1]中并没有严格要求三维点云空间是否必须为正立方体。为了消除坐标空间不同维度的宽度有别导致访问算法更复杂，本文在借鉴O-CNN[1]的基本思想，创新性地提出在初始化坐标空间时，根据坐标范围最大的轴（下文称“最长轴”），将其余两个轴沿中心拓展到与最长轴等长，即将原始空间拓展为标准正立方体的方法。此外，在初始化八叉树空间时，需要指定八叉树的“层数”，即三维空间的细分“粒度”。“层数”越多，每个叶子空间（称作“体素”，Voxel）的体积就越小，相同密度空间下包含的点数就越少；反之子空间体积就越大，包含的点数就越多。假设空间内的点数为C，叶子体素数为V，则显然（注意，公式需要单独一行，并编号） V<=C （3.1）因此，为三维空间的八叉树区分法同时也可以视作“三维点云的降采样”。“三维空间八叉树”数据结构仅仅是将访问点的时间复杂度降低到体素维度，但没有提出如何快速定位体素。而从“根”开始逐级向下查找的时间复杂度为O(log最后，考虑到现实情况中点云空间可能出现局部点密度过高，即少数含点体素的平均点数显著高于其他含点体素的平均点数，而少数含点较多的体素有继续划分的需要。本文提出了在不需要整体重新细分体素的前提下允许细分局部体素的方法，以允许降采样的同时保留细部特征。为了解决更方便定位三维空间中的体素，本文先提出了“任意维度坐标空间”数据结构。并将三维空间视为“任意维度坐标空间”的一个特化，同时将体素视为空间元素。此数据结构也为后续章节提供了理论铺垫。任意维度坐标空间的定义与实现任意维度坐标空间的定义本文“空间（Space）”的定义与线性代数的“线性空间”定义类似，所以“空间”的“维度”的定义也与“线性空间”的“维数”相同，即线性空间V中有n个线性无关向量，但存在n+1个向量都是线性相关，则称V是一个n维线性空间。记作dimV=n。在本文中，“空间”定义唯一与线性代数的“线性空间”不同的是，空间的刻度只有整数，即空间是离散的。在后文中如无特殊指定，“空间”均指“离散空间”。离散空间至少应为二维空间。考虑到计算机的地址空间有限，且受中央处理器单次访存限制，计算机实际能够实现的空间维度数存在上限。另一方面，目前计算机使用二进制表达所有内容。整数在计算机中的表达范围固定为232个，其中n为计算机字长。例如，32位计算机中，有符号整数的表示范围为[−2n−1为了简便说明，先以二维空间说明，然后再推广到更高维度空间。一、二维坐标离散空间空间本文中，二维坐标离散空间的定义为以直角坐标系为基础，以（0，0）为原点，每个维度的定义域均为[0..n−1]，（n为2的正整数次幂），每个维度只记录整数刻度d。即此二维空间是“正方形离散空间”。以图3.1为例，图中两条直线相交于坐标（6，7）、（7，7）、（6，8）和（7，8）。图3.1二维空间直角坐标更进一步地，因为“线性空间”的定义使用几何来表示时，并未要求每个维度之间必须为直角，仅需保证线性无关即可，因此二维空间中两个坐标维度方向可以不为直角，但不能相向或相反，即两个维度必须线性无关。图3.2二维空间非直角坐标举例图3.2中，原直角坐标系的空间经过一定变换得到了两个坐标系非直角也非平行的情况。由于此坐标变换前后依然保持线性无关，本文仍将其视作“正交”。此变换后的空间也没有违背“离散”原则，故本文仍将该空间视为“离散空间”。二、三维及更高维度坐标空间三维空间以直角坐标系为基础，以（0，0，0）为原点，每个维度的定义域均为[0..n−1]，（n为2的正整数次幂），每个维度只记录正整数刻度。即此三维空间是“正立方体离散空间”。图3.3三维空间直角坐标与“二维空间”类似，三维即更高维度坐标空间依然采用“每个维度定义域范围为2的整数次幂个离散刻度”与“原点即起点”的原则。例如，图3.3中三条直线交点坐标（6，7，8）即为该三维空间的整数刻度。三维坐标空间可以表示现实世界的立体空间。更高维度坐标空间在现实环境下无法表示，仅作为二维空间与三维空间的推广而存在。假设Vm为m为空间，（0,0,…,0）（一共m个0）为该空间的坐标原点，每个维度的定义域均为[0..n−1]，（n“更高维度坐标空间”可以将第四个维度赋予新的含义，如在随时间变化的空间中，第四维度可以视作“时间维度”等。固定某个维度坐标空间的实现一、二维坐标空间的存储结构表示二维空间定义域（domainofdefinition）有四种方法：1.使用两个一维数组各表示一个维度：vector<unsignedint>domain_a,vector<unsignedint>domain_b2.一个二维数组，分别表示两个维度：vector<vector<unsignedint>>domains3.使用一个一维数组表示两个维度：vector<unsignedint>domains4.使用一个散列表表示两个维度：unordered_map<unsignedint,_Tvalue>domains为了将二维坐标空间扩展到任意维度坐标空间，本文没有采用连续存储方案，而采用第4种方案——散列表方案，理由如下：1.连续数组在保存稀疏空间的元素时会造成大量空间浪费。特别是空间特别大时，STL容器可能无法达到，如坐标域达到2311.1假设离散二维正交坐标空间A，其两个维度的定义域均为[0..n−1]，（n为大于等于2的正整数），即每个坐标轴的表示个数为n个，合计共有n21.2假设A中有元素m个，随机分布在A中，而m远小于n2。（远小于的定义为m<log21.3浪费率 w=1−m1.4如果在“远小于”定义下，浪费率下限为 w0=1−1.5由上述定义过程可知，定义域范围越大，即n越大，空间浪费下限就越大，空间浪费就越严重。因此，连续存储空间不适合作为稀疏元素二维坐标定义域表示方案。访问某个元素的时间复杂度O(1)与空间复杂度O(n2.散列表方案中，选择使用“无序映射（unordered_map）”的理由是：2.1对于访问操作时间复杂度来说，平均情况为O(1)，最坏情况下为O(m)，其中m为unordered_map中保存的元素个数。2.2对于空间复杂度来说，为了避免频繁增删而导致的内存空间申请与释放的时间开销，我们使用了“存储桶（buckets）”概念，即存储一个数据时如果需要开辟空间，则一次开辟一个连续区域，而非只开辟恰好能保存一个数据大小的空间。这样元素散列映射到的是某个存储桶，而非具体的存储区域。这些存储桶默认并不存在，需要使用存储桶之前也需要申请空间，并且根据初始化unordered_map的方式来决定存储桶的数量。因此，具体实现中使用O(m+N)空间，其中m是元素个数，N是存储桶数。根据上述定义，N必定小于等于m。因此unordered_map空间复杂度上限为O(2m)=O(m)（空间复杂度只考虑数量级，而不考虑系数）。本文将用于保存“坐标”-“元素”映射的“无序映射”数据结构称为“坐标-元素映射表”（在本节范围内简称“该表”）。二、散列表键的设计方案“坐标-元素映射表”的键使用非负整数类型，长度与当前计算机位宽相同，即32位机的键类型长度为32位，64位机的键类型长度为64位。将键长度选取与计算机字长相当是为了既能充分利用CPU一次访存的全部潜力，又不会额外增加访问开销。考虑到当前计算机早已普及64位字长，以下内容均以64位计算机字长举例说明。在没有先验条件的情况下，元素出现在二维空间任何位置的概率均相同。因此，二维正交坐标空间两个维度应当设置为相同的表示范围。具体地说，即将键长64位等分为两部分，分别表示两个维度，即每个维度可以分得32位长度，能表示232如果两个维度范围没有超过或正好在232以内，则“坐标-元素映射表”可以实现无冲突保存每个元素。即访问操作的时间复杂度为O(1)，空间复杂度上限为O(m+N)，其中m为元素个数，N如果两个维度范围超过了分给每个维度的表示上限，即232裁剪的方案有两种，一种是“保留高位，抛弃低位”，另一种是“保留低位，抛弃高位”。此操作的目的是使裁剪后的坐标值范围不超过分配到的维度定义域，即32位。以下为两种方案的比较：1.如果采用“保留高位”，则特点为，相邻坐标元素的键值相同，会在散列表中产生堆积现象。2.如果采用“保留低位”，则可以避免相邻元素堆积现象。对于点云表示的空间场景来说，区域聚集现象明显，因此更适合采用“保留低位”的方案。假设某个元素的坐标为(x,y)，其中x,y为[0..n−1]内的整数。则散列表键的计算公式为： key=x其中“&”为按（二进制）位与运算，“<<”为算数左移运算。下同。具体坐标转为散列表键的代码如下：size_toperator()(coordinates_typeconst&c)const

{

//取得当前计算机unordered_map键类型的二进制长度

constautotype_length=sizeof(size_t)*8;

//将键长度平分给每个维度

constautodimension_length=type_length/D;

//设置掩码。掩码长度与维度位宽有关。

//如D=2（二维）且键长度为64位时，每维度分得的宽度为32位，此时掩码为0xFFFFFFFF。

unsignedintmask=0;

for(size_ti=0;i<dimension_length;i++)

{

mask<<=1;

mask+=1;

}

size_tindex=0;

for(inti=0;i<D;i++)

{

index+=static_cast<size_t>(c[i]&mask)<<(i*dimension_length);}returnindex;}“坐标-元素映射表”的键要求坐标范围为从0开始的非负整数。如果实际坐标范围并非从零开始，而是存在偏置，则可以在计算散列表键之前进行变换。变换公式如下： key=x其中∆x为x轴坐标相对于零点的偏置，∆y为y轴坐标相对于零点的偏置。例如实际坐标范围为∆x∈[5..10],∆y∈[−3..2]，其中∆x和∆y均为整数，则∆x=5,∆y=−3。三、散列表值的设计方案此二维空间并不限制元素的类型，即元素类型可以是标量（scalar），也可以是标量的复合类型，如“结构体”、“类的实例”、“指针”等。但要将值存入散列表中，需要将值复制一份。如果要保存的值类型是标量，即类型长度固定，则复制操作的时间复杂度和空间复杂度可以准确预估。但在复合类型情况下，每个值所占用的空间差距可能非常大，复制较大尺寸的值既浪费时间又浪费空间。另一方面，若值是“单例”或“复制赋值会影响外部变量”时，则不允许复制。为了解决上述困难，值的方案采用“指针指向方式”，即保存的是“指向当前坐标的值的指针”。由于元素的数量可能特别多，为了方便管理大量元素而尽量避免在元素申请、释放内存空间时可能产生的内存泄漏问题，也为了方便多个引用源访问，故采用“共享指针”方案。具体的正交散列表设计方案为：typedefstd::unordered_map<coordinates_type,std::shared_ptr<T>,Hash>pointers_map;其中Hash是“散列表键的设计方案”中提到的operator()。二维坐标空间的基本操作二维坐标空间的基本操作有如下四种：初始化空间二维坐标空间的初始化方案为：初始化用于保存“坐标”-“元素”的“无序映射”表。由于初始状态下没有任何元素，因此无须添加任何内容，故初始状态“无序映射”表只需开辟一个“存储桶”。初始化空间的时间复杂度为O(1)，空间复杂度为O(1)。声明初始化空间也包括定义坐标转换为键的换算方法。换算方法以式（3.5）为准。四、判断元素是否存在由于添加和删除元素前需要判断指定坐标的元素是否存在，故需要声明并实现此操作。由于保存坐标-元素使用的是“无序映射”表，因此，判断元素是否存在的实质是判断映射表指定键是否存在。如果指定键不存在冲突，则查找判断该键是否存在的时间复杂度为O(1)，最坏情况下是O(m)，其中m为“无序映射”表中的元素个数。判断元素是否存在的步骤如下：1.判断给定坐标是否为二维。如果不是则抛出异常；如果是则继续下一步。2.判断指定坐标是否在定义域范围内，如果不是，则抛出异常；如果是则继续下一步。3.查找指定坐标换算的键是否存在对应的元素。如果查找后返回的指针没有指向坐标映射的结尾，则表明指定坐标键不存在元素，返回false；如果不是，则表明指定坐标键已存在元素，返回true。添加一个元素添加一个元素的步骤如下：1.判断元素是否存在，如果抛出异常或存在，则返回0，否则继续下一步。2.将指定坐标键的值修改为待添加元素的共享指针，并返回1。第一个步骤的时间复杂度和空间复杂度参见“判断元素是否存在”一节。第二个步骤的时间复杂度平均为O(1)，最坏情况出现在所有待添加元素均冲突，即O(m)，其中m为“坐标-元素映射表”的已存在元素个数。综合平均时间复杂度为O(1)，最坏时间复杂度为O(m)。图3.4添加一个点（5,7）五、删除一个元素删除一个元素的步骤如下：1.判断元素是否存在，如果存在，则继续下一步，否则返回0。2.将指定坐标键的值修改为nullptr，并返回已删除元素的共享指针，交由用户进一步处置从“坐标-元素映射表”中刚删除的元素。第一个步骤的时间复杂度和空间复杂度参见“判断元素是否存在”一节。第二个步骤的时间复杂度平均为O(1)，最坏情况出现在待删除元素与其它所有元素均冲突，即O(m)，其中m为“坐标-元素映射表”的已存在元素个数。综合平均时间复杂度为O(1)，最坏时间复杂度为O(m)。图3.5删除（5,7）点后的状态，即坐标空间内已不存在任何元素基于三维坐标的八叉树的定义、实现与应用基于三维坐标的八叉树的定义八叉树是一种用于描述三维空间的树状的数据结构。八叉树的每个节