《表3 地图数据细节Tab.3 Map data details》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《基于八叉树的三维室内地图数据快速检索方法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

本文以Sketch Up与Arc GIS文件作为实验的数据，如图5所示，物体A与物体B为三维室内地图，具体细节参见表3所示。根据Namdari等[15]和王永志等[16]的分析得出，当不采用任何数据结构与搜索方法对三维室内地图进行搜索时，搜索的时间复杂度是O（np），其中n为数据的个数，p为目标数据周围有用数据的个数。付仲良等[17]指出当仅采用八叉树划分法对实验数据进行标准划分，而不采用任何搜索方法，由于经典八叉树无法找到邻居地址，所以此时搜索的时间复杂度是O（23 （L-1）） ，其中L为树的深度。肖怡等[18]指出当采用八叉树划分，并采用Schrack[14]提出的搜索算法时，搜索的时间复杂度为O（L）。当采用八叉树数据结构进行划分，并采用Aizawa等[4]所提出的邻居搜索算法进行搜索，由于其利用八叉树划分的规则性特点，可以通过公式计算出目标数据周围最多26个邻居地图数据，这能够满足地图应用中，对于目标地图数据的周围数据进行呈现的需求，即“搜一点，遍及周围”的情况，这会减少对于地图数据的搜索次数，这种应用背景下的搜索时间复杂度会保持在O（1）。同理若采用本文提出的带房间约束条件的邻居搜索方式进行物体的搜索，则搜索的时间复杂度也是O（1），因此采用八叉树结构的邻居搜索方式对室内地图数据搜索进行改善，在时间复杂度上有所降低，且不会随着树的深度的增加而变得更复杂。