路网拓扑图的划分方法、装置、设备及计算机程序产品.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113821550A(43)申请公布日2021.12.21(21)申请号202111384707.3(22)申请日2021.11.22(71)申请人腾讯科技（深圳）有限公司地址518057广东省深圳市南山区高新区科技中一路腾讯大厦35层(72)发明人张龙李伟征(74)专利代理机构广州三环专利商标代理有限公司44202代理人熊永强杜维(51)Int.Cl.G06F16/2458(2019.01)G06F16/29(2019.01)G06F16/22(2019.01)G06F16/23(2019.01)权利要求书3页说明书24页附图10页(54)发明名称路网拓扑图的划分方法、装置、设备及计算机程序产品(57)摘要本申请公开一种路网拓扑图的划分方法、装置、设备及计算机程序产品，可应用于地图领域；方法包括：获取当前版本路网数据的当前顶层路网拓扑图，以及前一版本路网数据的前一顶层路网拓扑图的划分信息；遍历当前顶层路网拓扑图的各个连通分支，扫描当前遍历的当前连通分支中的各顶点，并在检测到当前扫描的当前顶点位于前一顶层路网拓扑图中时，将划分信息所指示的当前顶点对应的单元图作为候选单元图；根据候选单元图的属性信息和启发条件之间的条件关系，确定当前顶点的目标划分方式；按照目标划分方式对当前顶点进行单元图划分，以确定当前顶点对应的目标单元图。通过本申请，可在一定程度上提升路网拓扑图的划分效率和划分结果的准确性。CN113821550ACN113821550A权利要求书1/3页1.一种路网拓扑图的划分方法，其特征在于，包括：获取当前版本路网数据的当前顶层路网拓扑图，以及前一版本路网数据的前一顶层路网拓扑图的划分信息；所述划分信息用于指示：所述前一顶层路网拓扑图中的各个顶点对应的单元图；确定启发条件，所述启发条件是在统计分析一个或多个历史版本路网数据对应的单元图的属性信息后，根据统计分析结果所启发得到的；遍历所述当前顶层路网拓扑图的各个连通分支，扫描当前遍历的当前连通分支中的各顶点，并在检测到当前扫描的当前顶点位于所述前一顶层路网拓扑图中时，将所述划分信息所指示的所述当前顶点对应的单元图作为候选单元图；根据所述候选单元图的属性信息和所述启发条件之间的条件关系，确定所述当前顶点的目标划分方式；所述目标划分方式包括：基于所述候选单元图进行划分的划分方式，或基于所述当前连通分支的拓扑结构进行划分的划分方式；按照所述目标划分方式对所述当前顶点进行单元图划分，以确定所述当前顶点对应的目标单元图。2.如权利要求1所述的方法，其特征在于，所述根据所述候选单元图的属性信息和所述启发条件之间的条件关系，确定所述当前顶点的目标划分方式，包括：若所述条件关系包括所述候选单元图的属性信息满足所述启发条件的关系，则将基于所述当前连通分支的拓扑结构进行划分的划分方式，确定为所述当前顶点的目标划分方式；若所述条件关系包括所述候选单元图的属性信息不满足所述启发条件的关系，则将基于所述候选单元图进行划分的划分方式，确定为所述当前顶点的目标划分方式。3.如权利要求1或2所述的方法，其特征在于，所述目标划分方式包括：基于所述当前连通分支的拓扑结构进行划分的划分方式；在确定所述当前连通分支中的任一顶点对应的目标单元图后，所述任一顶点的状态处于已划分状态；所述按照所述目标划分方式对所述当前顶点进行单元图划分，以确定所述当前顶点对应的目标单元图，包括：基于所述当前连通分支的拓扑结构，在所述当前连通分支中搜索所述当前顶点的关联顶点；所述关联顶点是指：与所述当前顶点连通，且处于已划分状态的顶点；将所述关联顶点对应的目标单元图的单元图标识赋值给所述当前顶点，以将所述关联顶点对应的目标单元图确定为所述当前顶点对应的目标单元图。4.如权利要求3所述的方法，其特征在于，所述方法还包括：在搜索到所述关联顶点后，确定所述关联顶点对应的目标单元图的目标量级大小；若所述目标量级大小大于或等于量级大小阈值，则执行将所述关联顶点对应的目标单元图的单元图标识赋值给所述当前顶点的步骤；若所述目标量级大小小于所述量级大小阈值，则将所述候选单元图的单元图标识赋值给所述当前顶点，以将所述候选单元图确定为所述当前顶点对应的目标单元图。5.如权利要求3所述的方法，其特征在于，所述基于所述当前连通分支的拓扑结构，在所述当前连通分支中搜索所述当前顶点的关联顶点，包括：以所述当前顶点为中心并采用泛洪法按照广度优先的搜索原则，基于所述当前连通分2CN113821550A权利要求书2/3页支的拓扑结构在所述当前连通分支中搜索所述当前顶点的关联顶点。6.如权利要求1或2所述的方法，其特征在于，所述目标划分方式包括：基于所述候选单元图进行划分的划分方式；所述按照所述目