移动导航电子地图数据结构设计

移动导航电子地图数据结构设计和特殊数据表示方法目录CONTENTS二、特殊数据表示方法一、数据结构一、数据结构交通网络中道路网是移动导航电子地图数据中最为重要的内容，也是路径规划、路径引导、地图匹配等功能实现的基础。它的基本元素可以抽象为点、线、面，在连续欧氏空间中，点为零维元素、线为一维元素、面为二维元素。为实现实时的路径搜索与信息查询功能，点、线之间需要具有简单的拓扑关系，因此,整个地图平面可视为点、线组成的网络，而面由封闭的线段组成。数据结构具体说来，移动导航电子地图数据可抽象为：（1）节点：表示空间对象所在的位置，或者线段的起始、终止点，它具有特定的拓扑性质。（2）孤立点：表示线、面经过的点，不具有拓扑性质。（3）线（弧线）：起始与终止点为节点，并且具有若干孤立点的有序点集。（4）面：由若干弧线相连的封闭曲线围成的区域称为面。面以弧线的形式表示，但通过编码与弧线区别，且其内部填充方式可以设置。包含以上数据的电子地图数据结构称为面向弧线的数据结构，其图形文件有ARC,NOD,IDX等三种。数据结构ARC文件既包括了弧线的几何参数，也包括弧线与节点、弧线与弧线之间的拓扑关系，其数据格式为：数据结构ARC_IDCODEFrom_NODTo_NODHead_ARCTail_ARCPoint_Number（x,y）坐标串ARC_ID弧线标示号；CODE弧线编码；From_NOD起始节点；To_NOD终止节点；Head_ARC指向弧线起始节点的下一弧线（入弧线）；Tail_ARC以弧线终止节点为起点的下一弧线（出弧线）；Tail_ARC弧线包含的点数；（x,y）坐标串各点的空间坐标。NOD文件表示了节点的几何参数及节点与弧线的拓扑关系，通过节点标示号，还可实现节点与非空间数据的链接，其数据格式为:数据结构NOD_IDIN_ARCOUT_ARC(x,y)NOD_ID节点标示号；IN_ARC以该节点为终止的第一条弧线（入弧线）；OUT_ARC以该节点为起始的第一条弧线（出弧线）；(x,y)该节点的空间坐标。IDX文件表示地图中路的映射。一条路由若干条弧线构成，通过IDX文件可以进行索引，同时Key_Item可用于实现与非空间数据的链接，其数据格式为:数据结构Key_ItemARC_NumberARC_1ARC_2.......Key_Item道路名称ARC_Number包括的弧线数ARC_1第一条弧线的标示号ARC_2第二条弧线的标示号图1为点、线、面组成的某地图区域，其中A、B、C为节点，D、E为孤立点，AB,BC,ADC,ADB,CEA,BDC为四条弧线,对应于该地图的面向弧线的数据结构文件分别见表1至表3。数据结构设计图1面向弧线的地图表数据结构设计表1ARC文件数据结构ARC_IDCODEFrom_NODTo_NODHead_ARCTail_ARCPoint_Number(x,y)坐标串AB0ABCEABC2(xA,yA)(xB,yB)BC1BCADBCEA2(xB,yB)(xC,yC)ADC2ACCEACEA3(xA,yA)(xD,yD)(xC,yC)ADB3ABCEABC3(xA,yA)(xD,yD)(xB,yB)CEA4CAADCAB3(xC,yC)(xE,yE)(xA,yA)BDC5BCABCEA3(xB,yB)(xD,yD)(xC,yC)数据结构设计表2NOD文件数据结构NOD_IDIN_ARCOUT_ARC(x,y)ACEAAB(xA,yA)BABBC(xB,yB)CADCCEA(xC,yC)数据结构设计表3IDX文件数据结构Key_ItemARC_NumberARC_1ARC_2Road12ABBCRoad22ADCCEA二、特殊数据表示方法一、项目概况现代交通网发展越来越完善，复杂度也越来越大。在交通网中进行最短路径査询，不同于一般简单有向拓扑网中的最短路径查询，它有其特殊性：特殊数据表示方法道路分级别高等级道路(高速公路、国道等)的通行条件好，速度快；低等级道路(街道、乡村路等)的通行条件差，速度慢，还有其他等级的道路通行状况好坏各不相同。一、项目概况道路有通行条件:

很多道路是单向通行的，且很多高等级道路以隔离带划分为两条道路，均是单向通行，在拓扑网中表现为有向性。不仅如此还有其他限制。特殊数据表示方法一、项目概况道路交叉点有限制条件:

交通网在道路交叉点处有各种各样的规制条件，最为常见的就是禁止向左转弯，如图1所示转弯(1-0-2)是禁止的，所以在计算最短路径时不能从道路(1-0)转到道路(0-2)。有时并没有交通规制说向哪里转弯不行，但是有潜在的禁止转弯规制。比如图2，图中箭头表示单向通行方向。特殊数据表示方法图1禁止转图2单向通一、项目概况道路交叉点有限制条件：

针对上述现实道路网中的特殊性，要实现移动导航电子地图系统，首先要建立仿真的交通道路网络拓扑模型，并且能对海量数据进行道路最短路径计算。特殊数据表示方法图3转弯规则特殊数据表示方法在表中，特殊转弯规则编码指的是对通行时间、通行车辆的限制，通过该编码在另外一张数据表中就可以查到该通行限制。自节点邻节点道路等级距离