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

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

2、条弧段卩以绑定的皿i点的数据-这里的d与显示系统的制一致 -弧禺饶于关联那段的坐标 旳坟件中的编号 node1_nam node2_name 为此磁两头彼截il嘶名称 nodck nodo2相对方冋育八个 nodel 2北2坐标作分最短路连 搜索中，貝断从哪头节点起葬， 师提取子图的需要 垂足坐标xt.yt以及坐标序列n 舄于路径的显示同盯口配合 弧段的相对方冋可阳于两 节也方耳关系、距嚮关揺前 判断以i点与道躍线拓扑关系模勺点线拓扑数据的文件结构以及索引结构，待定2）线与线的关联关系532941519517382841031011517，2175646道路拓扑关系，这里不面向车载导航，主要是

3、满足步行和自行车行人的引导需 求，道路拓扑存储为”无向图”不考虑道路转向限制以及红绿灯等待情况。4545道路无向图邻接表数据结构45由arc表和node表建立道路网的拓扑结构，索引结构将依据node建立网格索引 拓扑邻接表数据结构将依据这个网格索引来存储道路网拓扑数据，依然按照Hilbert顺序存储侗时此网格索引还将用于道路网子图的生成，为什么需要生成子图，理由有两个:1,求最短路径，只需要涉及到部分节点和边，也就是需要提取的子图范围；2,子图范围小，运算规模将会很小，有利于提高最短路径算法的效 率子图生成算法，通过空间索引，确定起点到终点之间大概包含的node节点的子集,再由这个子集，从整个

4、道路拓扑结构图中，提取出只与子集中节点相关的边 即可生成一个子的邻接表数据、数据处理需求1）弧段的处理普通道路依据交叉口打断，这里需要考虑高架、隧道和地铁的特殊情况，依据 实际情况，需进行特别处理，以符合交通的实际情况。保持整个系统id,全局一致原始概念意义下的道路id一A原始概念意义下的道路 n ame弧段id保持整个系统id,全局一致关联的节点node1d关联的节点node2_id被横截道路名称 n ode1 raod name被横截道路名称 n ode2 raod name节点相对方向 no de1 direct ion节点相对方向 no de2 direct ion弧段长度arc le

5、ngth*用于路径权值2）节点的处理节点只需要node_id即可。、需要生成的文件经过一系列数据处理，需要生成满足应用需求的、运行在手机上的各种文件，这里 主要包括的文件有：1）点线拓扑数据.pinpoint line topology），主要用于存储"原始道路”"弧段” 一一“ POI点”之间的拓扑关系。从整个文件的排列顺序来看，以原始道 路来组织，为了顾及到I/O数据存取这一块的性能一一空间邻近、存储邻近，这里采用“四叉树+Hilbert排序”的策略来安排文件的总体顺序。（四叉树，可以在保持原始道路不被切割或者打断情况下完整的索引，Hilbert顺序能保持空间聚簇，特别

6、注意的是，这里的四叉树是建立在“概念意义下的道路”上的空间索引）2）点线拓扑数据的索引.plti（point line topology index），该索引由一个int型变量（实际线在.pit文件中的实际偏移量）、两个byte型变量。对于POI点来说，两个byte型变量分别为该POI点所属弧段在实际线中的编号和该POI点在弧段中的编号；对于实际线来说，后两个 byte型变量为均为-1。此索引存放在 字典的叶子节点中（说明：两个序号是相对的，比如：一个实际线中中含有8个弧段，第二个弧段含有 10 个 POI 点，那么第二个弧段的第 2 个 POI 点的索 引=实际线的实际偏移地址+(byte)

7、2 + (byte)2)3) 线线拓扑数据，即“道路网” .llt(line line topology), 存储整个城市道路网拓扑 数据，采用“图”邻接表的方式存储，是在“弧段节点”拓扑关系基础上 建立的。文件的存储顺序按“节点 node 网格索引 +Hilbert 排序”的方式来组 织。4) 线线拓扑数据的索引， .llti(line line topology index), 按照节点顺序存储每个节 点在 .llt 文件中的实际偏移量，此索引在手机中被一次性全部加载。5) 弧段坐标数据， .lco(line coordnate), 存储弧段坐标序列，主要用于显示系统， 显示重画道路数据，

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

9、信息的索引，还需要加入“弧段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) 查询