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

POI点与线道路示意图
一、解决方案设计
分析以上这些需求，主要涉及到点与线、线与线之间的拓扑关联关系，至于点与点
关系，可以通过以上关系推导出。

1)点与线的绑定关联
目前城市地图，大都采集道路边上的重要POI点，也就表明POI点与道路有
着直接的绑定关联关系，所以，需要在这两者之间建立起这种绑定关系。

具体
模型如下：
点线拓扑数据的文件结构以及索引结构,待定. 2) 线与线的关联关系
道路拓扑关系，这里不面向车载导航，主要是满足步行和自行车行人的引导需求，道路拓扑存储为”无向图”，不考虑道路转向限制以及红绿灯等待情况。

1 3 5
道路无向图邻接表数据结构
由arc表和node表建立道路网的拓扑结构,索引结构将依据node建立网格索引,
拓扑邻接表数据结构将依据这个网格索引来存储道路网拓扑数据,依然按照
Hilbert顺序存储.同时此网格索引还将用于道路网子图的生成,为什么需要生成
子图,理由有两个:1,求最短路径,只需要涉及到部分节点和边,也就是需要提取
的子图范围;2,子图范围小,运算规模将会很小,有利于提高最短路径算法的效
率.
子图生成算法,通过空间索引,确定起点到终点之间大概包含的node节点的子
集,再由这个子集,从整个道路拓扑结构图中,提取出只与子集中节点相关的边,
即可生成一个子的邻接表数据.
二、数据处理需求
1)弧段的处理
普通道路依据交叉口打断,这里需要考虑高架、隧道和地铁的特殊情况，依据
实际情况，需进行特别处理，以符合交通的实际情况。

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点。