一种地图分割方法、装置、电子设备及存储介质

摘要

本申请提供了一种地图分割方法、装置、电子设备及存储介质，涉及地图分割技术领域，包括：针对每张待填充子图，执行以下处理：确定该待填充子图对应的第一连接点集合和第二连接点集合之间的第一差集；从第一差集中，确定目标连接点；将待划分道路集合中与目标连接点对应的多条目标道路填充至该待填充子图，并将多条目标道路从待划分道路集合中删除；利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充；由填充完毕的多张待填充子图，完成对待处理地图的分割处理。本申请通过连接点与道路之间的整体关系对地图中的道路进行子图拆分，保证了道路拓扑结构完整性，提高分割效率。

权利要求

1.一种地图分割方法，其特征在于，所述方法包括：获取待处理地图对应的待划分道路集合、待划分连接点集合和多张待填充子图，所述待划分道路集合包括多条道路，待划分连接点集合包括所述多条道路之间的多个连接点；

针对每张待填充子图，执行以下处理：

确定该待填充子图对应的第一连接点集合和第二连接点集合之间的第一差集，所述第一连接点集合包括覆盖该待填充子图中的全部道路的多个连接点，所述第二连接点集合包括所有邻接边均在该待填充子图中的多个连接点；

从所述第一差集中，确定目标连接点；

将所述待划分道路集合中与所述目标连接点对应的多条目标道路填充至该待填充子图，并将所述多条目标道路从所述待划分道路集合中删除；

利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充；

由填充完毕的多张待填充子图，完成对待处理地图的分割处理；

其中，所述从所述第一差集中，确定目标连接点的步骤包括：判断所述第一差集是否为空；

若所述第一差集为空，则确定所述待划分连接点集合与第一连接点集合之间的第二差集；

根据所述第二差集中每个连接点对应的提取概率，从所述第二差集对应的多个连接点中，随机抽取一连接点确定为目标连接点；

若所述第一差集不为空，则针对所述第一差集中每个连接点，确定该连接点在所述第二差集中的目标邻接连接点数目；

将所述第一差集中的目标邻接连接点数目最少的连接点，确定为目标连接点；

所述目标道路包括第一目标道路和第二目标道路，

其中，通过以下方式将所述待划分道路集合中与所述目标连接点对应的多条目标道路填充至每个待填充子图：将该待填充子图对应的目标连接点分别并入所述第一连接点集合和第二连接点集合；

将所述目标连接点对应的多个目标邻接连接点并入所述第一连接点集合；

针对每个目标邻接连接点，将该目标邻接连接点与所述目标连接点之间对应的第一目标道路和该目标邻接连接点与第一连接点集合中每个连接点之间对应的第二目标道路，并入该待填充子图；

所述利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充的步骤包括：获取该待填充子图对应的道路数量以及道路权重和；

分别判断该张待填充子图对应的道路数量是否小于预设道路数以及所述道路权重和是否小于第一均衡因子，所述预设道路数为第二均衡因子与所述待处理地图对应的总道路条数的乘积与待填充子图数量之间的比值；

若该待填充子图对应的道路数量小于预设道路数、所述道路权重和小于第一均衡因子，则确定该待填充子图满足预设约束条件，则返回执行从所述第一差集中，确定目标连接点；

若该待填充子图对应的道路数量大于预设道路数和/或所述道路权重和大于第一均衡因子，则确定该张待填充子图不满足预设约束条件，完成对该待填充子图的填充；

在完成对每张待填充子图的填充后，所述方法还包括：判断待划分道路集合中是否为空；

若所述待划分道路集合为空，则直接完成对待处理地图的分割处理；

若所述待划分道路集合不为空，则对待划分道路集合中剩余的道路进行再分配，直至所述待划分道路集合为空。

2.根据权利要求1所述的方法，其特征在于，通过以下方式对所述待划分道路集合中剩余的道路进行再分配：若每个待填充子图对应的第一差集均为空，则从多张待填充子图中随机选取一个确定为目标待填充子图，从所述待划分道路集合剩余的道路所包含的所有连接点中随机选取一个确定为目标连接点；

将所述待划分道路集合中与目标连接点对应的多条目标道路填充至所述目标待填充子图。

3.根据权利要求2所述的方法，其特征在于，针对每个待填充子图，执行以下处理：若该待填充子图对应的第一差集不为空，则执行所述从所述第一差集中，确定目标连接点，以将所述目标连接点在待划分道路集合中对应的多条目标道路填充至该待填充子图。

4.一种地图分割装置，其特征在于，所述装置包括：第一获取模块，用于获取待处理地图对应的待划分道路集合、待划分连接点集合和多张待填充子图，所述待划分道路集合包括多条道路，待划分连接点集合包括所述多条道路之间的多个连接点；

第一确定模块，用于针对每张待填充子图，确定该待填充子图对应的第一连接点集合和第二连接点集合之间的第一差集，所述第一连接点集合包括覆盖该待填充子图中的全部道路的多个连接点，所述第二连接点集合包括所有邻接边均在该待填充子图中的多个连接点；

第二确定模块，用于针对每张待填充子图，从所述第一差集中，确定目标连接点；

第一填充模块，用于针对每张待填充子图，将所述待划分道路集合中与所述目标连接点对应的多条目标道路填充至该待填充子图，并将所述多条目标道路从所述待划分道路集合中删除；

约束模块，用于针对每张待填充子图，利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充；

第二填充模块，由填充完毕的多张待填充子图，完成对待处理地图的分割处理；

其中，第二确定模块还用于：

判断所述第一差集是否为空；

若所述第一差集为空，则确定所述待划分连接点集合与第一连接点集合之间的第二差集；

根据所述第二差集中每个连接点对应的提取概率，从所述第二差集对应的多个连接点中，随机抽取一连接点确定为目标连接点；

若所述第一差集不为空，则针对所述第一差集中每个连接点，确定该连接点在所述第二差集中的目标邻接连接点数目；

将所述第一差集中的目标邻接连接点数目最少的连接点，确定为目标连接点；

所述目标道路包括第一目标道路和第二目标道路，

其中，第一填充模块还用于：

将该待填充子图对应的目标连接点分别并入所述第一连接点集合和第二连接点集合；

将所述目标连接点对应的多个目标邻接连接点并入所述第一连接点集合；

针对每个目标邻接连接点，将该目标邻接连接点与所述目标连接点之间对应的第一目标道路和该目标邻接连接点与第一连接点集合中每个连接点之间对应的第二目标道路，并入该待填充子图；

约束模块还用于：

获取该待填充子图对应的道路数量以及道路权重和；

分别判断该张待填充子图对应的道路数量是否小于预设道路数以及所述道路权重和是否小于第一均衡因子，所述预设道路数为第二均衡因子与所述待处理地图对应的总道路条数的乘积与待填充子图数量之间的比值；

若该待填充子图对应的道路数量小于预设道路数、所述道路权重和小于第一均衡因子，则确定该待填充子图满足预设约束条件，则返回执行从所述第一差集中，确定目标连接点；

若该待填充子图对应的道路数量大于预设道路数和/或所述道路权重和大于第一均衡因子，则确定该张待填充子图不满足预设约束条件，完成对该待填充子图的填充；

地图分割模块还包括分割补全模块，分割补全模块用于：判断待划分道路集合中是否为空；

若所述待划分道路集合为空，则直接完成对待处理地图的分割处理；

若所述待划分道路集合不为空，则对待划分道路集合中剩余的道路进行再分配，直至所述待划分道路集合为空。

5.一种电子设备，其特征在于，包括：处理器、存储器和总线，所述存储器存储有所述处理器可执行的机器可读指令，当电子设备运行时，所述处理器与所述存储器之间通过所述总线进行通信，所述机器可读指令被所述处理器运行时执行如权利要求1至3任一所述的地图分割方法的步骤。

6.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器运行时执行如权利要求1至3任一所述的地图分割方法的步骤。

说明书

一种地图分割方法、装置、电子设备及存储介质

技术领域

[0001] 本申请涉及地图分割技术领域，尤其涉及一种地图分割方法、装置、电子设备及存储介质。

背景技术

[0002] 地图分割指将一个大规模的地图数据集或者图片分割成许多小块的过程，在地图应用中，地图分割可以帮助用户更快速地加载和浏览地图数据，同时也有助于进行地图数据的处理和分析。

[0003] 现有技术中的地图分割方法主要包括：

[0004] 网格化地图分割算法：将地图划分成固定大小的矩形网格，每个网格通常包含相同数量的像素或者地理单元。

[0005] 导航网格(navigation mesh)算法：将一个复杂的三维空间地图分割成一个或多个可用于路径规划的凸多边形区域，以便进行高效的导航。

[0006] 基于图(graph)的路网划分算法：利用图的分割算法将其划分为多个连通子图，每个子图代表一个划分后的子区域。

[0007] 对于网格化地图分割算法和导航网格算法：利用网格划分破坏了道路完整性，且Opendrive格式地图并没有给出道路上每个点的世界坐标，需要进行转化计算量大，降低分割效率；

[0008] 对于基于图的路网划分算法，仅仅以道路连接点(junction)为顶点划分，处理的对象为顶点，同样破坏道路完整性。

发明内容

[0009] 有鉴于此，本申请的目的在于至少提供一种地图分割方法、装置、电子设备及存储介质，通过连接点与道路之间的整体关系对地图中的道路进行子图拆分，保证了道路拓扑结构完整性，提高分割效率。

[0010] 本申请主要包括以下几个方面：

[0011] 第一方面，本申请实施例提供一种地图分割方法，方法包括：获取待处理地图对应的待划分道路集合、待划分连接点集合和多张待填充子图，待划分道路集合包括多条道路，待划分连接点集合包括多条道路之间的多个连接点；针对每张待填充子图，执行以下处理：确定该待填充子图对应的第一连接点集合和第二连接点集合之间的第一差集，第一连接点集合包括覆盖该待填充子图中的全部道路的多个连接点，第二连接点集合包括所有邻接边均在该待填充子图中的多个连接点；从第一差集中，确定目标连接点；将待划分道路集合中与目标连接点对应的多条目标道路填充至该待填充子图，并将多条目标道路从待划分道路集合中删除；利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充；由填充完毕的多张待填充子图，完成对待处理地图的分割处理。

[0012] 在一种可能的实施方式中，从第一差集中，确定目标连接点的步骤包括：

[0013] 判断第一差集是否为空；若第一差集为空，则确定待划分连接点集合与第一连接点集合之间的第二差集；根据第二差集中每个连接点对应的提取概率，从第二差集对应的多个连接点中，随机抽取一连接点确定为目标连接点；若第一差集不为空，则针对第一差集中每个连接点，确定该连接点在第二差集中的目标邻接连接点数目；将第一差集中的目标邻接连接点数目最少的连接点，确定为目标连接点。

[0014] 在一种可能的实施方式中，目标道路包括第一目标道路和第二目标道路，其中，通过以下方式将待划分道路集合中与目标连接点对应的多条目标道路填充至每个待填充子图：将该待填充子图对应的目标连接点分别并入第一连接点集合和第二连接点集合；将目标连接点对应的多个目标邻接连接点并入第一连接点集合；针对每个目标邻接连接点，将该目标邻接连接点与目标连接点之间对应的第一目标道路和该目标邻接连接点与第一连接点集合中每个连接点之间对应的第二目标道路，并入该待填充子图。

[0015] 在一种可能的实施方式中，利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充的步骤包括：获取该待填充子图对应的道路数量以及道路权重和；分别判断该张待填充子图对应的道路数量是否小于预设道路数以及道路权重和是否小于第一均衡因子，预设道路数为第二均衡因子与待处理地图对应的总道路条数的乘积与待填充子图数量之间的比值；若该待填充子图对应的道路数量小于预设道路数、道路权重和小于第一均衡因子，则确定该待填充子图满足预设约束条件，则返回执行从第一差集中，确定目标连接点；若该待填充子图对应的道路数量大于预设道路数和/或道路权重和大于第一均衡因子，则确定该张待填充子图不满足预设约束条件，完成对该待填充子图的填充。

[0016] 在一种可能的实施方式中，在完成对每张待填充子图的填充后，方法还包括：判断待划分道路集合中是否为空；若待划分道路集合为空，则直接完成对待处理地图的分割处理；若待划分道路集合不为空，则对待划分道路集合中剩余的道路进行再分配，直至待划分道路集合为空。

[0017] 在一种可能的实施方式中，通过以下方式对待划分道路集合中剩余的道路进行再分配：若每个待填充子图对应的第一差集均为空，则从多张待填充子图中随机选取一个确定为目标待填充子图，从待划分道路集合剩余的道路所包含的所有连接点中随机选取一个确定为目标连接点；将待划分道路集合中与目标连接点对应的多条目标道路填充至目标待填充子图。

[0018] 在一种可能的实施方式中，针对每个待填充子图，执行以下处理：若该待填充子图对应的第一差集不为空，则执行从第一差集中，确定目标连接点，以将目标连接点在待划分道路集合中对应的多条目标道路填充至该待填充子图。

[0019] 第二方面，本申请实施例还提供一种地图分割装置，装置包括：第一获取模块，用于获取待处理地图对应的待划分道路集合、待划分连接点集合和多张待填充子图，待划分道路集合包括多条道路，待划分连接点集合包括多条道路之间的多个连接点；第一确定模块，用于针对每张待填充子图，确定该待填充子图对应的第一连接点集合和第二连接点集合之间的第一差集，第一连接点集合包括覆盖该待填充子图中的全部道路的多个连接点，第二连接点集合包括所有邻接边均在该待填充子图中的多个连接点；第二确定模块，用于针对每张待填充子图，从第一差集中，确定目标连接点；第一填充模块，用于针对每张待填充子图，将待划分道路集合中与目标连接点对应的多条目标道路填充至该待填充子图，并将多条目标道路从待划分道路集合中删除；约束模块，用于针对每张待填充子图，利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充；第二填充模块，由填充完毕的多张待填充子图，完成对待处理地图的分割处理。

[0020] 第三方面，本申请实施例还提供一种电子设备，包括：处理器、存储器和总线，所述存储器存储有所述处理器可执行的机器可读指令，当电子设备运行时，所述处理器与所述存储器之间通过所述总线进行通信，所述机器可读指令被所述处理器运行时执行上述第一方面或第一方面中任一种可能的实施方式中所述的地图分割方法的步骤。

[0021] 第四方面，本申请实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器运行时执行上述第一方面或第一方面中任一种可能的实施方式中所述的地图分割方法的步骤。

[0022] 本申请实施例提供的一种地图分割方法、装置、电子设备及存储介质，包括：针对每张待填充子图，执行以下处理：确定该待填充子图对应的第一连接点集合和第二连接点集合之间的第一差集；从第一差集中，确定目标连接点；将待划分道路集合中与目标连接点对应的多条目标道路填充至该待填充子图，并将多条目标道路从待划分道路集合中删除；利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充；由填充完毕的多张待填充子图，完成对待处理地图的分割处理。本申请通过连接点与道路之间的整体关系对地图中的道路进行子图拆分，保证了道路拓扑结构完整性，提高分割效率。

[0023] 本申请有益之处在于：

[0024] 1、实现对Opendrive格式地图数据的快速处理，提高地图分割效率；

[0025] 2、保持道路完整性以及道路拓扑结构完整性(比如十字路口倾向于划分在同一地图)；

[0026] 3、保证了分割后的小地图负载均衡。

[0027] 为使本申请的上述目的、特征和优点能更明显易懂，下文特举较佳实施例，并配合所附附图，作详细说明如下。

附图说明

[0028] 为了更清楚地说明本申请实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本申请的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他相关的附图。

[0029] 图1示出了本申请实施例所提供的一种地图分割方法的流程图；

[0030] 图2示出了本申请实施例提供的一种G(V，E)格式示意图；

[0031] 图3示出了本申请实施例提供的一种地图分割装置的结构示意图；

[0032] 图4示出了本申请实施例所提供的一种电子设备的结构示意图。

具体实施方式

[0033] 为使本申请实施例的目的、技术方案和优点更加清楚，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，应当理解，本申请中的附图仅起到说明和描述的目的，并不用于限定本申请的保护范围。另外，应当理解，示意性的附图并未按实物比例绘制。本申请中使用的流程图示出了根据本申请的一些实施例实现的操作。应当理解，流程图的操作可以不按顺序实现，没有逻辑的上下文关系的步骤可以反转顺序或者同时实施。此外，本领域技术人员在本申请内容的指引下，可以向流程图添加一个或多个其他操作，也可以从流程图中移除一个或多个操作。

[0034] 另外，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本申请实施例的组件可以以各种不同的配置来布置和设计。因此，以下对在附图中提供的本申请的实施例的详细描述并非旨在限制要求保护的本申请的范围，而是仅仅表示本申请的选定实施例。基于本申请的实施例，本领域技术人员在没有做出创造性劳动的前提下所获得的全部其他实施例，都属于本申请保护的范围。

[0035] 对于交通流/虚拟城市以10万大为单位的环境车在地图上运行，仿真软件由于性能原因需要分割地图以并行仿真渲染。具体可以描述如下：给定任意大地图(例如Opendrive标准格式)，将其均匀分成K份子图，使得任意位置的点(由Vissim等软件给出的交通车的位置)能够快速查询其所在子图编号。

[0036] 现有技术中，地图分割算法研究工作主要分为以下几类方法：

[0037] 1. 网格化地图分割算法：是一种常见的地图分割方法，它将地图分割成多个规则的网格，以便进行高效的数据加载和处理。该算法通常包括的步骤有：网格化，将地图划分成固定大小的矩形网格，每个网格通常包含相同数量的像素或者地理单元；网格索引：对每个网格进行编号，并建立一个索引表，以便快速访问每个网格的数据。

[0038] 2. 导航网格算法：是一种用于游戏开发、机器人导航、虚拟现实等领域的地图分割算法，其主要目的是将一个复杂的三维空间地图分割成一个或多个可用于路径规划的凸多边形区域，以便进行高效的导航。

[0039] 3. 基于图的路网划分算法：是一种将道路网格划分为具有一定属性的子区域的算法，它使用图论的方法，将道路网格表示为一个图，利用图的分割算法将其划分为多个连通子图，每个子图代表一个划分后的子区域。Ali Kemal Sinop首先通过执行随机游走将高度连接的道路口聚合，随后利用惯性流算法将路网均衡地分割为两部分。

[0040] 通过网格化算法/导航网格进行地图分割，其缺点包括了：

[0041] a.Opendrive格式地图并没有给出道路上每个点的世界坐标，需要进行转化计算量大；

[0042] b.网格划分将破坏道路的完整性，环境车在不同小地图间来回跳跃；

[0043] c.难以控制不同网格的交通流量，产生数据不均衡问题。

[0044] 基于图的路网划分算法，其缺点包括了：

[0045] A.以道路连接点(junction)为顶点划分，处理的对象为顶点，破坏道路完整性；

[0046] B.关注不同划分区域之间的道路联通，对同一个区域内的负载、流量没有约束；

[0047] C.划分后的不同区域会产生较大差异(比如道路数及其它信息)。

[0048] 基于此，本申请实施例提供了一种地图分割方法、装置、电子设备及存储介质，通过连接点与道路之间的整体关系对地图中的道路进行子图拆分，保证了道路拓扑结构完整性，提高分割效率，具体如下：

[0049] 请参阅图1，图1示出了本申请实施例所提供的一种地图分割方法的流程图。如图1所示，本申请实施例提供的地图分割方法，包括以下步骤：

[0050] S100、获取待处理地图对应的待划分道路集合、待划分连接点集合和多张待填充子图。

[0051] 本申请中，待处理地图为Opendrive格式，可以先按照连接点（junction）属性和道路属性，将Opendrive格式的待处理地图转换为图G(V，E)的数据格式，表示待划分连接点集合，E表示待划分道路集合，待划分道路集合E包括多条道路，待划分连接点集合 包括多条道路之间的多个连接点。

[0052] 本申请直接基于Opendrive格式的地图进行分割，降低了数据转化成本，提高分割效率。

[0053] 请参阅图2，图2示出了本申请实施例提供的一种G(V，E)格式示意图。在图2中，包括多条道路L1 L12，以及多条道路L1 L12对应的多个连接点T1 T12。~ ~ ~

[0054] S200、针对每张待填充子图，确定该待填充子图对应的第一连接点集合和第二连接点集合之间的第一差集。

[0055] 其中，第一连接点集合包括覆盖该待填充子图中的全部道路的多个连接点，第二连接点集合包括所有邻接边均在该待填充子图中的多个连接点。

[0056] 在一具体实施例中，针对第张待填充子图对应的第一连接点集合 ，其中， 表示第张待填充子图中道路集合， 即表示覆盖第张待填充子图中的全部道路的多个连接点所形成的第一连接点集合 ， 则表示第 张待填充子图对应的第二连接点集合，第一差集可表示为 。

[0057] 在具体实施例中，若第 张待填充子图对应的第一连接点集合 中的全部道路包括道路L1、道路L2和道路L3，第一连接点集合 包括连接点T1、连接点T2、连接点T3和连接点T4，第二连接点集合 包括连接点T1、连接点T2和连接点T3，则第一差集包括连接点T4。

[0058] 在本申请中，在获取到多张待填充子图后，需要先将每张待填充子图对应的第一连接点集合、第二连接点集合以及道路集合初始化为空集，然后再对每张待填充子图进行填充。

[0059] S300、针对每张待填充子图，从第一差集中，确定目标连接点。

[0060] 在一优选实施例中，从第一差集中，确定目标连接点的步骤包括：

[0061] 判断第一差集是否为空，若第一差集为空，则确定待划分连接点集合与第一连接点集合之间的第二差集，根据第二差集中每个连接点对应的提取概率，从第二差集对应的多个连接点中，随机抽取一连接点确定为目标连接点。

[0062] 具体的，若待填充子图对应的第一差集为空，说明对于待填充子图中的每个连接点来说，该连接点相关的全部邻接边均处于待填充子图中或待填充子图此时还未被填充，此时需要从待划分连接点集合与第一连接点集合之间的第二差集中抽取一个作为目标连接点，其中，第二差集中每个连接点对应的提取概率= 表示连接点T的邻接连接点数量。

[0063] 若第一差集不为空，则针对第一差集中每个连接点，确定该连接点在第二差集中的目标邻接连接点数目，将第一差集中的目标邻接连接点数目最少的连接点，确定为目标连接点。

[0064] 其中，针对第一差集中每个连接点，其对应的多个邻接连接点，可能有一部分已经存在于第一差集中，而目标邻接连接点则是指存在于第二差集中的邻接连接点，第一差集于第二差集之间的交际始终为空。

[0065] 若第 张待填充子图对应的第一连接点集合 包括连接点T6和连接点T7，第二连接点集合 为空，则第一差集包括连接点T6和连接点T7，即第一差集不为空，此时连接点T6对应的邻接连接点数目为1，目标邻接连接点数目也为1，连接点T7对应的邻接连接点数目为2，目标邻接连接点数目也为2，则此时将连接点T6确定为目标连接点。

[0066] S400、针对每张待填充子图，将待划分道路集合中与目标连接点对应的多条目标道路填充至该待填充子图，并将多条目标道路从待划分道路集合中删除。

[0067] 在一优选实施例中，目标道路包括第一目标道路和第二目标道路，通过以下方式将待划分道路集合中与目标连接点对应的多条目标道路填充至每个待填充子图：

[0068] 将该待填充子图对应的目标连接点分别并入第一连接点集合和第二连接点集合，将目标连接点对应的多个目标邻接连接点并入第一连接点集合，针对每个目标邻接连接点，将该目标邻接连接点与目标连接点之间对应的第一目标道路和该目标邻接连接点与第一连接点集合中每个连接点之间对应的第二目标道路，并入该待填充子图。

[0069] 具体的，将多个目标邻接连接点并入第一连接点集合之后，此时，针对每个目标邻接连接点，若目标连接点或第一连接点集合内的每个连接点与该目标邻接连接点之间存在道路，则将该道路添加至该待填充子图对应的道路集合，也就是说，每次添加目标连接点至第二连接点集合时，与目标连接点相关的所有道路（包括第一目标道路和第二目标道路）也会加入至添加至该待填充子图对应的道路集合，这样有助于保持道路交叉口的拓扑结构。

[0070] 如上述实施例，对于目标连接点T6，将目标连接点T6对应的目标邻接连接点T5并入第 张待填充子图中，同时将T5分别并入第张待填充子图对应的第一连接点集合 和第二连接点集合 ，然后将目标连接点T6对应的目标邻接连接点T5之间的道路L5并入第张待填充子图对应的道路集合 中。

[0071] S500、针对每张待填充子图，利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充。

[0072] 在一优选实施例中，步骤S500包括：

[0073] 获取该待填充子图对应的道路数量以及道路权重和，分别判断该张待填充子图对应的道路数量是否小于预设道路数以及道路权重和是否小于第一均衡因子，若该待填充子图对应的道路数量小于预设道路数、道路权重和小于第一均衡因子，则确定该待填充子图满足预设约束条件，则返回执行从第一差集中，确定目标连接点；若该待填充子图对应的道路数量大于预设道路数和/或道路权重和大于第一均衡因子，则确定该张待填充子图不满足预设约束条件，完成对该待填充子图的填充。

[0074] 其中，预设道路数为第二均衡因子与待处理地图对应的总道路条数的乘积与待填充子图数量之间的比值，具体的，对于第i个待填充子图，针对预设道路数对应的约束，可以表示为判断：

[0075]

[0076] 其中， 表示第i个待填充子图中道路数量， 表示预设道路数，

[0077] 表示第二均衡因子， 表示待处理地图对应的总道路条数，K表示待填充子图数量。

[0078] 针对道路权重和对应的约束，可以表示为判断：

[0079]

[0080] 其中， 表示第i个待填充子图中连接点m和连接点n之间的道路对应的权重，表示第i个待填充子图的道路集合对应的道路权重和， 表示第一均衡因子。

[0081] 若待填充子图满足预设约束条件，说明此时待填充子图还存在可填充空间，此时可返回执行步骤S300，若待填充子图不满足预设约束条件，说明此时待填充子图已填充完毕。

[0082] 本申请通过上述约束条件，可以确保最后分割得到的待填充子图处于负载均衡状态。

[0083] 在一优选实施例中，在完成对每张待填充子图的填充后，方法还包括：

[0084] 判断待划分道路集合中是否为空，若待划分道路集合为空，则直接完成对待处理地图的分割处理，若待划分道路集合不为空，则对待划分道路集合中剩余的道路进行再分配，直至待划分道路集合为空。

[0085] 在全部待填充子图都满足对应的预设约束条件后，待划分道路集合中可能还存在未被分配的道路，对于未被分配的道路还需要进行分割补全，即将未被分配划分至对应的待填充子图，以完成对待处理地图中全部道路的分配。

[0086] 在另一优选实施例中，通过以下方式对待划分道路集合中剩余的道路进行再分配：

[0087] 若每个待填充子图对应的第一差集均为空，则从多张待填充子图中随机选取一个确定为目标待填充子图，从待划分连道路集合剩余的道路所包含的所有连接点中随机选取一个确定为目标连接点，将待划分道路集合中与目标连接点对应的多条目标道路填充至目标待填充子图。

[0088] 在一优选实施例中，针对每个待填充子图，执行以下处理：

[0089] 若该待填充子图对应的第一差集不为空，则执行从所述第一差集中，确定目标连接点，以将目标连接点在待划分道路集合中对应的多条目标道路填充至该待填充子图。

[0090] 具体的，若待填充子图不满足预设约束条件，且第一差集不为空，此时在不考虑预设约束条件的情况下，将第一差集中的连接点对应的道路全部并入至待填充子图，保证待填充子图的完整性。

[0091] S600、由填充完毕的多张待填充子图，完成对待处理地图的分割处理。

[0092] 基于同一申请构思，本申请实施例中还提供了与上述实施例提供的地图分割方法对应的地图分割装置，由于本申请实施例中的装置解决问题的原理与本申请上述实施例的地图分割方法相似，因此装置的实施可以参见方法的实施，重复之处不再赘述。

[0093] 请参阅图3，图3示出了本申请实施例提供的一种地图分割装置的结构示意图。如图3所示，地图分割装置包括：

[0094] 第一获取模块700，用于获取待处理地图对应的待划分道路集合、待划分连接点集合和多张待填充子图，待划分道路集合包括多条道路，待划分连接点集合包括多条道路之间的多个连接点。

[0095] 第一确定模块710，用于针对每张待填充子图，确定该待填充子图对应的第一连接点集合和第二连接点集合之间的第一差集，第一连接点集合包括覆盖该待填充子图中的全部道路的多个连接点，第二连接点集合包括所有邻接边均在该待填充子图中的多个连接点。

[0096] 第二确定模块720，用于针对每张待填充子图，从第一差集中，确定目标连接点。

[0097] 第一填充模块730，用于针对每张待填充子图，将待划分道路集合中与目标连接点对应的多条目标道路填充至该待填充子图，并将多条目标道路从待划分道路集合中删除。

[0098] 约束模块740，用于针对每张待填充子图，利用预设约束条件对该待填充子图中的道路进行约束，以完成对该待填充子图的填充。

[0099] 第二填充模块750，由填充完毕的多张待填充子图，完成对待处理地图的分割处理。

[0100] 优选的，第二确定模块720还用于：判断第一差集是否为空；

[0101] 若第一差集为空，则确定待划分连接点集合与第一连接点集合之间的第二差集，根据第二差集中每个连接点对应的提取概率，从第二差集对应的多个连接点中，随机抽取一连接点确定为目标连接点；

[0102] 若第一差集不为空，则针对第一差集中每个连接点，确定该连接点在第二差集中的目标邻接连接点数目，将第一差集中的目标邻接连接点数目最少的连接点，确定为目标连接点。

[0103] 优选的，目标道路包括第一目标道路和第二目标道路，第一填充模块730还用于：

[0104] 将该待填充子图对应的目标连接点分别并入第一连接点集合和第二连接点集合，将目标连接点对应的多个目标邻接连接点并入第一连接点集合；针对每个目标邻接连接点，将该目标邻接连接点与目标连接点之间对应的第一目标道路和该目标邻接连接点与第一连接点集合中每个连接点之间对应的第二目标道路，并入该待填充子图。

[0105] 优选的，约束模块740还用于：

[0106] 获取该待填充子图对应的道路数量以及道路权重和；

[0107] 分别判断该张待填充子图对应的道路数量是否小于预设道路数以及道路权重和是否小于第一均衡因子，预设道路数为第二均衡因子与待处理地图对应的总道路条数的乘积与待填充子图数量之间的比值，若该待填充子图对应的道路数量小于预设道路数、道路权重和小于第一均衡因子，则确定该待填充子图满足预设约束条件，则返回执行从第一差集中，确定目标连接点，若该待填充子图对应的道路数量大于预设道路数和/或道路权重和大于第一均衡因子，则确定该张待填充子图不满足预设约束条件，完成对该待填充子图的填充。

[0108] 地图分割装置还包括分割补全模块（图中未示出），用于：

[0109] 判断待划分道路集合中是否为空，若待划分道路集合为空，则直接完成对待处理地图的分割处理，若待划分道路集合不为空，则对待划分道路集合中剩余的道路进行再分配，直至待划分道路集合为空。

[0110] 优选的，分割补全模块还用于：

[0111] 若每个待填充子图对应的第一差集均为空，则从多张待填充子图中随机选取一个确定为目标待填充子图，从待划分道路集合剩余的道路所包含的所有连接点中随机选取一个确定为目标连接点；

[0112] 将待划分道路集合中与目标连接点对应的多条目标道路填充至目标待填充子图。

[0113] 优选的，分割补全模块还用于：针对每个待填充子图：若该待填充子图对应的第一差集不为空，则执行从第一差集中，确定目标连接点，以将目标连接点在待划分道路集合中对应的多条目标道路填充至该待填充子图。

[0114] 基于同一申请构思，请参阅图4，图4示出了本申请实施例提供的一种电子设备的结构示意图，电子设备800包括：处理器810、存储器820和总线830，所述存储器820存储有所述处理器810可执行的机器可读指令，当电子设备800运行时，所述处理器810与所述存储器820之间通过所述总线830进行通信，所述机器可读指令被所述处理器810运行时执行如上述实施例中提供的地图分割方法的步骤。

[0115] 基于同一申请构思，本申请实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器运行时执行上述实施例提供的地图分割方法的步骤。

[0116] 所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统和装置的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。在本申请所提供的几个实施例中，应所述理解到，所揭露的系统、装置和方法，可以通过其它的方式实现。以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，又例如，多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些通信接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

[0117] 所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

[0118] 另外，在本申请各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。

[0119] 所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个处理器可执行的非易失的计算机可读取存储介质中。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分或者所述技术方案的部分可以以软件产品的形式体现出来，所述计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备（可以是个人计算机，服务器，或者网络设备等）执行本申请各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器（Read‑Only Memory，ROM）、随机存取存储器（Random Access Memory，RAM）、磁碟或者光盘等各种可以存储程序代码的介质。

[0120] 以上仅为本申请的具体实施方式，但本申请的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本申请揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本申请的保护范围之内。因此，本申请的保护范围应以权利要求的保护范围为准。