导航电子地图中道路网络拓扑分区的方法及装置

暂无

导航电子地图中道路网络拓扑分区的方法及装置\n技术领域\n[0001] 本发明属于导航技术领域，尤其涉及一种导航电子地图中道路网络拓扑分区的方法及装置。\n背景技术\n[0002] 随着卫星导航应用的快速发展，导航电子地图作为整个导航应用体系中的核心组成部分，越来越受到关注和重视。良好的数据格式和数据结构模型直接影响着导航电子地图的应用程度。\n[0003] 现有的导航电子地图中道路网络的数据量往往非常庞大，而导航应用的硬件环境是受限的，将道路网络的数据全部读入内存是不现实的，因此在地理信息系统中，可应用拓扑分区方法将一个较大的地理区域按地理位置或道路网络的疏密分成多个区，每个区还可划称为多个格网，其中任意一个拓扑分区都以若干个格网为核心，而且还可进行适当的扩展。在Kiwi(日系汽车导航物理编译格式)规格中定义了一种拓扑分区方法，Kiwi规格是日本Kiwi联盟制定的汽车导航数据标准。Kiwi是按分层结构来组织地图的，并且这种层的逻辑结构与其物理存储也是相联系的，它可以在不同的层之间做快速的数据引用，即在任意一个网为核心的拓扑分区中，在该分区范围内可通过与上层道路的连接点属性向上一层切换，由于存在多个连接点，因此该分区是一个范围远大于核心格网的多边形区域。因此在该分区模型中，道路网络的拓扑分区不是常规的矩形，而是多边形，从而会导致不同的拓扑分区所存储的实际路网数据存在冗余。\n[0004] 在实现本发明的过程中，发现现有技术中至少存在如下问题：现有的数据存储方式中数据冗余度大，在以Kiwi为代表的现有技术中，将拓扑分区定义为一个范围远大于核心格网的多边形区域。而且，拓扑分区需要同时存储扩展部分的道路数据和核心格网部分的道路数据，由于存储扩展部分的道路数据会重复存储，也就是通常所说的数据冗余，因此增加了维护人员在导航电子地图的维护过程中的工作量。\n发明内容\n[0005] 为了解决上述问题，本发明的目的是提供一种导航电子地图中道路网络拓扑分区的方法及装置，可有效减少在导航电子地图中道路数据存储过程中所产生的冗余数据。\n[0006] 为了达到上述目的，本发明提供一种导航电子地图中道路网络拓扑分区的方法，所述方法包括：\n[0007] 步骤A、获取所述导航电子地图中道路网络的原始路网数据，并将获取的所述原始路网数据划分为多个格网；\n[0008] 步骤B、基于道路的功能等级，分别设定所述多个格网中道路的拓扑等级；\n[0009] 步骤C、以每个格网为核心格网，从所述核心格网的边界的低拓扑等级的道路出发进行路径扩展；\n[0010] 步骤D、通过遍历路径扩展所经过的其他格网得到拓扑扩展分区，所述拓扑扩展分区保证路径搜索数据分区层间的拓扑连通性；\n[0011] 步骤E、存储所述核心格网中的道路数据，并在拓扑分区管理数据中通过索引数据记录所述拓扑扩展分区的格网列表；\n[0012] 重复步骤C～步骤E的处理流程，直到所述多个格网作为核心格网获取拓扑扩展分区的过程全部处理完毕。\n[0013] 优选地，当需要应用所述道路网络中的道路数据时，所述方法还包括：\n[0014] 根据所述拓扑分区管理数据中提供的所述格网列表的索引数据，读取所述拓扑扩展分区中的道路数据。\n[0015] 优选地，存储所述核心网中的道路数据的步骤具体为：\n[0016] 根据所述格网中道路的拓扑等级，将所述格网中的道路数据分块存储。\n[0017] 优选地，将所述格网中的道路分块存储的步骤包括：\n[0018] 按所述拓扑等级重新组织格网中道路数据的信息，所述道路数据的信息包括：道路的节点信息、弧段信息、或者复合节点信息；\n[0019] 将相同的拓扑等级的道路数据保存在同一数据块中。\n[0020] 优选地，将获取的所述原始路网数据划分为多个格网的步骤为：\n[0021] 以预定角度的经度线和纬度线作为边界将所述原始路网数据划分为多个格网；或者\n[0022] 以基准点的东西轴和南北轴的平行线为边界将所述原始路网数据划分为多个格网。\n[0023] 优选地，所述原始路网数据按导航电子地图的物理存储格式PSF规格，设置成层-区集-区-格网四级结构进行管理，其中每一层的道路数据通过区集进行管理，所述区集划分为多个不同的区，所述区保护实际拥有道路数据的格网。\n[0024] 优选地，所述方法还包括：\n[0025] 将所述每一层的道路数据进行分割处理或者合并处理，所述格网为处理后的分割格网或者统合格网。\n[0026] 优选地，所述道路的功能等级包括：城际道路和城市道路，其中所述城际道路包括：高速公路、国道、省道、县道和乡道；所述城市道路包括：城市快速路、主干道、次干道和支路。\n[0027] 优选地，所述方法还包括：\n[0028] 根据所述格网中道路的连通性、封闭性和最优性，来调整所述道路的拓扑等级。\n[0029] 优选地，所述道路的最优性为以任意一对道路作为出发地和目的地，在由拓扑等级不低于所述一对道路所组成的网络中规划最优路径。\n[0030] 本发明还提供一种导航电子地图道路网络拓扑分区的装置，所述装置包括：\n[0031] 划分模块，用于获取所述道路网络中的原始路网数据，将获取的所述原始路网数据划分为多个格网；\n[0032] 拓扑等级划分模块，用于基于道路的功能等级，分别设定所述多个格网中道路的拓扑等级；\n[0033] 路径扩展模块，用于以每个格网为核心格网，从所述核心格网的边界的低拓扑等级的道路出发进行路径扩展；\n[0034] 遍历模块，用于通过遍历路径扩展所经过的其他格网得到拓扑扩展分区，所述拓扑扩展分区保证路径搜索数据分区层间的拓扑连通性；\n[0035] 存储模块，用于存储所述核心格网中的道路数据，并在拓扑分区管理数据中通过索引数据记录所述拓扑扩展分区的格网列表。\n[0036] 优选地，所述装置还包括：\n[0037] 读取模块，用于根据所述拓扑分区管理数据中提供的所述格网列表的索引数据，读取所述拓扑扩展分区中的道路数据。\n[0038] 优选地，所述道路的功能等级包括：城际道路和城市道路，其中所述城际道路包括：高速公路、国道、省道、县道和乡道；所述城市道路包括：城市快速路、主干道、次干道和支路。\n[0039] 优选地，所述拓扑等级划分模块包括拓扑等级调整单元，根据所述格网中道路的连通性、封闭性和最优性，来调整所述道路的拓扑等级。\n[0040] 上述技术方案中的至少一个技术方案具有如下有益效果：通过只存储核心格网中的道路数据，而对扩展部分的道路数据不重复存储，并对扩展部分的道路数据采用数据间接索引的方法，通过一系列格网列表的方式记录在分区管理数据中，应用时只需根据分区管理数据提供的索引来读取该道路数据，而并不需要重复记录这些区域中的道路数据，从而可有效减少导航电子地图中道路数据实际存储所占的容量，并且还可提供分区内道路的跟踪和导航服务，并可应用于按需下载和增量更新应用模式的实现。\n附图说明\n[0041] 图1为本发明的实施例中网络拓扑分区的方法流程图；\n[0042] 图2为本发明的实施例中单层区集、区和格网的平面示意图；\n[0043] 图3为本发明的实施例中原始路网数据预处理的流程图；\n[0044] 图4a、4b为本发明的实施例中从核心格网出发的最优路径扩展示意图；\n[0045] 图5为本发明的实施例中拓扑扩展分区的示意图；\n[0046] 图6为本发明的实施例中完成拓扑扩展分区的流程图；\n[0047] 图7为本发明的实施例中网络拓扑分区的装置框图。\n具体实施方式\n[0048] 在本发明的实施例中，通过只存储核心格网中的道路数据，而对拓扑扩展分区部分的道路数据不重复存储，并对拓扑扩展分区部分的道路数据采用数据间接索引的方法，通过一系列格网列表的方式记录在分区管理数据中，当需要应用时可根据分区管理数据提供的索引来读取该道路数据，而并不需要重复记录这些区域中的道路数据，从而可有效减少导航电子地图中道路数据实际存储所占的容量。\n[0049] 下面，首先对本发明所涉及的术语进行介绍。\n[0050] (1)格网(Parcel)：是指对原始路网数据进行分区的基本单元。该格网的划分方式可采用由最南端的纬线和最北端的纬线与最西端的经线的最东端的经线所包围的范围界定，当然该划分方式也并不限于此。通过该格网可以达到快速索引指定地理区域内地图数据的目的。\n[0051] (2)拓扑扩展分区(Topological Overlap Area)：是指道路网络的拓扑覆盖范围，用来表示道路网络的拓扑可控范围。\n[0052] (3)路径搜索(Route Planning)：是指利用导航地图数据库所提供的地图帮助驾驶者在行驶前或行驶中规划路径的过程。\n[0053] 为了使本发明实施例的目的、技术方案和优点更加清楚明白，下面结合实施例和附图，对本发明实施例做进一步详细地说明。在此，本发明的示意性实施例及说明用于解释本发明，但并不作为对本发明的限定。\n[0054] 如图1所示，为本发明的实施例中道路网络拓扑分区的方法流程图，具体步骤如下：\n[0055] 步骤101、获取导航电子地图中道路网络中的原始路网数据，并将获取的原始路网数据划分为多个格网；\n[0056] 在本实施例中，可从SHP格式及DBF格式的道路路网数据文件中获取原始路网数据，上述原始路网数据的来源方式也并不限于此。在本步骤中，原始路网数据可按预先定义的PSF(Physical Storage Format，物理存储格式)规格，设置成“层——区集——区——格网”四级结构进行管理，其中“层”中的道路数据通过“区集”进行管理，“区集”可进一步划分为不同的“区”，而“区”中包含了实际拥有地图数据的格网，参见图2，为本发明的实施例中单层区集、区和格网的平面示意图。\n[0057] 上述划分格网的方式可采用如下方式：通过以预定角度的经度线和纬度线作为边界将该原始路网数据划分为多个格网；或者，以基准点的东西轴和南北轴的平行线为边界将原始路网数据划分为多个格网，其中每一层的格网大小可设置为相同大小，即以各层的标准格网为单位来处理数据。此外，当道路路网中的道路数据量过多或过少时，还可将该格网平均分割处理或者合并处理，此时形成的分割格网或者统合格网可称为处理后的格网(参见图2)。\n[0058] 在本步骤中，该道路网络中的原始路网数据一般按照行政区划提供的，该行政区划可以是按省、自治区或者直辖市，此时步骤101中的原始路网数据预处理可包括如下具体步骤，参见图3，为本发明的实施例中原始路网数据预处理的流程图。\n[0059] 步骤301、配置文件解析；\n[0060] 本步骤中的配置文件包括：原始路网数据路径、路网数据范围、道路种别和道路形态、以及预定的等级划分策略等；\n[0061] 步骤302、判断是否完成所有行政区划的原始路网数据的预处理，若是，执行步骤\n306；否则，执行步骤303；\n[0062] 步骤303、读取原始路网中的道路数据；也就是获取源数据。\n[0063] 步骤304、格网做成；\n[0064] 步骤305、格网输出；\n[0065] 步骤306、全区域编译。\n[0066] 也就是指原始路网数据范围，按行政区划所属格网列表的结构组织，需要对多个格网循环处理。\n[0067] 通过步骤301～步骤306的执行，可将所有行政区划中的原始路网数据进行预处理\n[0068] 步骤102、根据预定的等级划分策略，分别设定多个格网中道路的拓扑等级；\n[0069] 在本实施例中，可基于道路的功能等级来设定格网中道路的拓扑等级，该道路的功能等级包括：城际道路和城市道路，其中该城际道路包括：高速公路、国道、省道、县道和乡道；该城市道路包括：城市快速路、主干道、次干道和支路。此时该拓扑等级的划分可参见表1：\n[0070] 表1\n[0071] \n[0072] 其次，根据道路的形态对设定格网中道路的拓扑等级进行调整，该道路的形态包括：主路、辅路、岔道、匝道和交通环岛。\n[0073] 在执行完步骤102后，若需要调整拓扑等级，则还可对该拓扑等级进行调整，例如基于道路连通性要求进行调整、基于交叉点内道路进行调整、基于环岛道路调整、基于轮渡线道路调整、基于道路封闭性和基于道路的最优性要求进行拓扑等级的调整，其中[0074] (1)基于道路连通性要求调整拓扑等级，此时每一拓扑等级的道路与所有等级比它更高的道路所组成的道路网络都应该构成一个连通的道路网络。即每一条道路至少有一端必须有同等级或高等级的道路与之连通，在本步骤中可对不连通弧段进行降级处理，也就是当该弧段最初拓扑等级设置为1级时，可将拓扑等级调整为2级。例外情况是：高速道路、国道、省道及快速道可能出现某一端不连接(断头路)；岛屿内道路与其它区域道路无轮渡线连接时不连通；\n[0075] (2)基于交叉点内道路调整拓扑等级。此时在弧段始点所在的复合交叉点内查找经过该交叉点内弧段的所有可通行记录，获得进入和输出弧段的最高拓扑等级，然后根据获得的拓扑等级调整交叉点内道路的拓扑等级；\n[0076] (3)基于环岛道路调整拓扑等级。此时对环岛弧段进行调整，确保环岛弧段的拓扑等级等于它的连接弧段的最高拓扑等级；\n[0077] (4)基于轮渡线道路调整拓扑等级。此时对轮渡线进行升级，确保和高层路网连通；\n[0078] (5)根据道路封闭性要求调整拓扑等级。封闭性是指在考虑交通规制(包括弧段和节点的交通规制两部分)的前提下，每一条道路首尾都必须有同等级或高等级的道路与之连通，换言之，在所形成的道路交叉点上，从每一条道路到其它各条同等级或高等级道路都必须是可通行的。本步骤对不封闭弧段进行降级；\n[0079] (6)根据道路的最优性要求进行拓扑等级的调整，最优性是指以任意一对道路作为出发地和目的地，可以在由拓扑等级不低于它们的道路所组成的网络中规划最优路径，结果与在原始道路网络中规划相同。本步骤将升级相关道路。最优性的意义在于保证搜索过程中从出发地到目的地的搜索道路拓扑等级呈阶梯状分布，即两端等级较低而中央较高。例如在利用现有的双向Dijkstra算法中，在任何一个方向的搜索树中，当一条临时路径在搜索到等级较高的弧段时，可忽略等级较低弧段继续进行搜索，这种处理方法大大减小了搜索空间，而路径最优最优性仍能得到保证。\n[0080] 在执行完步骤103后，可根据格网中道路的拓扑等级，将该格网中的道路数据分块存储。具体为按道路的拓扑等级重新组织格网中道路的信息，该信息包括：道路的节点记录信息、弧段记录信息、或者复合节点记录信息，然后将相同拓扑等级的道路保存在同一数据块中，即相同等级的数据保存在同一分块中，从而可有效提高数据读取效率。\n[0081] 步骤103、以每个格网为核心格网，从该核心格网边界的低拓扑等级的道路出发进行最优路径扩展；\n[0082] 在本实施例中分区的实际物理存储数据只有核心格网，而对拓扑扩展分区部分不重复存储，因此首先要获得核心格网，然后根据该核心格网来获取响应的拓扑扩展分区。上述核心格网区域不重叠，且它们的并集可构成整个道路网络，设置核心格网的原则可以是保持各分区核心区域内数据量均衡。在本步骤中每个格网应被选择到，且仅被选设置为核心格网一次。\n[0083] 在完成设置核心格网后，再进行相应拓扑扩展分区最优路径探索，在本实施例中可从该核心格网边界的低拓扑等级道路出发，例如从核心格网边界的4级和3级道路出发，然后以多种优先条件进行正向及逆向最优路径扩展，该多种优先条件是指时间优先、距离优先或者收费优先等。最优路径扩展中所覆盖区域是格网经过延伸形成的范围更大的多边形区域。根据在拓扑扩展分区中所能到达节点的拓扑等级，可区分为2级和1级两种等级的拓扑扩展分区；而根据核心格网是出发地还是目的地的区分，又可区分为正向及逆向两种类型。图4a是从分区核心格网出发的正向最优路径扩展；图4b是从分区核心格网出发的逆向最优路径扩展。\n[0084] 步骤104、通过遍历最优路径扩展所经过的其他格网得到拓扑扩展分区，该拓扑扩展分区保证路径路径搜索数据分层间的拓扑连通性；\n[0085] 在本步骤中，通过遍历最优路径扩展经过的格网，可得到2级和1级两种拓扑扩展分区，在拓扑分区管理记录中记录2级和1级虚拟拓扑分区的格网列表。拓扑扩展分区可保证路径搜索数据分区层次间的连接性，在分区边界，可通过上层道路的同一节点连接属性向上一层次切换，使路径搜索可以按层次分段进行。图5是由最优路径探索结果得到拓扑扩展分区示意，图中从最优路径终点开始回溯整条路线，路线中2级道路L4、L3所在的格网为1级扩展分区，3级或者4级道路L2和L1所在的格网为2级扩展分区，此时拓扑分区由核心格网、2级拓扑扩展分区、1级拓扑扩展分区三个组成部分。\n[0086] 参见图6，为本发明的实施例中完成拓扑扩展分区的方法流程图，该方法包括如下具体步骤：\n[0087] 步骤601、初始化探索工作区；\n[0088] 步骤602、判断是否遍历核心格网所有3级和4级节点记录，若是，则结束本方法流程；否则，执行步骤603；\n[0089] 在本实施例中，由于2级扩展分区是由核心格网边界的3级和4级节点进行线路探索，达到2级及以上节点停止扩展。对2级及以上节点，按上述要求无需进行扩展，因此可结束本方法的流程。\n[0090] 步骤603、判断当前节点是否为核心格网的边界节点，若是，则返回步骤602；否则，执行步骤604；\n[0091] 核心格网中的任意非边界节点在路线扩展过程中必然会经过边界节点，因此它们扩展经过的区域包含在边界节点扩展经过的区域内，故可以忽略这类节点的扩展。\n[0092] 步骤604、取得当前结点对应弧段记录；\n[0093] 步骤605、时间优先，正向线路探索；\n[0094] 步骤606、根据探索结果得到2级和1级正向扩展分区格网列表；\n[0095] 本步骤中的1级扩展分区，是由核心格网的2级扩展分区边界上的2级节点进行路线探索，到达1级节点停止扩展。\n[0096] 步骤607、时间优先，进入线路探索；\n[0097] 步骤608、根据探索结果得到2级和1级反向扩展分区格网列表；\n[0098] 步骤609、距离优先，退出线路探索；\n[0099] 步骤610、根据探索结果得到2级和1级正向扩展分区格网列表；\n[0100] 步骤611、距离优先，进入线路探索；\n[0101] 步骤612、根据探索结果得到2级和1级反向扩展分区格网列表，然后返回到步骤\n602。\n[0102] 步骤105、存储核心网中的道路数据，并在拓扑分区管理数据中通过索引数据记录拓扑扩展分区的格网列表。\n[0103] 然后，重复步骤103～步骤105的处理流程，直到多个格网作为核心格网获取拓扑扩展分区的过程全部处理完毕。\n[0104] 本发明所使用的路网数据模型为每个网格预先定义了多级拓扑扩展分区。在拓扑扩展分区可以保证到达上一层次的拓扑等级节点，因此可以保证路径搜索按层次分段进行。本发明中使用拓扑扩展分区技术生成的分区，可独立提供分区内的跟踪和导航服务，并可应用于按需下载和增量更新应用模式的实现。\n[0105] 为了实现上述的方法实施例，本发明的其他实施例还提供了一种导航电子地图中道路网络拓扑分区的装置。另需首先说明的是，由于下述的实施例是为实现前述的方法实施例，故该装置都是为了实现前述方法的各步骤而设，但本发明并不限于下述的实施例，任何可实现上述方法的装置都应包含于本发明的保护范围。并且在下面的描述中，与前述方法相同的内容在此省略，以节约篇幅。\n[0106] 如图7所示，为本发明的实施例中网络拓扑分区的装置框图，该装置70包括：\n[0107] 划分模块71，用于获取所述道路网络中的原始路网数据，将获取的所述原始路网数据划分为多个格网；\n[0108] 拓扑等级划分模块72，用于根据预定的等级划分策略，分别设定所述多个格网中道路的拓扑等级；\n[0109] 上述预定的等级划分策略为基于道路的功能等级，来设定所述格网中道路的拓扑等级，所述道路的功能等级包括：城际道路和城市道路，其中所述城际道路包括：高速公路、国道、省道、县道和乡道；所述城市道路包括：城市快速路、主干道、次干道和支路。及[0110] 而且道路的拓扑等级还可根据道路的形态进行拓扑等级的调整，此时该道路的形态包括：主路、辅路、岔道、匝道和交通环岛。\n[0111] 路径扩展模块73，用于以每个格网为核心格网，从所述核心格网的边界的低拓扑等级的道路出发进行路径扩展；\n[0112] 遍历模块74，用于通过遍历路径扩展所经过的其他格网得到拓扑扩展分区，所述拓扑扩展分区保证路径搜索数据分区层间的拓扑连通性；\n[0113] 存储模块75，用于存储所述核心格网中的道路数据，并在拓扑分区管理数据中通过索引数据记录所述拓扑扩展分区的格网列表。\n[0114] 在本发明的另一实施例中，该装置70还包括：\n[0115] 读取模块，用于根据所述拓扑分区管理数据中提供的所述格网列表的索引数据，读取所述拓扑扩展分区中的道路数据。\n[0116] 在本发明的另一实施例中，拓扑等级划分模块72包括：拓扑等级调整单元，根据所述格网中道路的连通性、封闭性和最优性，来调整所述道路的拓扑等级。\n[0117] 上述道路的最优性是指以任意一对道路作为出发地和目的地，在由拓扑等级不低于所述一对道路所组成的网络中规划最优路径。\n[0118] 由上述技术方案可知，通过只存储核心格网中的道路数据，而对扩展部分的道路数据不重复存储，并对扩展部分的道路数据采用数据间接索引的方法，通过一系列格网列表的方式记录在分区管理数据中，应用时只需根据分区管理数据提供的索引来读取该道路数据，而并不需要重复记录这些区域中的道路数据，从而可有效减少导航电子地图中道路数据实际存储所占的容量，并且还可提供分区内道路的跟踪和导航服务，并可应用于按需下载和增量更新应用模式的实现。\n[0119] 以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以作出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。