城市地图拓扑数据的存储与应用

1、城市地图拓扑数据的存储与应用目前,我们通常所能拿到的城市地图数据,主要是POI(point of interest)点和道路线数据,为了更好地支持空间关系的查询,为此我们需要建立点与线、线与线之间拓扑关联关系。中山路中山路中山路珠江路珠江路珠江路珠江路长江路长江路长江路长江路鱼市街进香河路洪武北路太平北路太平北路太平北路POI点与线道路示意图一、 解决方案设计分析以上这些需求，主要涉及到点与线、线与线之间的拓扑关联关系，至于点与点关系，可以通过以上关系推导出。1) 点与线的绑定关联目前城市地图，大都采集道路边上的重要POI点，也就表明POI点与道路有着直接的绑定关联关系，所以，需要在这两者之间

2、建立起这种绑定关系。具体模型如下： 点线拓扑数据的文件结构以及索引结构,待定.2) 线与线的关联关系道路拓扑关系，这里不面向车载导航，主要是满足步行和自行车行人的引导需求，道路拓扑存储为”无向图”，不考虑道路转向限制以及红绿灯等待情况。124359151068177 123452941557195173828410463101155617217道路无向图邻接表数据结构 由arc表和node表建立道路网的拓扑结构,索引结构将依据node建立网格索引,拓扑邻接表数据结构将依据这个网格索引来存储道路网拓扑数据,依然按照 Hilbert顺序存储.同时此网格索引还将用于道路网子图的生成,为什么需要生成子

3、图,理由有两个:1,求最短路径,只需要涉及到部分节点和边,也就是需要提取的子图范围;2,子图范围小,运算规模将会很小,有利于提高最短路径算法的效率. 子图生成算法,通过空间索引,确定起点到终点之间大概包含的node节点的子集,再由这个子集,从整个道路拓扑结构图中,提取出只与子集中节点相关的边,即可生成一个子的邻接表数据.二、 数据处理需求1) 弧段的处理普通道路依据交叉口打断,这里需要考虑高架、隧道和地铁的特殊情况，依据实际情况，需进行特别处理，以符合交通的实际情况。保持整个系统id，全局一致原始概念意义下的道路id保持整个系统id,全局一致原始概念意义下的道路name弧段id关联的节点nod

4、e1_id关联的节点node2_id被横截道路名称node1_raodname被横截道路名称node2_raodname节点相对方向node1_direction节点相对方向node2_direction用于路径权值弧段长度arc_length2) 节点的处理节点只需要node_id 即可。三、 需要生成的文件经过一系列数据处理，需要生成满足应用需求的、运行在手机上的各种文件，这里主要包括的文件有：1) 点线拓扑数据 .plt(point line topology)，主要用于存储“原始道路”“弧段”“POI点”之间的拓扑关系。从整个文件的排列顺序来看，以原始道路来组织，为了顾及到I/O数据存

5、取这一块的性能空间邻近、存储邻近，这里采用“四叉树+Hilbert排序”的策略来安排文件的总体顺序。（四叉树，可以在保持原始道路不被切割或者打断情况下完整的索引，Hilbert顺序能保持空间聚簇，特别注意的是，这里的四叉树是建立在“概念意义下的道路”上的空间索引）2) 点线拓扑数据的索引 .plti(point line topology index)，该索引由一个int型变量（实际线在.plt文件中的实际偏移量）、两个byte型变量。对于POI点来说，两个byte型变量分别为该POI点所属弧段在实际线中的编号和该POI点在弧段中的编号；对于实际线来说，后两个byte型变量为均为-1。此索引存

6、放在字典的叶子节点中（说明：两个序号是相对的，比如：一个实际线中中含有8个弧段，第二个弧段含有10个POI点，那么第二个弧段的第2个POI点的索引实际线的实际偏移地址(byte)2(byte)2）3) 线线拓扑数据，即“道路网”.llt(line line topology),存储整个城市道路网拓扑数据，采用“图”邻接表的方式存储，是在“弧段节点”拓扑关系基础上建立的。文件的存储顺序按“节点node网格索引+Hilbert排序”的方式来组织。4) 线线拓扑数据的索引，.llti(line line topology index),按照节点顺序存储每个节点在.llt文件中的实际偏移量，此索引在手

7、机中被一次性全部加载。5) 弧段坐标数据，.lco(line coordnate),存储弧段坐标序列，主要用于显示系统，显示重画道路数据，以高亮突出显示道路。本文件不可以存储在“点线拓扑数据”中，因为在最短路径重画中，需要单独用到，需单独保存，文件存储顺序按弧段id顺序存储。文件的存储顺序按“节点node网格索引+Hilbert排序”的方式来组织。6) 弧段坐标数据的索引，.lcoi(line coordinate index),按id顺序存储，查找可采用一维数组直接定位的方式即可。既然按弧段id来查找弧段坐标数据，就要求在“道路网”数据中，加入节点到节点的弧段id信息，即在权重后面多加一个弧

8、段id信息，这样有助于最短路径的重画高亮显示；为了从弧段id到 点线拓扑数据的弧段信息的索引，还需要加入“弧段id点线拓扑数据中 弧段”索引。7) 图节点坐标数据，.nco(node coordinate),按id顺序存储，不需要索引。四、 应用需求人们对空间关系有着各种各样的认识和需求，我们需要用计算机来存储和刻画这种关系，满足人们的需求。具有有哪些需求呢？1) 查询某个POI点位于某条路的哪个路段上。输入：POI点name或者点选POI点；输出：POI点所绑定的路段，及此路段的两头被哪两条线打断。2) 查询某个POI点距离这条路段两头节点的大概长度。输入：POI点name或者点选POI点；输出：POI点到路段两头的距离。3) 查询同一条路上，两个不同POI之间方向、距离关系。输入：两个POI点的name或者点选；输出：两POI点的方向、距离关系。注：两个POI点位于同一概念意义的路上，但可能不是同一路段，需要推理它们之间的方向关系。4) 查询任意两P