一种构建数字地图的道路网的方法及装置

摘要

本发明提供一种构建数字地图的道路网的方法，首先选择第一行政区划，获取与所述第一行政区划的距离在预设范围内的若干第二行政区划；然后，获取第一行政区划的路径起点和路径终点，根据所述第一行政区划的路径起点和路径终点确定第一行政区划的探索点集合；最后，依次从每个探索点开始，获取到达所述第二行政区划的探索点的可通行路径，形成道路网。该方法中，先获取探索点，然后根据探索点来探索路径，形成可定制的道路网，该方案通过调整行政区划数量或连通算法，可以改变任意区域的道路网。得到的道路网结合导航仪的路径规划算法，可以提高导航仪的路径规划效率。此外，该方法能够自动化计算道路网，减少人工操作，避免重复工作。

说明书

技术领域

本发明涉及数字地图领域，具体涉及一种构建数字地图的道路网的方法及装置。

背景技术

在电子地图中，道路数字化后，使用一条线和两个结点代表现实世界中的一条道路。道路种别有高速，国道，省道，县道，乡镇村道，其它道路。在一定区域内，由各种道路组成的相互联通的道路系统，形成道路网。道路网密集度分布合理，密集度太大或太小都会降低路径规划效率。一种或几种道路种别的道路形成道路网，道路网等级表示道路网的重要性。

导航仪中的道路网一般有多层，从下层向上层，道路网等级越来越高，重要性越来越高，密集度越来越小，适用于更远距离的路径规划。并且上一层的道路网，必须在下一层道路网存在。导航仪的多层道路网，可以视为多次抽取主干道路的结果。最底层道路网拥有现实世界所有道路网，从最底层抽取部分主干道路，构成高级道路网。例如一级道路网为国道组成的省会等大城市之间的道路网，二级道路网为在一级道路网的基础上增加连接不同城市的省道，三级道路网为在二级道路网的基础上增加连接县镇的县道。当新增城市或新增道路后，则需要重新构建新的道路网，进行远距离路径规划，从而用于实现远程导航，但是人工修改费时费力，且更新周期慢，导致数字地图中的道路网数据的有效性差。

发明内容

因此，本发明要解决的技术问题在于克服现有技术中道路更新后无法及时构建新的道路网的缺陷。

本发明提供一种构建数字地图的道路网的方法，包括：选择第一行政区划，获取与所述第一行政区划的距离在预设范围内的若干第二行政区划；获取第一行政区划的路径起点和路径终点，根据所述第一行政区划的路径起点和路径终点确定第一行政区划的探索点集合；依次从每个探索点开始，获取到达所述第二行政区划的探索点的可通行路径，形成道路网。

优选地，所述获取与所述第一行政区划的距离在预设范围内的若干第二行政区划，包括：以所述第一行政区划的中心为圆心，以预设第一距离为半径，获取在该半径覆盖范围内的周边行政区划；将每个周边行政区划的中心分别与第一行政区划的中心连接，若连接线的夹角小于角度阈值，则删除距离第一行政区划中心远的一个或多个周边行政区划，剩余的周边行政区划为第二行政区划。

优选地，所述获取所述第一行政区划的路径起点，包括：以第一行政区划的中心为圆心，预设第二距离为半径，获取该半径范围内的道路结点；以所述道路结点为顶点，分别连接第一行政区划的中心和第二行政区划的中心，得到两条连线的夹角；获取所述夹角接近180°的道路结点的集合作为第一行政区划的路径起点。

优选地，所述获取所述第一行政区划的路径起点，包括：以所述第一行政区划的中心为原点，以预设第三距离为半径画圆；获得圆周与周围道路的交点的集合，以所述交点作为第一行政区划的路径起点。

优选地，所述获取所述第一行政区划的路径终点，包括：确定所述第二行政区划的路径起点，探索从第二行政区划的路径起点到第一行政区划的可通行路径；所述可通行路径的结点与第一行政区划的中心的距离小于预设距离阈值时，探索结束，探索终点为所述第一行政区划的路径终点。

优选地，所述根据所述第一行政区划的路径起点和路径终点确定第一行政区划的探索点集合，包括：将所述路径起点和路径终点合并得到探索点集合。

优选地，所述获取到达所述第二行政区划的探索点的可通行路径形成道路网的过程，包括：根据可通行道路的道路等级形成不同层级的道路网。

此外，本发明还提供一种构建数字地图的道路网的装置，包括：区域选择单元，用于选择第一行政区划，获取与所述第一行政区划的距离在预设范围内的若干第二行政区划；探索点获取单元，用于获取第一行政区划的路径起点和路径终点，根据所述第一行政区划的路径起点和路径终点确定第一行政区划的探索点集合；路网构建单元，用于依次从每个探索点开始，获取到达所述第二行政区划的探索点的可通行路径，形成道路网。

优选地，所述区域选择单元包括：周边行政区划获取子单元，用于以所述第一行政区划的中心为圆心，以预设第一距离为半径，获取在该半径覆盖范围内的周边行政区划；筛选子单元，用于将每个周边行政区划的中心分别与第一行政区划的中心连接，若连接线的夹角小于角度阈值，则删除距离第一行政区划中心远的一个或多个周边行政区划，剩余的周边行政区划为第二行政区划。

优选地，所述探索点获取单元包括路径起点获取子单元，其包括：道路结点选择子单元，用于以第一行政区划的中心为圆心，预设第二距离为半径，获取该半径范围内的道路结点；夹角获取子单元，用于以所述道路结点为顶点，分别连接第一行政区划的中心和第二行政区划的中心，得到两条连线的夹角；选择子单元，用于获取所述夹角接近180的道路结点的集合作为第一行政区划的路径起点。

本发明的方案，具有如下优点：

1.本发明提供的构建数字地图的道路网的方法，首先选择第一行政区划，获取与所述第一行政区划的距离在预设范围内的若干第二行政区划；然后，获取第一行政区划的路径起点和路径终点，根据所述第一行政区划的路径起点和路径终点确定第一行政区划的探索点集合；最后，依次从每个探索点开始，获取到达所述第二行政区划的探索点的可通行路径，形成道路网。该方法中，先获取探索点，然后根据探索点来探索路径，形成可定制的道路网，该方案通过调整行政区划数量或连通算法，可以改变任意区域的道路网，得到的道路网结合导航仪的路径规划算法，可以提高导航仪的路径规划效率。此外，该方法能够自动化计算道路网，减少人工操作，避免重复工作。

附图说明

为了更清楚地说明本发明具体实施方式或现有技术中的技术方案，下面将对具体实施方式或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施方式，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例1中构建数字地图的道路网的方法的一个具体示例的流程图；

图2、图3、图4为本发明实施例1中获取周围行政区划的示意图；

图5、图6为本发明实施例1中获取路径起点的示意图；

图7为本发明实施例1中的构建的道路网的示意图；

图8为本发明实施例2中的构建数字地图的道路网的装置的结构框图。

具体实施方式

下面将结合附图对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

在本发明的描述中，需要说明的是，术语“中心”、“上”、“下”、“左”、“右”、“竖直”、“水平”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。此外，术语“第一”、“第二”、“第三”仅用于描述目的，而不能理解为指示或暗示相对重要性。

在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，还可以是两个元件内部的连通，可以是无线连接，也可以是有线连接。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。

此外，下面所描述的本发明不同实施方式中所涉及的技术特征只要彼此之间未构成冲突就可以相互结合。

实施例1

本实施例中提供一种构建数字地图的道路网的方法，用于数字地图中，能够自动生成多个城市之间的道路网，为远距离路径规划提供参考，该方法的流程图如图1所示，包括如下步骤：

S1、选择第一行政区划，获取与所述第一行政区划的距离在预设范围内的若干第二行政区划。

此处的行政区划一般指的就是城市，例如直辖市、省会城市、地级市等等。行政区划的中心为一个中心坐标，但行政区划包含的区域一般是一个不规则的范围。

获取与所述第一行政区划的距离在预设范围内的若干第二行政区划的过程中，首先，以所述第一行政区划的中心为圆心，以预设第一距离为半径，获取在该半径覆盖范围内的周边行政区划；然后，将每个周边行政区划的中心分别与第一行政区划的中心连接，若连接线的夹角小于角度阈值，则删除距离第一行政区划中心远的一个或多个周边行政区划，剩余的周边行政区划为第二行政区划。此外，作为优选的方式，还可以人工调整周边行政区划，通过人工方式调整周边的行政区划。

下面给出一个具体的实例，例如以武汉为第一行政区划，获取武汉周围的行政区划，方法如下：

首先，按范围筛选周边行政区划。以当前的行政区划武汉的中心为原点，以指定长度R为半径。保留圆形范围以内的周边行政区划，如图2所示，为郑州、合肥、南京、南昌、杭州、长沙。

然后，按角度筛选。连接每个周边行政区划中心与当前行政区划中心，求出连线与正北方向的夹角。如果有任意两条连线的角度差，小于域值T(一般为30度以内)，保留其中一个(或多个)。如图3所示，南京和合肥之间的夹角较小，则删除距离较远的南京，南京不作为武汉的周边行政区划。

最后，手工调整周边行政区划。当上述方法不能找到合适的周边行政区划，使用人工配置的方法。如图4所示，追加西安和重庆作为武汉的周边行政区划。

S2、获取第一行政区划的路径起点和路径终点，根据所述第一行政区划的路径起点和路径终点确定第一行政区划的探索点集合。

其中，获取所述第一行政区划的路径起点的步骤，可采用两种方式来实现。

方式一：

第一，以第一行政区划的中心为圆心，预设第二距离为半径，获取该半径范围内的道路结点；

第二，以所述道路结点为顶点，分别连接第一行政区划的中心和第二行政区划的中心，得到两条连线的夹角；

第三，获取所述夹角接近180度的道路结点的集合作为第一行政区划的路径起点。接近180度可以通过范围判断，例如夹角在165-180之间认为是接近180度，本领域技术人员可以根据需要合理设置。

具体地，给出一个例子，如图5所示，首先获取当前行政中心半径r范围内的所有道路结点的集合N＝{N₁,N₂…N_n}，道路结点可以是道路的起点、交叉点，以道路结点为顶点，连接当前行政中心和周边行政中心，求两条连线的夹角α。得到每个结点对应的夹角集合P＝{α₁,α₂…α_n}。取α最接近180度的结点集合，得到探索起点集合S＝{N₁＇,N₂＇…N_n＇}。

方式二：

第一，以所述第一行政区划的中心为原点，以预设第三距离为半径画圆；

第二，获得圆周与周围道路的交点的集合，以所述交点作为第一行政区划的路径起点。

如图6所示，以当前行政中心为原点，以r为半径画圆，得到圆周与道路的交点集合S＝{N₁,N₂…N_n}，S作为探索起点集合。

获取路径终点的过程如下：首先，确定所述第二行政区划的路径起点，此处确定第二行政区划的路径起点的方式与上述第一行政区划的路径起点的方式相同。探索从第二行政区划的路径起点到第一行政区划的可通行路径。由于第二行政区划可以是若干个，因此每个第二行政区划都可以形成倒第一行政区划的可通行路径。每条可通行路径都有道路结点，如交叉点、起始点等，当所述可通行路径的结点与第一行政区划的中心的距离小于预设距离阈值时，探索结束，预设的距离阈值可以选择0-2km，由于接近行政区划的中心坐标即可，此处的探索终点为所述第一行政区划的路径终点。

当获得了路径起点和路径终点后，将所述路径起点和路径终点合并得到探索点集合。合并当前行政中心的探索起点和探索终点，得到探索点集合X＝{M₁,M₂…M_n}。

S3、依次从每个探索点开始，获取到达所述第二行政区划的探索点的可通行路径，形成道路网。第二行政区划的探索点的获取方式与第一行政区划的探索点的获取方式相同，从而所有的行政区划都建立了其对应的探索点集合，通过依次从每个探索点开始，探索可到达其它探索点的可通行路径，此处的路径探索算法可根据需要设置，如速度最快、距离最短等等，路径探索方法配置表如下表1所示。

表1路径探索配置表

起点行政区划目的地行政区划路径探索算法可以使用的道路种别武汉长沙速度最快，距离最短高速，国道武汉南昌所有可通行路径高速，国道，省道…………

最终，将多个可通行路径连通成一个道路网。将若干个行政区划都进行上述处理，则形成了道路网，如图7所示。

在形成道路网的过程中，根据可通行道路的道路等级形成不同层级的道路网。例如根据国道、高速路形成一级道路网，在一级道路网基础上增加省道形成二级道路网，以此类推，如表2所示，作为可变换的实施方式，此处的分层方式可以在生成道路网时根据需要设置。该方案实现了基于行政等级，结合不同路径探索算法构造多层道路网。

表2道路种别配置表

道路网等级道路种别1主要包括高速道路，城市高速，国道2主要包括高速道路，城市高速，国道，省道3主要包括高速道路，城市高速，国道，省道，县道4主要包括高速道路，城市高速，国道，省道，县道，乡镇村道5所有道路

实施例2：

本实施例中提供一种构建数字地图的道路网的装置，如图8所示，包括：

区域选择单元01，用于选择第一行政区划，获取与所述第一行政区划的距离在预设范围内的若干第二行政区划；

探索点获取单元02，用于获取第一行政区划的路径起点和路径终点，根据所述第一行政区划的路径起点和路径终点确定第一行政区划的探索点集合；

路网构建单元03，用于依次从每个探索点开始，获取到达所述第二行政区划的探索点的可通行路径，形成道路网。

其中，所述区域选择单元包括：

周边行政区划获取子单元，用于以所述第一行政区划的中心为圆心，以预设第一距离为半径，获取在该半径覆盖范围内的周边行政区划；

筛选子单元，用于将每个周边行政区划的中心分别与第一行政区划的中心连接，若连接线的夹角小于角度阈值，则删除距离第一行政区划中心远的一个或多个周边行政区划，剩余的周边行政区划为第二行政区划。

其中，所述探索点获取单元包括路径起点获取子单元，其包括：

道路结点选择子单元，用于以第一行政区划的中心为圆心，预设第二距离为半径，获取该半径范围内的道路结点；

夹角获取子单元，用于以所述道路结点为顶点，分别连接第一行政区划的中心和第二行政区划的中心，得到两条连线的夹角；

选择子单元，用于获取所述夹角接近180的道路结点的集合作为第一行政区划的路径起点。

本实施例提供的构建数字地图的道路网的装置，包括区域选择单元、探索点获取单元和路网构建单元，该方案实现了道路网的构建，提高了构建速度和效率。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

显然，上述实施例仅仅是为清楚地说明所作的举例，而并非对实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。而由此所引伸出的显而易见的变化或变动仍处于本发明创造的保护范围之中。