A road connection logic method and application for efficient pathfinding in electronic maps

Abstract

The invention relates to a road connection logicalization method for high-efficiency way finding of an electronic map. The method comprises the following steps: extracting a node set directly connected with a center node according to the given center node; determining that physical auxiliary connection passing through the center node is optimal auxiliary connection or not in order to judge whether logic direct connection is added or not; judging connection beginning from an incoming node, passing through the center node and ending at an outgoing node is the optimal auxiliary connection or not, and adding the logic direct connection between the incoming node and the outgoing node when the connection total cost of any matching of all incoming node incoming interfaces and outgoing node outgoing interfaces is less than the bypass total cost by considering the crossing turning cost in order to obtain a direct connection interface matrix; regarding the physical connection passing through the center node, which is not the optimal auxiliary connection, as ineffective indirect connection, and finally obtaining a vector formed by the indexes of all the ineffective interfaces; and determining the current center node according to a processing sequence provided by node weighting with other node in a road network as the center node, and repeating above processes until all the nodes in the road network are logicalized.

Description

technical field [0001] The invention relates to the field of on-board electronic navigation, in particular to a road connection logic method and application of an electronic map for efficient pathfinding for organizing and constructing topology information related to pathfinding in the electronic map. Background technique [0002] With the increasing scale of the road network, the increasing complexity of road connectivity, and the increasing regional differences in road network distribution, the amount of information in electronic maps in local areas is gradually increasing, and the structure is becoming more and more complex; on the other hand, as With the continuous development of electronic map technology, the information carried by the roads and nodes in the electronic map is becoming more and more abundant. The increase in the amount of electronic map information will lead to an increase in the amount of topology information data related to pathfinding in the vehicle n...

AI Technical Summary

Problems solved by technology

The increase in the amount of electronic map information will lead to an increase in the amount of topology information data related to pathfinding in the vehicle navigation road network, which will reduce the speed and optimality of the existing pathfinding algorithms; in addition, the regional deterioration of the road network, a large number of non- The road network expressed by the urban area only contains a very small number of high-level roads, so that there are a lot of expansions that have little impact on the results in the long-distance pathfinding process, which affects the overall effect of pathfinding

Images