室内疏散方案可以指导用户从空间内的一点到达另一点，此类应用离不开位置范围的确定^[1-6]。在确定位置范围的过程中引入空间索引，可以减少此过程的时间耗费和降低定位出错的几率^[7-11]。

用于优化空间操作的典型索引有四叉树索引、KD树索引和R树索引等^[12-16]。这些索引通过减小搜索空间范围达到优化操作性能的目的。在这类索引中，面向对象的R树索引空间操作性能表现较优。不同于四叉树和KD树这些单纯从平衡节点数据量出发的通用索引，R树索引通过生成空间上包裹对象集合的最小外接矩形框来构建索引^[17-18]。R树从诞生到现在，衍生出了R+树和R^*树等变种。在这些R树变种中，R^*树因其对于空间操作的优良性能得到了广泛应用^{[12, 19-20]}。

R^*树与标准R树一样，也采用最小外接矩形框来包裹空间对象。但是与标准R树对重叠叶节点的粗糙处理方式不同，R^*树对于重叠以及溢出叶节点进行考虑平衡的重新插入，以达到减小外接矩形框的重叠空间范围的目的(图 1)。

图  1  标准R树和R^*树空间索引效果图

Figure  1.  Diagram of Spatial Classification Results of Classic R Tree and R^* Tree

下载: 全尺寸图片 幻灯片

在使用空间索引的过程中，需要关注的一个关键技术细节是节点的遍历顺序问题。由于对节点的不同遍历方式往往会导致巨大的性能差异，相关研究人员提出了若干空间遍历曲线，以利用它们提高空间操作效率^{[19, 21]}。其中, 以Peano曲线、Moore曲线和Hilbert曲线最为著名^{[1, 19, 22]}。在这些曲线中，Hilbert曲线以其良好的局部相关性和位置编码接近真实坐标的特性被广泛关注(见图 2)^[23-25]。局部相关性是指曲线上前后遍历的节点在空间操作中被同时使用的几率；位置编码是指特定空间位置在曲线上利用若干基本方向构成的相对坐标数值(见图 3)。局部相关性好是指在曲线上被顺序遍历的空间对象在空间操作中也有极大几率被同时调用；位置编码无限逼近真实坐标则是指空间遍历曲线上通过无限迭代最终和真实空间坐标拟合的特性。

图  2  1次、2次、3次和4次迭代的二维Hilbert曲线

Figure  2.  Graphic Illustration of One Iteration, Two Iterations, Three Iterations and Four Iterations of 2-Dimensional Hilbert Curve

下载: 全尺寸图片 幻灯片

图  3  二维3次迭代Hilbert曲线遍历空间和编码映射原理

Figure  3.  Graphic Demonstration of Traversing and Coding for Hilbert Curve in 2-Dimensional Space

下载: 全尺寸图片 幻灯片

综上所述，本文将R^*树对于空间对象聚类的特点和Hilbert曲线高效遍历邻近空间对象的特点融合，得到集成Hilbert曲线的R^*树索引, 利用这种索引能够对室内疏散相关的应用进行优化，从而达到提高空间操作效率的目的。

1 集成Hilbert曲线的R^*树索引

构建集成Hilbert曲线的R^*树需要完成Hilbert码的生成、Hilbert码和R^*树的集成这两个步骤。前者是为了利用Hilbert曲线对邻近空间对象的优良遍历特性打下基础；后者则是将Hilbert码和R^*树进行融合以发挥各自特点的必要步骤。

1.1   Hilbert码生成

本文的Hilbert码生成方法的原理来自于文献[21]。该方法的特点是采用自下而上的方式生成Hilbert码，并且在生成编码的过程中不断复用若干基本模板基因，以达到快速生成特定位置对应Hilbert曲线编码的目的。本文的模板基因是指构成特定维度和迭代次数Hilbert曲线的基本空间走向单元。此过程的原理参见图 4和图 5。图 4中，C³代表最基本的三维Hilbert曲线模板基因，X₁$\leftrightarrow $X₃是指X₁坐标轴和X₃坐标轴互换之后的模板基因，X₂$\leftrightarrow $X₃是指X₂坐标轴和X₃坐标轴互换之后的模板基因，X₁$\leftrightarrow $X₃∩X'₁, X'₃是指X₁坐标轴和X₃坐标轴互换，且X₁和X₃坐标各自求反的模板基因，X₂$\leftrightarrow $X₃∩X'₂, X'₃是指X₂坐标轴和X₃坐标轴互换，且X₂和X₃坐标各自求反的模板基因。图 5则描述了使用1次迭代基因模板生成2次迭代三维Hilbert曲线的过程。表 1展示了1次迭代三维Hilbert曲线编码生成基本模板。

图  4  三维Hilbert曲线编码生成模板基因展示

Figure  4.  Diagram of Template for Generating Hilbert Curve Code Gene in 3-Dimensional Space

下载: 全尺寸图片 幻灯片

图  5  使用1次迭代基因模板生成2次迭代三维Hilbert曲线展示

Figure  5.  Diagram of Utilizing One Iteration Hilbert Curve to Encode Two Iterations in 3-Dimensional Space

下载: 全尺寸图片 幻灯片

表  1  利用1次迭代三维Hilbert曲线编码生成基本模板列表

Table  1.  Template for Generating Hilbert Curve Code in 3-Dimensional Space

位置	0号点	1号点	2号点	3号点	4号点	5号点	6号点	7号点
0	000	001	011	010	110	111	101	100
1	000	100	101	001	011	111	110	010
2	000	100	110	010	011	111	101	001
3	101	100	110	111	011	010	000	001
4	000	001	011	010	110	111	101	100
5	000	100	110	010	011	111	101	001
6	011	111	110	010	000	100	101	001
7	101	100	110	111	011	010	000	001

下载: 导出CSV 

| 显示表格

1.2   Hilbert码与R^*树的集成

Hilbert码需要和R^*树进行深度整合，才能在空间相关操作中体现出引入Hilbert遍历曲线的优势。这就要求在R^*树的插入和删除节点相关的操作中引入对于Hilbert码的生成和更新，涉及到插入节点、拆分节点和删除节点3个核心算法。其中，插入节点算法负责将当前空间对象插入合适的叶节点中；拆分节点则是当前节点所容纳的对象数量多于设置上限时，需要将当前节点拆分为多个节点的操作；删除节点则是将所需删除空间对象从R^*树中删除。

以上3个R^*树的核心操作中，在引入Hilbert码之后都需要进行适当的修改，其中最为关键的是在插入空间对象时选择节点。该算法描述如下:

输入：待插入空间对象，涉及的空间节点和内部包含对象。

输出：插入后的空间节点。

处理过程：

1) 检索当前节点的子对象数目，如果该数目小于预设值上限，则继续检索，否则结束；

2) 如果待插入对象的Hilbert码小于当前节点包含对象的最小Hilbert码，那么将待插入对象插入节点包含对象列表的最前端，结束；

3) 如果待插入对象的Hilbert码大于当前节点包含对象的最大Hilbert码，那么将待插入对象插入节点包含对象列表的最后端，结束；

4) 遍历当前节点包含的对象列表，如果发现待插入对象的Hilbert码位于列表里的两个对象的Hilbert码之间，那么将其插入此位置，结束。

2 空间操作实验与数据分析

2.1   实验场景与结果展示

实验场景选择的是河南城建学院5号教学楼，该教学楼分为A座、B座和C座3个教学功能区，分别对应该教学楼的实验室区、办公区和教学区。这些功能区通过位于东西两侧的两个长风雨走廊相连。建筑的数据源是平面设计图纸(见图 6)。在图 6中使用1号图框标示的范围是B座东侧楼梯区域，针对该区域的空间对象查询操作模拟应急疏散情况下对于室内人员位置的查询；被3个2号图框所圈定的范围是B座二层的3间办公室，针对该区域的空间对象删除操作则是模拟火灾发生情况下，由于灾害阻挡作用导致的对室内通行空间的删除；被2个3号图框所圈定的范围是B座三层的两间办公室南侧窗户外的邻近空间，针对这两块通行空间的插入是模拟消防人员通过架设云梯的方式新增建筑物邻近通行空间的场景。

图  6  实验建筑的平面设计图展示

Figure  6.  Illustration of Experiment Building by 2D Floor Plan

下载: 全尺寸图片 幻灯片

针对建筑物的空间对象操作实验, 除了以上提到的针对指定范围的空间对象查询、删除和插入，还包括对于完整索引树的遍历。这些空间操作由于单位耗时较短，所以本文展示的实验结果是将其重复10 000次所得的总时间耗费。

2.2   结果分析与讨论

图 7展示的是依照Hilbert编码升序遍历R^*树的曲线，从中能够看出该树在遍历过程中优先经过邻近空间对象。这种依照Hilbert码组织空间索引的R^*树在表 2的数据中将空间操作效能优势进行了充分发挥。从表 2中可以看出, 通过引入Hilbert遍历曲线，在全树遍历过程中，引入Hilbert曲线的R^*树相比于普通R^*树时间节省了43.34%；在查询特定空间对象的过程中, 时间节省了47.15%；而在删除操作中，时间更是节省了70.91%。但是，引入Hilbert曲线也有副作用：在插入操作中，由于需要进行较为庞杂的空间坐标向Hilbert码的转化，因此引入Hilbert曲线的R^*树相比于普通R^*树时间耗费增加了70倍。

图  7  依照Hilbert码排序的实验建筑的R^*树遍历曲线展示

Figure  7.  Demonstration of Traversing Lines Sorted by Hilbert Code for Nodes in R^* Tree for Experiment Building

下载: 全尺寸图片 幻灯片

表  2  引入Hilbert曲线编码对于R^*树的10 000次关键空间操作的效果展示表

Table  2.  Time Cost for Introducing Hilbert Curve to R^* Tree on Spatial Operations

对比项目	Hilbert R*树索引/s	R*树索引/s	Hilbert引入效果/%
全树遍历	4.236 207	7.477 665	-43.34
查询	4.073 165	7.706 982	-47.15
删除	0.049 924	0.171 622	-70.91
插入	3.723 421	0.052 240	+7 027.53

下载: 导出CSV 

| 显示表格

但是不能简单地认为由于引入Hilbert曲线的R^*树在插入对象操作上的时间耗费过大，就不适用于室内位置相关的应用。由于在针对室内位置相关的空间应用中，绝大多数操作都是空间位置查询和删除操作，而插入操作一般都是在初始化室内场景的过程中或者是极少数的新增通行空间的场景中(如引入消防云梯这种较为罕见的场景), 所以引入Hilbert曲线的R^*树在查询操作上的优势能够弥补其在插入操作上的劣势。此外，针对Hilbert码的生成优化算法也一直在进步，引入Hilbert曲线对于R^*树插入操作的负面影响也会得到有效遏制。总体来看，引入Hilbert曲线对于R^*树这类空间索引利大于弊。

3 结语

因为Hilbert曲线具有针对遍历空间对象的良好空间局部性的特点，所以引入该曲线能够提高R^*树针对空间邻近对象的相关操作效率，即可以显著提升针对全树的对象遍历、查询和删除操作效率。虽然在引入Hilbert曲线后，由于生成Hilbert码的复杂运算的影响会导致对象插入效率的下降，但是在进行针对Hilbert码的生成优化之后，可以降低这种负面影响。未来的研究方向有两个：

1) 针对多级索引的Hilbert码动态扩展，可以满足针对更加精确坐标和基本单元扩展的Hilbert编码扩展需求。

2) 以降低运算复杂度为目的的Hilbert算法的精简和优化，能够在运算时间受限的情况下快速得到可接受精度的Hilbert编码。