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

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

目前,我们通常所能拿到的城市地图数据,主要是POI(point of interest)点和道路线数据,为了更好地支持空间关系的查询,为此我们需要建立点与线、线与线之间拓扑关联关系。

中山路
中山路
中山路
珠江路
珠江路
珠江路
珠江路
长江路
长江路
长江路
长江路
鱼市街
进香河路
洪武北路
太平北路
太平北路
太平北路
POI点与线道路示意图

一、 解决方案设计
分析以上这些需求，主要涉及到点与线、线与线之间的拓扑关联关系，至于点与点关系，可以通过以上关系推导出。
1) 点与线的绑定关联
目前城市地图，大都采集道路边上的重要POI点，也就表明POI点与道路有着直接的绑定关联关系，所以，需要在这两者之间建立起这种绑定关系。具体模型如下：

点线拓扑数据的文件结构以及索引结构,待定.
2) 线与线的关联关系
道路拓扑关系，这里不面向车载导航，主要是满足步行和自行车行人的引导需求，道路拓扑存储为”无向图”，不考虑道路转向限制以及红绿灯等待情况。
1
2
4
3
5
9
15
10
6
8
17
7

1
2
3
4
5
2
9
4
15
5
7
1
9

5
17
3
8
2
8
4
10
4
6

3
10
1
15
5
6
1
7
2
17

道路无向图邻接表数据结构

由arc表和node表建立道路网的拓扑结构,索引结构将依据node建立网格索引,拓扑邻接表数据结构将依据这个网格索引来存储道路网拓扑数据,依然按照
Hilbert顺序存储.同时此网格索引还将用于道路网子图的生成,为什么需要生成子图,理由有两个:1,求最短路径,只需要涉及到部分节点和边,也就是需要提取的子图范围;2,子图范围小,运算规模将会很小,有利于提高最短路径算法的效率.
子图生成算法,通过空间索引,确定起点到终点之间大概包含的node节点的子集,再由这个子集,从整个道路拓扑结构图中,提取出只与子集中节点相关的边,即可生成一个子的邻接表数据.

二、 数据处理需求
1) 弧段的处理
普通道路依据交叉口打断,这里需要考虑高架、隧道和地铁的特殊情况，依据实际情况，需进行特别处理，以符合交通的实际情况。
保持整个系统id，全局一致

原始概念意义下的道路id
保持整个系统id,全局一致
原始概念意义下的道路name
弧段id
关联的节点node1_id
关联的节点node2_id
被横截道路名称node1_raodname
被横截道路名称node2_raodname
节点相对方向node1_direction
节点相对方向node2_direction
用于路径权值
弧段长度arc_length

2) 节点的处理
节点只需要node_id 即可。

三、 需要生成的文件
经过一系列数据处理，需要生成满足应用需求的、运行在手机上的各种文件，这里主要包括的文件有：
1) 点线拓扑数据 .plt(point line topology)，主要用于存储“原始道路”——“弧段”——“POI点”之间的拓扑关系。从整个文件的排列顺序来看，以原始道路来组织，为了顾及到I/O数据存取这一块的性能——空间邻近、存储邻近，这里采用“四叉树+Hilbert排序”的策略来安排文件的总体顺序。（四叉树，可以在保持原始道路不被切割或者打断情况下完整的索引，Hilbert顺序能保持空间聚簇，特别注意的是，这里的四叉树是建立在“概念意义下的道路”上的空间索引）
2) 点线拓扑数据的索引 .plti(point line topology index)，该索引由一个int型变量（实际线在.plt文件中的实际偏移量）、两个byte型变量。对于POI点来说，两个byte型变量分别为该POI点所属弧段在实际线中的编号和该POI点在弧段中的编号；对于实际线来说，后两个byte型变量为均为-1。此索引存放在字典的叶子节点中（说明：两个序号是相对的，比如：一个实际线中中含有8个弧段，第二个弧段含有10个POI点，那么第二个弧段的第2个POI点的索引＝实际线的实际偏移地址＋(byte)2＋(byte)2）
3) 线线拓扑数据，即“道路网”.llt(line line topology),存储整个城市道路网拓扑数据，采用“图”邻接表的方式存储，是在“弧段——节点”拓扑关系基础上建立的。文件的存储顺序按“节点node网格索引+Hilbert排序”的方式来组织。
4) 线线拓扑数据的索引，.llti(line line topology index),按照节点顺序存储每个节点在.llt文件中的实际偏移量，此索引在手机中被一次性全部加载。
5) 弧段坐标数据，.lco(line coordnate),存储弧段坐标序列，主要用于显示系统，显示重画道路数据，以高亮突出显示道路。本文件不可以存储在“点线拓扑数据”中，因为在最短路径重画中，需要单独用到，需单独保存，文件存储顺序按弧段id顺序存储。文件的存储顺序按“节点node网格索引+Hilbert排序”的方式来组织。
6) 弧段坐标数据的索引，.lcoi(line coordinate index),按id顺序存储，查找可采用一维数组直接定位的方式即可。既然按弧段id来查找弧段坐标数据，就要求在“道路网”数据中，加入节点到节点的弧段id信息，即在权重后面多加一个弧段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) 查询任意两POI点之间的最短路径。输入：任意两点；输出：它们之间的路径及距离。
5) 查询附近本路段以及附近路段上有哪些POI点。本查询属于“查找周边”，输入：任意一点或者配合相关属性查找；输出：此点“附近”符合查找条件的POI点。需要借助“道路图”查找相邻路段上绑定的POI点。