专利名称：导航电子地图的处理方法和装置、导航仪的制作方法
技术领域：
本发明涉及卫星导航领域，尤其涉及一种导航电子地图的处理方法和装置、导航仪。
背景技术：
目前，在导航电子地图中，基于道路自然特征的多级分层模型，将现实世界道路网络中的道路和路口分别抽象为弧段和节点。由于道路交通流具有方向性，因此道路网络采用有向图模型，其中，弧段记录了道路的属性信息和通行限制信息，例如，道路的长度、宽度、道路等级、车道数、限制速度等属性信息，节点记录了路口的转向限制信息和转向代价 fn息ο考虑到道路网的特点，并结合驾驶员更愿意选择较为宽阔的主干道行车的特点， 来构造分层模型。城市道路网一方面包含网络本身地理位置的拓扑特征，另一方面还包含了大量的反映道路网知识特点与应用有关的数据。例如，我国城际道路分为高速公路、国道、省道、县道、乡道等，城市道路分为城市快速路、主干道、次干道、支路等。以道路形态划分，道路具有主路、辅路、岔道、匝道、交通环岛等不同属性，道路网的这种知识特征将直接关系到驾驶者对行车路径的选择心理，因此道路分层等级可以根据以上道路自然特征赋予。目前，多级道路网的构建方法为将道路数据按照种别信息，由高到低构建多级道路网数据模型，并且保证每一级的道路网和更高级别的道路网整体是连通可达的。这样，在某级道路网数据不连通或不封闭时，通过将低级道路升级到该级别，就能够使得该级网络达到连通和封闭的要求。但是，上述采用级别进行导航电子地图的道路计算时，由于该方案需要基于道路自然特征的多级分层模型(道路的级别模型)，因此，在这种模型下无法保证计算结果的最优性，导致道路实际的计算和规划结果与最优结果之间存在较大的误差；此外，由于实际情况下城市中心和郊区的道路密度差别较大，因此会导致导航电子地图的网络数据量分布不均，在进行道路规划时会造成搜索空间在城乡之间变化幅度过大，不仅会降低城市道路与乡村导致之间过渡的平滑性，而且由于嵌入式设备的处理资源有限，且规划过程中无法调整较为密集的城市道路的搜索空间大小，因此会进一步降低规划结果的准确性和效率。目前，针对相关技术中道路规划结果不理想、效率低的问题，目前尚未提出有效的解决方案。

发明内容
针对相关技术中道路规划结果不理想、效率低的问题，本发明提出一种导航电子地图的处理方法，能够在保证道路规划和计算结果的准确性的前提下提高处理效率。针对相关技术中道路规划结果不理想、效率低的问题，本发明提出一种导航电子地图的处理装置，能够在保证道路规划和计算结果的准确性的前提下提高处理效率。
针对相关技术中道路规划结果不理想、效率低的问题，本发明还提出一种导航仪， 能够在保证道路规划和计算结果的准确性的前提下提高处理效率。本发明的技术方案是这样实现的本发明提供了一种导航电子地图的处理方法。根据本发明的导航电子地图的处理方法包括将导航电子地图分成多个格网；对于多个格网中的每个格网，将该格网所有边界点向外进行多起点路线扩展，得到该格网的邻近连通区域，其中，邻近连通区域中包括路线扩展所途经的格网，并且，每个格网的数据量与相应的邻近连通区域的数据量总和小于预定值；对于每个格网的每个边界点，从该边界点向该格网以外进行高速网道路扩展，得到高速网道路，其中，高速网道路用于将该格网的邻近连通区域与其他格网的邻近连通区域相连通，高速网道路所连通的邻近连同区域彼此不相交，并且高速网道路位于其连通的邻近连通区域以外的区域内。该方法还包括对于每个格网进行高速网道路扩展得到的断裂节点，将该断裂节点与其他格网进行高速网道路扩展得到的断裂节点连通，其中，断裂节点的一侧为高速网道路，另一侧为非高速网道路。此外，在该方法中，多个格网中每个格网的数据量在预定范围内。本发明提供了一种导航电子地图的处理装置。根据本发明的导航电子地图的处理装置包括格网分割模块，用于将导航电子地图分成多个格网；连通区域确定模块，用于对多个格网中的每个格网，将该格网所有边界点向外进行多起点路线扩展，得到该格网的邻近连通区域，其中，邻近连通区域中包括路线扩展所途经的格网，并且，每个格网的数据量与相应的邻近连通区域的数据量总和小于预定值；高速网道路确定模块，用于对每个格网的每个边界点，从该边界点向该格网以外进行高速网道路扩展，得到高速网道路，其中，高速网道路用于将该格网的邻近连通区域与其他格网的邻近连通区域相连通，高速网道路所连通的邻近连同区域彼此不相交，并且高速网道路位于其连通的邻近连通区域以外的区域内。该装置还可以包括连通处理模块，用于将每个格网进行高速网道路扩展得到的断裂节点与其他格网进行高速网道路扩展得到的断裂节点连通，其中，断裂节点的一侧为高速网道路，另一侧为非高速网道路。此外，上述多个格网中每个格网的数据量在预定范围内。本发明提供了一种导航仪。根据本发明的导航仪包括上述导航电子地图的处理装置，其中，该导航电子地图的处理装置包括格网分割模块，用于将导航电子地图分成多个格网；连通区域确定模块，用于对多个格网中的每个格网，将该格网所有边界点向外进行多起点路线扩展，得到该格网的邻近连通区域，其中，邻近连通区域中包括路线扩展所途经的格网，并且，每个格网的数据量与相应的邻近连通区域的数据量总和小于预定值；高速网道路确定模块，用于对每个格网的每个边界点，从该边界点向该格网以外进行高速网道路扩展，得到高速网道路，其中，高速网道路用于将该格网的邻近连通区域与其他格网的邻近连通区域相连通，高速网道路所连通的邻近连同区域彼此不相交，并且高速网道路位于其连通的邻近连通区域以外的区域内。该导航仪中的导航电子地图的处理装置还可以包括连通处理模块，用于将每个格网进行高速网道路扩展得到的断裂节点与其他格网进行高速网道路扩展得到的断裂节点连通，其中，断裂节点的一侧为高速网道路，另一侧为非高速网道路。此外，上述多个格网中每个格网的数据量在预定范围内。借助于本发明的上述技术方案，通过将导航电子地图划分为格网模型，并以各格网的边界点为起始进行道路的规划，相比于依据道路自然特性的规划方式，能够有效提高导航电子地图路径规划的准确度，并且能够使地图上任意两点间的路径规划时的搜索数据量可控，避免了由于地图上数据量分布不均勻而导致路径搜索最坏搜索空间指标差以及处理效率低的问题；此外，通过确定格网的邻近连通区域，能够将道路进行分层，能够减少所需考虑的节点数量，有助于在后续路线搜索时提高搜索的效率，降低搜索终端的负担。


图1是根据本发明实施例的导航电子地图的处理方法的流程图；图2是根据本发明实施例的高速网道路的示意图；图3是根据本发明实施例的导航电子地图的处理方法中采用高速网道路进行搜索的处理示意图；图4是根据本发明实施例的导航电子地图的处理方法中对单个格网分别进行处理的处理流程图；图5是根据本发明实施例的导航电子地图的处理方法中对标准格网的统合与分割的处理流程图；图6是根据本发明实施例的导航电子地图的处理方法中格网内路线做成处理的流程图；图7是根据本发明实施例的导航电子地图的处理方法中计算格网的邻近连通区域处理的流程图；图8是根据本发明实施例的导航电子地图的处理方法中设定和本格网相关的高速网道路处理的流程图；图9是根据本发明实施例的导航电子地图的处理方法中对待扩展弧段进行扩展的处理示意图；图10是根据本发明实施例的导航电子地图的处理方法中高速网数据连通处理的流程图；图11是根据本发明实施例的导航电子地图的处理方法中高速网数据抽象处理的流程图；图12是根据本发明实施例的导航电子地图的处理方法中格网边界节点和高速网拓扑关联处理的流程图；图13是根据本发明实施例的导航电子地图的处理装置的组成结构图。
具体实施方式
由于现实应用中导航电子地图的道路网络数据量非常庞大，而导航应用的硬件环境是受限的(也就是说，通常导航仪的处理能力是有限的)，如果将数据全部读入内存是不现实的。因此，本发明提出了基于格网对道路网络进行分区，具体做法是将一个较大的地理区域按地理位置或道路网络的疏密分成多个不同的部分，对每个部分进行单独的处理(例如，进行单独的I/O处理以及后续与导航电子地图的道路规划相关的处理)，划分得到的每个分区可以称为格网。对于格网数据，可以设定一个基准大小为单位来处理数据。此外，在数据量过多或过少时，还可进一步将每个格网进一步平均分割或者合并处理，形成分割格网和统合格网。这样，在道路密集的城市区域，格网的划分同样较为密集，而在道路较为稀疏的乡村区域，格网的分布也较少，从而能够保证每个格网的数据量更为合理，使得在道路规划和计算过程中每个格网的数据均能够得到充分考虑，避免道路规划和计算过程仅依赖于道路的自然特征，解决了相关技术中城市与乡村之间过渡平滑性差、道路规划效率低、结果不准确的问题。图1是根据本发明实施例的导航电子地图的处理方法，如图1所示，该方法包括步骤S101，将导航电子地图分成多个格网；步骤S103，对于多个格网中的每个格网，将该格网所有边界点向外进行多起点路线扩展(也就是说，对于每个格网，取所有边界点作为根节点想该格网外进行扩展，即，可以理解为进行多起点路线树扩展)，得到该格网的邻近连通区域，其中，邻近连通区域中包括路线扩展所途经的格网，并且，每个格网的数据量与相应的邻近连通区域的数据量总和小于预定值；步骤S105，对于每个格网的每个边界点，从该边界点向该格网以外进行高速网道路扩展，得到高速网道路，其中，高速网道路用于将该格网的邻近连通区域与其他格网的邻近连通区域相连通，高速网道路所连通的邻近连同区域彼此不相交，并且高速网道路位于其连通的邻近连通区域以外的区域内。借助于本发明的上述技术方案，通过将导航电子地图划分为格网模型，并以各格网的边界点为起始进行道路的规划，相比于依据道路自然特性的规划方式，能够有效提高导航电子地图路径规划的准确度，并且能够使地图上任意两点间的路径规划时的搜索数据量可控，避免了由于地图上数据量分布不均勻而导致路径搜索最坏搜索空间指标差以及处理效率低的问题；此外，通过确定格网的邻近连通区域，能够将道路进行分层，能够减少所需考虑的节点数量，有助于在后续路线搜索时提高搜索的效率，降低搜索终端的负担。在以上处理中，多个格网中每个格网的数据量应当在预定范围内。并且，对于每个格网进行高速网道路扩展得到的断裂节点，将该断裂节点与其他格网进行高速网道路扩展得到的断裂节点连通，其中，由于断裂节点是进行高速网道路扩展的过程中扩展中断的节点，因此，断裂节点的一侧为高速网道路，另一侧为非高速网道路。优选地，在实际应用当中，可以遍历所有断裂的边界点，使得任意两个断裂边界点之间的路线相连通，从而保证整个地图的连通性。在上述处理中，对于进行道路搜索没有用处的假节点，则可以直接删除，从而减少了不必要的数据搜索(从而可以减少诸如数据I/O的相关道路规划处理)，可以加快搜索的速度，能够进一步提高道路规划过程中道路搜索的效率。下面将结合具体实例，详细描述根据本发明的导航电子地图的处理过程。基于划分为多个格网的导航电子地图，本发明提出了邻近连通区域的概念，其中， 与一个格网邻近的连通区域是指从该格网所有边界点出发的数据量总和在预定值之内的拓扑连通区域，该区域由最短路径树所覆盖的格网构成，并有正向和逆向两种类型，具体定义如下设G = (E，V)为基于格网划分的网络，以某个格网的所有边界节点为根，构造最短路径树，在扩展过程中，如果扩展到达格网边界，并且在已读取格网数据量和该新格网数据量之和小于邻近连通区域数据量控制值M(M为预先设置的邻近连通区域数据量阈值)情况下，继续读取新格网数据以继续扩展；在已读取格网数据量和该新格网数据量之和大于或等于M的情况下，则终止在该边界点的扩展。扩展过程全部结束后将最短路径树经过的全部格网标记为该格网的邻近连通区域。在网络中，一个指定格网的邻近连通区域可以分为正向邻近连通区域和逆向邻近连通区域，其中，格网的正向邻近连通区域为以该指定格网的所有边界节点为根，沿边界弧段正方向扩展构成的最短路径树覆盖格网，在扩展过程中所读取的格网总数据量小于预定的最大允许扩展数据量(即，小于M)，这些在扩展过程中读取的格网构成该格网的正向邻近连通区域；格网的逆向邻近连通区域为以该指定格网的所有边界节点为根，沿边界弧段逆方向扩展构成的最短路径树覆盖格网，并且，在扩展过程中所读取的格网总数据量小于预定的最大允许扩展数据量，这些在扩展过程中读取的格网构成该格网的逆向邻近连通区域。以格网的正向邻近连通区域为例，道路的规划和计算过程如下将已扩展数据量初始化为该指定格网的数据量MO ；以该格网的所有边界节点(vl，v2,... vn)为根，构造初始代价均为0的多出发节点的最短路径树；循环进行最短路径树扩展。在扩展的过程中，如扩展遇到新的格网边界点，并且， 当前已扩展数据量MO和新格网数据量之和小于最大允许扩展数据量Mmax (即，上述的阈值 M)，则读取新格网，并更新已扩展数据量M0，将更新后的MO用于后续扩展的判断，否则停止扩展该边界点；在最短路径树扩展结束时，将所有已读取的格网标记为格网的正向邻近连通区域，从而完成了正向邻近连通区域的道路的规划和计算过程。逆向邻近连通区域的道路的规划和计算过程类似，这里不再重复。此外，在本发明的实现过程中，为了便于远距离道路的规划，还可以定义高速网道路。其中，在本发明实施例中，高速网道路是指在网络中跨区域搜索所需要通过的弧段。例如，某弧段A出现在某条最优路径中，该高速网道路的路径分别以弧段s和弧段t为出发地和目的地的，如图2所示。如图2中实线所示的部分，如路径符合下述条件，该路径的弧段可设定为高速网道路该弧段不属于弧段S开始到第一次扩展出本格网的正向邻近连通区域部分，同时也不属于沿弧段t反向回溯到最后一次进入t所在格网的逆向邻近连通区域部分。在网络中，高速网道路可以采用上述方法从全部道路中抽取，并可以将抽取的高速网道路映射到全体道路网络的一个子集，以便应用于远距离路径规划和计算。在获取全部高速网道路数据后，需要将这些道路在所涉及的地图数据范围内的全部格网进行合并，即，对假节点进行抽象后获得抽象层网络，然后进行整体存储，即，将网络存储为分层模型。可以看出，分层模型删除了部分假节点，减少了数据不必要的搜索(从而可以减少诸如数据I/O的相关道路规划处理)，可以加快搜索的速度，能够进一步提高道路规划过程中道路搜索的效率。为了保证本发明的道路规划方案能够更好地实施，本发明中的还可以进一步定义远程区域定义为，该远程区域是指在一次路径规划中，该区域既不属于出发地所在格网的正向邻近连通区域，也不属于目的地所在格网的逆向邻近连通区域的范围。基于远程区域的定义，当在任意出发地和目的地之间进行的路径规划时，如果出发地所在格网的正向邻近连通区域和目的地所在格网的正向邻近连通区域的逆向邻近连通区域不重叠时，可将分层搜索算法分为以下三个部分第一部分为出发地所在格网的正向邻近连通区域，使用全部道路搜索；第二部分为远程区域，使用高速网搜索，其中，由前述高速网道路构造方法可见， 任何一条最优路径中位于远程区域的部分，必然已在道路阶层设定过程中设定为高速网道路，因此，如图3所示，在该区域搜索时可以忽略非高速网道路；第三部分为目的地所在格网的逆向邻近连通区域，使用全部道路搜索。在实际规划时，假设高速网的数据量为Chigh,同时，无论正向或逆向邻近连通区域，其数据量均不大于邻近连通区域制作过程中的“最大允许扩展数据量” Mmax，因此本发明中任何两点间路径规划中用到的数据量不大于Chigh+2*Mmax。并且，之前所描述的使用最大数据量进行规划和计算的方式可以适用出发地所在格网的正向邻近连通区域和目的地所在格网的正向邻近连通区域的逆向邻近连通区域有重叠的情况。在实际应用中，可以对每个作为扩展根节点的格网配置对应的线程，从而通过线程实现相应格网的扩展。如图4所示，首先需要解析配置文件，之后需要判断是否完成所有格网的遍历，如果未完成，则对单个格网进行处理；如果已经完成对所有格网的遍历，则处
理结束。下面将以对单个格网的处理过程为例进行详细描述。在实际应用中，应该遍历全道路网络范围内的所有格网，具体过程如下步骤(1)标准格网的统合和分割处理(对应于上述步骤S101)；步骤(2)格网内路线做成处理；步骤( 计算格网的邻近连通区域处理(对应于上述步骤S103)；步骤(4)设定和本格网相关的高速网道路处理(对应于上述步骤S105)；步骤(5)高速网数据连通处理；步骤(6)高速网数据抽象处理(该步骤为可选步骤)；步骤(7)格网边界节点和高速网拓扑关联处理。其中，如图5所示，在步骤(1)中，可进一步包括如下步骤以格网为单位读取原始数据，进行格网生成；之后，根据格网数据量，进行不分割、 平均分割或者统合(可以理解为合并)处理，分别形成标准格网、分割格网和统合格网，并且重复该处理，直至输出所有格网。并且，如图6所示，在步骤(2)中，可进一步包括如下步骤在格网内路线做成的处理过程中，需要初始化格网内道路探索工作区；找出格网边界上的任意一对边界点；仅考虑格网内道路网络数据，以找到的节点为出发和到达节点，规划最优路径；如果格网内存在最优路径，则将该最佳路径记录为格网内路线，并存储该路线所包含的系列弧段和节点，之后继续查找边界点对，直到格网边界上的节点对全部遍历结束的过程全部处理完成。如图7所示，在步骤C3)中，计算格网的邻近连通区域的处理可进一步包括如下步骤以格网的所有边界节点(vl，v2, ... vn)为根，构造初始代价均为0的多出发节点的最短路径树；最短路径树扩展过程必须在所读取的格网总数据量不大于预定的最大允许扩展数据量Mmax条件下进行，否则应停止扩展；这些在正向最短路径树扩展过程中读取的格网构成格网的正向邻近连通区域，并根据扩展结果得到正向纶巾连通区域格网列表。之后，可以以逆向扩展最短路径树方法重复上述步骤的处理流程，得到指定格网的逆向邻近连通区域，具体过程如下以该格网的所有边界节点(vl，v2,... vn)为根，构造初始代价均为0的多出发节点的最短路径树；之后进行反向路线扩展，得到逆向邻近连通区域。如图8所示，在上述步骤(4)中，设定和本格网相关的高速网道路处理的具体过程如下步骤81，初始化最短路径树扩展工作区；步骤82，选取一个格网的边界节点S，如图9所示，初始化代价为0，使用格网内路线扩展最短路径树；步骤83，选择代价最小的待扩展路线；步骤84，判断是否有可继续扩展的路线，如果判断结果为是，则执行步骤87 ；否则执行步骤85 ；步骤87，在最短路径搜索树中，遍历每条临时路径，设定高速网道路弧段，处理结束；步骤85，S至当前路线的临时路径经过可设定为高速网道路的弧段，并执行步骤 86 ；步骤86，当前路线设定可终止扩展标记，并执行步骤88 ；步骤88，判断所有待扩展弧段是否已设定可终止扩展标记，如果判断结果为是，则实行步骤87，否则执行步骤89 ；步骤89，当前路线状态更新为已扩展，并扩展当前路线，之后执行步骤83。在图8所示的处理中，对于路径树中的每个叶节点路线r，如果满足以下条件，可终止路线r的扩展条件(1)路线r所在的格网不同于本格网；条件(2)在s至！·的最优路径中至少有一条路线v，既不属于本格网的正向邻近连通区域，也不属于路线r所在格网的逆向邻近连通区域。当以S为出发点的最短路径树的叶节点路线全部终止扩展后，对所有从S到叶节点路线t的路径中，参照高速网道路设定原则标记高速网道路。如图10所示，在上述步骤(5)中，高速网数据连通处理的具体过程如下步骤1001，初始化最短路径树扩展工作区；
步骤1002，选取格网的一个边界节点S，应满足所连接的格网内弧段为高速网，格网外弧段为非高速网。设初始代价为0，使用格网内路线扩展最短路径树；步骤1003，选择代价最小的待扩展路线；步骤1004，判断是否有可继续扩展的路线，如果判断结果为是，则执行步骤1007 ； 否则执行步骤1005 ；步骤1007，在最短路径搜索树中，遍历每个临时路径；将S至临时路径中最后一段高速网路线之间的全部弧段设定为高速网道路弧段，处理结束；步骤1005，S至当前路线的临时路径为高速网道路弧段，并执行步骤1006 ；步骤1006，当前路线设定可终止扩展标记，并执行步骤1008 ；步骤1008，判断所有待扩展弧段是否已设定可终止扩展标记，如果判断结果为是， 则实行步骤1007，否则执行步骤1009 ；步骤1009，当前路线状态更新为已扩展，并扩展当前路线，之后执行步骤1003。也就是说，在上述处理中，对于格网的边界节点，如果该节点连接的格网内弧段为高速网道路，而格网外为非高速网道路，则应进行连通处理。以该节点S为出发节点构造初始代价为0的使用格网内路线扩展的最短路径树，对搜索树中的每个叶节点路线r，如果r 连接高速网道路，则可终止路线r的扩展。当以S为出发点的最短路径树的叶节点路线全部终止扩展后，遍历所有连接高速网道路的叶节点路线r，将从S到的r的路径升级为高速网道路。如图11所示，在上述步骤(6)中，可进一步包括如下步骤步骤1101，在原始网络基础上，抽取高速网道路弧段构成的网络，优选地，可以抽取格网通达度等级最高的弧段构成网络；步骤1102，找出网络内的节点；步骤1103，判断节点是否遍历结束，如果判断结果为是，则处理结束；否则执行步骤 1104 ；步骤1104，判断该节点是否为假节点，如果判断结果为是，则执行步骤1105 ；否则执行步骤1102，继续找出网络内的节点；步骤1105，删除假节点，并执行步骤1106 ；步骤1106，将假节点两侧的弧段直接合并。在原始网络基础上，抽取格网通达度等级最高的弧段构成网络；602对该网络中的假节点(删除部分假节点，即弧段合并)进行抽象后，获得抽象网络。通过上述删除假节点的处理，能够达到网络简化的目的，减少处理的次数，提高处理效率，而将假节点两侧的节点直接关联的过程可以称为抽象。如图12所示，在上述步骤(7)中，格网边界节点和高速网道路拓扑关联处理的具体处理过程如下步骤1201，找出格网边界的交点，建立其它分层和高速网的关联；步骤1202，判断是否遍历完所有的边界节点；如果判断结果为是，则处理结束；否则执行步骤1203 ；步骤1203，判断该节点是否为高速网道路节点；如果判断结果为是，则执行步骤 1204 ；否则执行步骤1201 ；
步骤1204，匹配该节点对应的高速网道路弧段，并执行步骤1205 ；步骤1205，以该节点为分割点，将对应的高速网弧段分割成两条假定弧段，并执行步骤1206 ；步骤1206，记录该节点和高速网的关联属性(例如，分割成的两条假定弧段等)。由于在步骤(7)中，这些格网边界点在高速网中已经被抽象。因此，通过图12中所示的处理，就能够建立高速网道路弧段在格网边界上节点和高速网的关联，从而在网络搜索过程中实现了层次切换，并且能够保证路径计算结果的合理性。图13是根据本发明实施例的导航电子地图的处理装置，如图13所示，该装置包括格网分割模块131，用于将导航电子地图分成多个格网；连通区域确定模块132，用于对多个格网中的每个格网，将该格网所有边界点向外进行多起点路线扩展，得到该格网的邻近连通区域，其中，邻近连通区域中包括路线扩展所途经的格网，并且，每个格网的数据量与相应的邻近连通区域的数据量总和小于预定值；高速网道路确定模块133，用于对每个格网的每个边界点，从该边界点向该格网以外进行高速网道路扩展，得到高速网道路，其中，高速网道路用于将该格网的邻近连通区域与其他格网的邻近连通区域相连通，高速网道路所连通的邻近连同区域彼此不相交，并且高速网道路位于其连通的邻近连通区域以外的区域内。该装置还可以还包括连通处理模块134，用于将每个格网进行高速网道路扩展得到的断裂节点与其他格网进行高速网道路扩展得到的断裂节点连通，其中，由于断裂节点是高速网道路扩展的中断节点，因此，断裂节点的一侧为高速网道路，另一侧为非高速网道路。其中，上述多个格网中每个格网的数据量在预定范围内。本发明还提供一种导航仪，包括如图13所示的导航电子地图的处理装置。根据本发明的导航仪和导航电子地图的处理装置同样可以执行图1、4、5、6、7、8、 9、10、11、和12所示的处理，具体过程之前已经描述，这里不再重复。通过上述处理，由于高速网道路被定义为在网络中跨区域搜索所需要通过的道路，因此，在道路规划和计算时能够从高速网道路的直观意义上分析，等级越高表示通过该道路的路径通达能越强，对长距离道路搜索的贡献越大。此外，借助于分层格网模型，能够从数学上解决如何界定道路的重要程度的问题，即，根据道路在路径搜索过程中的实际作用，确定其在多级网络中的拓扑等级；此外，由于路径规划算法用到的数据分为三个部分， 第一部分为出发地附近上升搜索，第二部分为顶层搜索，第三部分为目的地附近下降搜索， 而路径规划全过程的搜索空间是三个部分搜索空间之和，且由于最高级网络(顶层)数据量在数据编译时已确定，同时，第一和第三部分的数据量不超过数据编译时确定的预定值， 因此，能够使得任意两点间的路径规划搜索数据量可控。在路径规划算法的道路网层级向高层切换时，不会因为对搜索空间的裁减破坏路径规划结果的最优性；并且，由于对搜索空间的较强裁减效应，能够删除不必考虑的假节点，因此能够在保 证道路搜索结果的最优性的同时提高计算效率，解决了基于道路自然特征的多级分层模型计算效率低的问题。以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
权利要求
1.一种导航电子地图的处理方法，其特征在于，包括将导航电子地图分成多个格网；对于所述多个格网中的每个格网，将该格网所有边界点向外进行多起点路线扩展，得到该格网的邻近连通区域，其中，所述邻近连通区域中包括路线扩展所途经的格网，并且， 每个格网的数据量与相应的邻近连通区域的数据量总和小于预定值；对于每个格网的每个边界点，从该边界点向该格网以外进行高速网道路扩展，得到高速网道路，其中，所述高速网道路用于将该格网的邻近连通区域与其他格网的邻近连通区域相连通，所述高速网道路所连通的邻近连同区域彼此不相交，并且所述高速网道路位于其连通的邻近连通区域以外的区域内。
2.根据权利要求1所述的处理方法，其特征在于，还包括对于所述每个格网进行高速网道路扩展得到的断裂节点，将该断裂节点与其他格网进行高速网道路扩展得到的断裂节点连通，其中，所述断裂节点的一侧为高速网道路，另一侧为非高速网道路。
3.根据权利要求1或2所述的处理方法，其特征在于，所述多个格网中每个格网的数据量在预定范围内。
4.一种导航电子地图的处理装置，其特征在于，包括格网分割模块，用于将导航电子地图分成多个格网；连通区域确定模块，用于对所述多个格网中的每个格网，将该格网所有边界点向外进行多起点路线扩展，得到该格网的邻近连通区域，其中，所述邻近连通区域中包括路线扩展所途经的格网，并且，每个格网的数据量与相应的邻近连通区域的数据量总和小于预定值；高速网道路确定模块，用于对所述每个格网的每个边界点，从该边界点向该格网以外进行高速网道路扩展，得到高速网道路，其中，所述高速网道路用于将该格网的邻近连通区域与其他格网的邻近连通区域相连通，所述高速网道路所连通的邻近连同区域彼此不相交，并且所述高速网道路位于其连通的邻近连通区域以外的区域内。
5.根据权利要求4所述的处理装置，其特征在于，还包括连通处理模块，用于将所述每个格网进行高速网道路扩展得到的断裂节点与其他格网进行高速网道路扩展得到的断裂节点连通，其中，断裂节点的一侧为高速网道路，另一侧为非高速网道路。
6.根据权利要求4或5所述的处理装置，其特征在于，所述多个格网中每个格网的数据量在预定范围内。
7.一种导航仪，其特征在于，包括导航电子地图的处理装置，其中，所述导航电子地图的处理装置包括格网分割模块，用于将导航电子地图分成多个格网；连通区域确定模块，用于对所述多个格网中的每个格网，将该格网所有边界点向外进行多起点路线扩展，得到该格网的邻近连通区域，其中，所述邻近连通区域中包括路线扩展所途经的格网，并且，每个格网的数据量与相应的邻近连通区域的数据量总和小于预定值；高速网道路确定模块，用于对每个格网的每个边界点，从该边界点向该格网以外进行高速网道路扩展，得到高速网道路，其中，所述高速网道路用于将该格网的邻近连通区域与其他格网的邻近连通区域相连通，所述高速网道路所连通的邻近连同区域彼此不相交，并且所述高速网道路位于其连通的邻近连通区域以外的区域内。
8.根据权利要求7所述的导航仪，其特征在于，所述导航电子地图的处理装置还包括 连通处理模块，用于将所述每个格网进行高速网道路扩展得到的断裂节点与其他格网进行高速网道路扩展得到的断裂节点连通，其中，断裂节点的一侧为高速网道路，另一侧为非高速网道路。
9.根据权利要求7或8所述的导航仪，其特征在于，所述多个格网中每个格网的数据量在预定范围内。
全文摘要
本发明公开了一种导航电子地图的处理方法和装置、导航仪，该方法包括将导航电子地图分成多个格网；对于多个格网中的每个格网，将该格网所有边界点向外进行多起点路线扩展，得到该格网的邻近连通区域，其中，邻近连通区域中包括路线扩展所途经的格网，每个格网的数据量与相应的邻近连通区域的数据量总和小于预定值；对于每个格网的每个边界点，从该边界点向该格网以外进行高速网道路扩展，得到高速网道路，其中，高速网道路用于将该格网的邻近连通区域与其他格网的邻近连通区域相连通，高速网道路所连通的邻近连同区域彼此不相交，并且高速网道路位于其连通的邻近连通区域以外的区域内。能够使地图上任意两点间的路径规划时的搜索数据量可控。
文档编号G01C21/26GK102235873SQ201010157659
公开日2011年11月9日 申请日期2010年4月21日 优先权日2010年4月21日
发明者彭建, 黄栋 申请人:北京四维图新科技股份有限公司