CN1920483A - Device for displaying road navigation track - Google Patents

Abstract

The invention relates to a device for providing road navigation road, especially a road traffic controller, wherein the electric map of its data memory contains the inlet top point from each cross road into said road and the road arc record relative to the inlet top point with steering limit character; the main controller controls the map edit modifier, based on the steering limit information at each port of cross road provided by the input module, to modify the road arc data of relative inlet top point of electric map; and the receiver/sender receives present position and target position information, to send the navigation path to the carrier terminal; the searcher extracts the electric map data and uses the steering limit character of each road arc to use the Di jkStra algorism to calculate out the shortest navigation path in top point serial type.

Description

A device for providing road navigation path

technical field

The invention relates to a road traffic control device for transmitting navigation instructions to vehicles.

technical background

The currently reported navigation center device that provides road navigation paths for vehicles is equipped with a main controller with a computer as the core, and a transceiver for receiving the vehicle's current position and destination information provided by the vehicle-mounted terminal and sending the navigation route data to the vehicle-mounted terminal. device, data storage device with electronic map, search device. Its transceiver will receive the vehicle's current location and destination information provided by the vehicle-mounted terminal and transfer it to the main controller. After the navigation path data is submitted to the main controller; under the control of the main controller, the transceiver sends the navigation path data obtained by the main controller to the vehicle terminal. After receiving the navigation route data, the vehicle-mounted terminal instructs the driver to drive the vehicle to the destination according to the navigation route combined with the vehicle position data measured by the vehicle's positioning device at any time. Since the current electronic map uses a simple road centerline model, each road is simplified into a polyline segment located in the middle of the road surface, and an intersection where the roads meet is recorded as a vertex of the abstract graph of the traffic network. A polyline segment separating two adjacent vertices is recorded as an arc in the transportation network abstract graph. Points on the road that curve but do not meet other roads are not considered vertices. Please see Figure 1. A crossing in the road is abstracted as a vertex and four road arcs connecting the vertex. In the electronic map, the crossing is recorded as vertex O and four vertices A adjacent to the connecting vertex O. , B, C, D four road arcs OA, OB, OC, OD. A vertex record data in an electronic map includes the longitude and latitude of the location, the number of road arcs connected to the vertex, and the index of each road arc record; a road arc record data includes the starting vertex number and end vertex of the road arc number and the length of the road arc. Please look at the abstract graph of the traffic network shown in Figure 2, the vertices V1, V2, ... V9, etc. are all vertices in the abstract graph of the traffic network; and the roads V1->V2, V1->V3, ... V8->V9, etc. Both are road arcs in the abstract graph of the transportation network. The electronic map of the transportation network is essentially the record data of vertices V1, V2, ... V9, and the record data of road arcs V1->V2, V1->V3, ... V8->V9. The searcher uses the standard DijkStra algorithm to extract vertex data and road arc data from the electronic map of the road centerline model, and calculates the navigation path data in the form of road vertex sequences based on the principle of the shortest path length. Comparing with Figure 2, calculating the shortest path from the starting point V1 to the ending point V9 in the traffic network is actually seeking a vertex sequence (assumed to be V1->V2->V4->V7->V9) so that the passing road arc (assumed The sum of the lengths of V1->V2, V2->V4, V4->V7, V7->V9) is the smallest. For simplicity, the road arc length is the actual length of the road before abstraction. The DijkStra algorithm is essentially based on the graph growth theory. In the case of a fixed starting point, it is determined that the current path must be the vertex of the shortest path in turn, and it cannot be terminated until the vertex with the shortest path matches the end point. When the DijkStra algorithm finds the shortest path, it always saves the previous vertex before the current vertex with the shortest path—the previous point, so the specific composition of the shortest path can be obtained by backtracking from the end point to the starting point. At present, the electronic map using the simple road centerline model and the searcher using the DijkStra algorithm cannot get the correct shortest path when there is a no-turn restriction at the road intersection. Please see Figure 3. It is known that from vertex S to vertex E The shortest path between them is vertex S->vertex P->vertex A->vertex O->vertex D->vertex Q->vertex E without any restrictions. If you cannot turn to vertex D when reaching vertex O from vertex A (such traffic control situations often occur in real life). Intuitively, at this time, the vertex E should be reached according to vertex S->vertex P->vertex A->vertex O->vertex C->vertex Q->vertex E, but in fact the path vertex S->vertex P->vertex B -> Vertex O -> Vertex D -> Vertex Q -> Vertex E may be more in line with the requirements in length. If vertex S->vertex P->vertex B->vertex O->vertex D->vertex Q->vertex E path length is less than vertex S->vertex P->vertex A->vertex O under the above turning constraints -> Vertex C -> Vertex Q -> Vertex E path length, DijkStra algorithm will fail at this time. Because according to the generation process of the above-mentioned DijkStra algorithm, vertex S->vertex P->vertex A->vertex O must be the shortest path from the starting point S to the ending point O, that is, the previous point of the vertex O must be the vertex during the calculation process A. In this way, when the calculation is completed and the path is traced back, it is impossible to obtain a more realistic shortest path vertex S->vertex P->vertex B->vertex O->vertex D->vertex Q->vertex E. Because the existing reported navigation center device that provides road navigation paths for vehicles cannot deal with the search problem of the shortest road navigation path that prohibits turning restrictions, it cannot meet the traffic control requirements that often occur at road intersections in real life. Under the circumstances, it is necessary to provide the vehicle with the shortest navigation path on the road.

Contents of the invention

The present invention aims to provide a device that can provide vehicles with the shortest road navigation path under the traffic control situation where there is no turning restriction at the road intersection.

The technical solution method of the present invention is: a kind of device that provides road navigation path, comprises master controller, transceiver, data memory, searcher; Data memory stores electronic map; Transceiver receives vehicle-mounted terminal to provide The current location and destination information of the vehicle is transferred to the main controller, and the navigation route data obtained by the main controller is sent to the vehicle terminal; the searcher extracts the electronic map data of the data storage under the control of the main controller and calculates according to the current location and destination of the vehicle The navigation path data in the form of the exit road vertex sequence is submitted to the main controller; it is characterized in that: the electronic map of the data storage includes the entry apex record of each road port entering the crossing at each crossing and the corresponding entry apex of each road port. The road arc record with turning restriction features; it also includes an input module and a map editor; under the control of the main controller, the map editor receives the turning restriction information modification of each road port of the intersection provided by the input module Edit the electronic map of the electronic map in the data memory and the corresponding road arc record of the intersection at the vertex; the searcher utilizes the turning restriction feature of the road arc record corresponding to each road port entry vertex, and uses the DijkStra algorithm to find the shortest path under the condition of turning restrictions at the intersection. Navigation path data.

In order to facilitate the man-machine dialogue when the map editor revises and edits an intersection data of the electronic map: the electronic map of the data storage has map editing format data and path search calculation format data; the map editing format data has road records of each road And the crossing record of each crossing, the road record of each road includes the road name, road number, the number of crossings in the road, and the number of each crossing in the road; the crossing record of each crossing includes the name of the crossing, the number of the crossing, the entry The number of vertices, the number of each entry vertex in the crossing; the path search calculation format data has the records of each entry vertex and the record of each road arc; each entry vertex record includes the entry vertex number, longitude, latitude, starting from it The number of road arcs at the starting point, the number of each road arc starting from it; the record of each road arc includes road arc number, starting vertex number, ending vertex number, passable sign, road arc length; map revision The process of modifying and editing an intersection data on the electronic map includes:

A. Obtain the crossing name from the input module through the main controller, or the names of the two roads where the crossing is located, and take out the crossing record in the map editing format data from the electronic map;

B. The main controller controls the input module to prompt the number of each entry vertex of the crossing and extracts the number of the entry vertex that needs to be modified and edited and the vehicle steering restriction from the input module;

C. Use the number of the entry vertex of the crossing in the map editing format data to find out the road arc record of the entry vertex of the crossing in the path search calculation format data as the starting point, select the corresponding road arc record according to the vehicle driving steering restriction condition and Write the state of the passable sign corresponding to the vehicle steering restriction condition into the road arc record of the electronic map route search calculation format data.

The recommended searcher process for searching the shortest navigation path with intersection turning constraints includes:

Step S1: Record the number of the departure vertex and the number of the destination crossing vertex, extract all entry vertex records and road arc records in the electronic map path search calculation format data, and establish a vertex state table and a road arc state table; , each incoming vertex is regarded as a column in the vertex state table. The data items in this column include the number of the current vertex, the number of the previous point, the current path length from the starting vertex to the current vertex, and the status of whether the shortest path is calculated. The previous point is the vertex before this vertex in the shortest path; in the electronic map, each road arc is regarded as a column in the road arc state table, and the data items in this column include the starting vertex number of this road arc, the current road arc The arc end vertex number, the length of this road arc, and the status of this road arc being accessed in the calculation;

Step S2: Initialize the previous point numbers of all vertices in the vertex state table as invalid values, the current path length is positive infinity, and the state is that the shortest path has not been calculated; initialize the state of all road arcs in the road arc state table as unvisited;

Step S3: Initialize the previous point of the starting vertex in the vertex state table as the starting vertex itself, and the current path length is 0;

Step S4: Take out the vertex in the vertex state table that has not yet calculated the shortest path and has the smallest current path length. If this step fails, the search fails and exits the search calculation; if the taken vertex is the destination vertex, the search is successful and then go to step S12;

Step S5: mark the state of the vertex taken out in step 4 in the vertex state table as the shortest path has been obtained;

Step S6: Find a road arc starting from the extracted vertex in the road arc state table that has not been visited, if not found, return to step S4 to process other vertices in the vertex state table;

Step S7: mark the state of the road arc as visited in the road arc state table;

Step S8: Check whether the passable identification data item of the road arc is passable, if not passable, then abandon the further search process of the road arc, and directly go to step S6 to process other road arcs;

Step S9: Check the terminating vertex pointed to by the road arc in the vertex state table, if the state is that the shortest path has been obtained, go directly to step S6 to search for other road arcs;

Step S10: check whether the starting vertex of the road arc in the vertex state table can be used as the previous point of the ending vertex it points to, if it cannot be used as the previous point, then directly go to step S6 to search for other road arcs;

Step S11: In the vertex state table, the previous point number of the end vertex pointed to by the road arc is rewritten as the start vertex number of the road arc, and the current path length of the end vertex pointed to by the road arc is the current path length of the start vertex of the road arc. Path length adds the length of this road arc, and changes over to S6 to search and process other road arcs;

Step S12: Backtrack the previous point from the destination vertex to the starting vertex according to the vertex state table, and then arrange in reverse order to obtain the specific composition of each vertex on the shortest path.

Especially for the situation that different types of road arcs should be treated differently: the road arc record includes the road grade of this road arc; the searcher searches for the shortest navigation path under the intersection turning restriction in the processing step S11, Use the road level adjustment weighting coefficient of the road arc to calculate the weighted length of the road arc, and replace the length of the road arc with the weighted length of the road arc to rewrite the current path length of the terminal vertex pointed to by the road arc in the vertex state table.

The device for providing the road navigation path of the present invention uses the two-line road model to process the data of each road crossing in the electronic map of the data storage in a multi-vertex manner, and enters the road at the port of each crossing to other ports to drive out from the vertices. The restriction features of arc-introduced turns are recorded in the corresponding road arc records, and it also solves the problem of distinguishing one-way roads from general two-way roads in urban traffic. The searcher uses the turn restriction feature information recorded by each road arc in the search process. Find the shortest path using DijkStra's algorithm. It solves the problem that the current electronic map using the simple road centerline model and the searcher using the DijkStra algorithm cannot obtain the correct shortest path when there is a prohibition of turning at the intersection of the road. The present invention adds a map editor and an input module on the basis of a navigation center device that provides road navigation paths for vehicles in the prior art, and solves the problem that often occurs in real life when road crossings are set at traffic control situations where steering is prohibited. Modify the problem of editing electronic maps in time; thus the device for providing road navigation paths of the present invention can adapt to dynamic changes in road traffic control, provide correct shortest road navigation path data for vehicles, and guide drivers to drive vehicles to their destinations according to the navigation path land. Set map edit format data and path search calculation format data in the electronic map of the data storage, wherein the data structure of the map edit format is designed according to people's habit of identifying geographical location and taking into account the characteristics of computer processing electronic map data records; it is convenient for map editing The editor modifies the man-machine dialogue when editing the intersection data of the electronic map. The data structure of the path search calculation format is designed according to the characteristics of computer processing electronic map data records; it is convenient for searchers to perform search operations. The process of modifying and editing the intersection data of the electronic map by the map editor is simple and concise, and the input module is arranged to give clear prompts. The operator can quickly input the dynamic changes of road traffic control into the electronic map, so that the device provides navigation path data High efficiency and high data validity. The searcher uses a vertex state table and a road arc state table and combines the passable identification data items of the road arc to successfully use the mature DijkStra algorithm to search for the shortest navigation path with intersection turning restrictions, and the processing process is highly reliable. In particular, the road arc record contains the road level of the road arc; during the search process, the searcher uses the road level adjustment weighting coefficient of the road arc to calculate the weighted length of the road arc, and replaces the road according to the weighted length of the road arc The length of the arc rewrites the current path length of the terminating vertex pointed to by the road arc in the vertex state table, so that different types of road arcs can be treated differently, and it can handle road selection situations such as priority to large roads, priority to fewer traffic lights, and priority to small traffic flows. The choice is flexible and can suit the driver's habits.

Description of drawings

FIG. 1 is a schematic diagram of a road centerline model used in an electronic map in the prior art.

Fig. 2 is an abstract diagram of a traffic network used in an electronic map in the prior art.

FIG. 3 is a schematic diagram of processing a shortest path from a starting point S to an end point E in the prior art.

Fig. 4 is a schematic structural diagram of an embodiment of the device for providing a road navigation route according to the present invention.

FIG. 5 is a schematic diagram of a two-line model used in the electronic map of the device for providing road navigation routes according to the present invention.

FIG. 6 is a schematic diagram of the data relationship of an intersection in the electronic map of the device for providing road navigation routes according to the present invention.

FIG. 7 is an abstract diagram expressing the traffic network in FIG. 2 in the electronic map of the device for providing road navigation routes according to the present invention.

FIG. 8 is a flow chart of preparation work for the searcher in the embodiment of FIG. 4 to calculate the shortest path.

FIG. 9 is a flowchart of the calculation of the shortest path by the searcher in the embodiment of FIG. 4 .

FIG. 10 is a schematic diagram of a path from a starting point vertex 1 to an ending point vertex 5 .

FIG. 11 is the vertex state table 1 for calculating the shortest path in FIG. 10 by the searcher in the embodiment of FIG. 4 .

FIG. 12 is the vertex state table 2 for calculating the shortest path in FIG. 10 by the searcher in the embodiment of FIG. 4 .

FIG. 13 is the vertex state table 3 for calculating the shortest path in FIG. 10 by the searcher in the embodiment of FIG. 4 .

FIG. 14 is the vertex state table 4 for calculating the shortest path in FIG. 10 by the searcher in the embodiment of FIG. 4 .

FIG. 15 is the vertex state table 5 for calculating the shortest path in FIG. 10 by the searcher in the embodiment of FIG. 4 .

FIG. 16 is the vertex state table 6 for calculating the shortest path in FIG. 10 by the searcher in the embodiment of FIG. 4 .

FIG. 17 is the vertex state table 7 for the searcher in the embodiment of FIG. 4 to calculate the shortest path in FIG. 10 .

FIG. 18 is the vertex state table 8 for the searcher in the embodiment of FIG. 4 to calculate the shortest path in FIG. 10 .

Detailed ways

1. Embodiment 1

The present invention provides the structure of an embodiment of the device of road navigation path, as shown in Figure 3, it is made up of main controller 10, transceiver 20, the data store 30 that has electronic map, searcher 40, map editor 50 and The input module 60 is composed. The main controller 10 controls the transceiver 20, the data memory 30 storing the electronic map, the searcher 40, the map editor 50 and accepts the data for modifying the electronic map provided by the input module.

Transceiver 20 adopts public GPRS network or CDMA network mobile transceiver, receives the vehicle current location and destination information provided by the vehicle terminal and forwards it to the main controller 10, or sends the navigation route data obtained by the main controller 10 to the vehicle terminal.

The abstract way of adopting the two-line road model in the electronic map stored in the data memory 30 is shown in FIG. 5 , and the two side lines of the road are used to more truly reflect the road traffic relationship. As can be seen from Figure 5, a two-lane road will generate two vertices at each road port at each crossing, and according to the direction of entering and leaving the crossing, these crossing vertices can be divided into again entering the crossing (hereinafter referred to as the crossing). Enter the vertex (solid black dot in Fig. 5, hereinafter referred to as vertex) and leave the virtual exit vertex (hollow point in Fig. 5) of this crossing. From the entry vertex of a road port at the crossing, a virtual turning road arc is drawn to the virtual exit vertices of other road ports respectively to connect the road arc with the virtual exit vertex of the road port as the starting point, and finally form the road arc starting from the entry vertex The road arc with turning relationship whose end point is the end point of the road arc where the virtual vertex is located. To describe the steering relationship at the intersection of each road at the intersection. For example, as shown in FIG. 6 , a road W and a road V intersect to form an intersection WV. From the entry vertex D1 of a road W port at the intersection WV, lead a virtual turning road arc D1-D2 to the virtual exit vertex D2 of the road V port on the right to connect the road with the virtual exit vertex D2 of the road V port as the starting point Arc D2-D3 forms a road arc D1-D3 with steering relationship; lead a virtual turning road arc D1-D4 to the virtual vertex D4 of the road W port ahead to connect the virtual vertex D4 of the road W port as the starting point The road arc D4-D5 of the road forms a road arc D1-D5 with turning relationship; leads a virtual turning road arc D1-D6 to the virtual vertex D6 of the left road V port to connect the virtual vertex D6 of the road V port The road arc D6-D7 as the starting point forms a road arc D1-D7 with steering relationship; road arc D1-D3 with steering relationship, road arc D1-D5 with steering relationship, and road arc D1-D1 with steering relationship D7 expresses the turning relationship of the entry vertex D1 of a road W port at the intersection WV. In the same way, the turning relationships of the entry vertices of the other three road ports at the intersection WV can be expressed by three road arcs with turning relationships. Since the road arc with turning relationship hides the virtual exit vertex and the virtual turning road arc, the entry vertex will be referred to as the vertex in the following description. The abstract diagram of the transportation network in the electronic map is shown in Figure 7.

In the electronic map stored in the data memory 30, there are map editing formats applicable to editing operations for the recording forms of various map elements such as roads, intersections (hereinafter referred to as crossings), vertices, and road arcs, and path search calculations applicable to search operations. Format. In the electronic map, each type of map element is uniquely numbered, and a numbered topological relationship is established among different map elements.

The map element data in the map editing format includes road records of each road and crossing records of each crossing. The data items contained in the road record of each road are: road name, road number, the number of crossings in the road, the starting crossing number, the ending crossing number, and the crossing numbers in the middle; the data items contained in the crossing record of each road crossing are: : Crossing name, crossing number, number of vertices in the crossing, start vertex number, end point vertex number, and the number of each middle vertex. The topological relationship between road elements and crossing elements in the map editing format data is reflected in the number of each crossing in the road record of each road. If two roads intersect, the number of the same crossing must appear in the road records of these two roads.

The map element data in the route search calculation format has records of vertices and road arcs. The data items contained in the record of each vertex are: vertex number, longitude, latitude, number of connected road arcs, and numbers of connected road arcs. The data items contained in each road arc record are: road arc number, start vertex number, end vertex number, passable sign, road arc length, other detailed data of the road arc, and road grade of the road arc. Among them, the passable sign is used to indicate whether the virtual turning arc connected to the road arc is passable, that is, whether turning is prohibited; the road grade of the road arc can be used to adjust the weighting coefficient of the length of the road arc during calculation.

The topological relationship between the crossing elements in the map editing format data and the vertex elements and road arc elements in the route search calculation format data is reflected by the number of each vertex in the crossing record of each crossing in the map editing format data, and a crossing record can Accurately find out the numbers of each vertex of the crossing; in the path search calculation format data, according to these vertex numbers, the road arcs connected by each vertex can be accurately found. The topological relationship between each vertex element is recorded by the two fields of start vertex number and end vertex number in the road arc record.

After being notified by the traffic management department to control or lift traffic control at a crossing. The operator uses the input module 60 to input commands to the main controller 10, and the main controller 10 starts the map editor 50 to enter the working state. The map editor 50 obtains from the input module 60 through the main controller 10 the name of the intersection or the names of the two roads where the vehicle is to be modified, and the vehicle steering restriction is obtained. Take out the numbers of each vertex in the crossing record in the map editing format data, and control the display of the input module 60 through the main controller 10 to display the figure of the crossing and prompt the number of each vertex. The operator uses the input module 60 to provide the map editor 50 with the numbering of the vertex that needs to be edited and the vehicle steering that is forbidden or unbanned in the above-mentioned notification through the main controller 10; After the vertex number of the crossing in the map editing format data is deduced from the vertex in the path search calculation format data, take out the road arc records for which the vertex of the crossing in the path search calculation format data is the starting vertex, and press prohibition or release prohibition The vehicle turns and selects the corresponding road arc record and writes the corresponding passable sign state into the road arc record in the electronic map of the data memory 30 .

After the main controller 10 receives the vehicle current position and the destination information provided by the vehicle-mounted terminal from the transceiver 20, it utilizes the electronic map in the data memory 30 to convert the vehicle's current position and the destination information into a starting vertex and a destination vertex. In the process that the controller 10 controls the searcher 40 to use the DijkStra algorithm to find the shortest path, the searcher 40 first records the number of the departure vertex and the number of the destination vertex, and then extracts all the information in the electronic map route search calculation format data of the data storage 30. Vertex records and road arc records, after which the searcher 40, as shown in FIG. 8, starts preparations for searching the shortest path.

Step 101: Create a vertex state table. Each vertex in the electronic map is used as a column in the table, and the data items in each column include: the number of this vertex; the number of the previous point of this vertex in the shortest path; the current path length from the starting vertex to this vertex; whether it is confirmed is the state of the shortest path.

And build a road arc state table. Each road arc in the electronic map is regarded as a column in the table, and the data items in each column include: the starting vertex number of this road arc; the ending vertex number of this road arc; the length of this road arc; the length of this road arc The state that was visited during the computation.

Step 102: Initialize the previous point of all vertices in the vertex state table as an invalid value and the current path length is positive infinity, and the state is that the shortest path has not been calculated; positive infinity means that no path from the starting vertex to each vertex has been calculated yet. Initialize the state of all road arcs in the road arc state table as unvisited.

Secondly, it is necessary to do special initialization work on the starting vertex in the vertex state table:

Step 103: Initialize the previous point of the starting vertex in the vertex state table as the starting vertex itself, and the current path length is 0;

Then start the cyclic process of search calculation:

Step 104: Check all vertices in the vertex state table whose status is that the shortest path has not been calculated but whose current path length is not positive and infinite, and take out the vertex with the smallest path length. According to the DijkStra algorithm, the current path of the vertex is the shortest path of the vertex, and the shortest path is determined by the previous point of the vertex. If the search fails, go to step 105; if the search is successful, go to step 106.

Step 105: Indicates that the shortest path from the departure vertex to the destination vertex cannot be obtained, then the search fails and the calculation is exited.

Step 106: Judging whether the vertex found in step 4 is the destination vertex, if it is, it means that the shortest path from the starting vertex to the destination vertex has been obtained, and the search is successful and the calculation is exited; otherwise, continue searching.

Step 107: In the vertex state table, mark the state of the vertex (assumed to be numbered r) found in step 4 as the shortest path obtained.

Step 108: Find a road arc starting from the vertex numbered r in the road arc state table and whose state is unvisited.

Step 109: If the search in step 108 is unsuccessful, it means that all road arcs connected to the vertex numbered r have been searched and processed, then go to step 4 to re-enter the loop to search and process other vertices.

Step 110: If the search is successful in step 108, a road arc (assumed to be numbered arc) is obtained, and the status of the road arc marked with the number arc is visited in the road arc state table.

Step 111: Check whether the passable identification data item numbered as arc road arc is passable, if not passable, then give up further search processing on the road arc numbered as arc, and directly go to step 109 to search for other road arcs. This step does not exist in the DijkStra prototype algorithm, and is the key to obtain the real shortest path under the condition of turning prohibition.

Step 112: Check the status of the terminal vertex whose number is pointed to by the arc road arc in the vertex status table, if the status is that the shortest path has been obtained, directly go to step 109 to process other road arcs.

Step 113: The state of the terminal vertex pointed to by the road arc numbered arc is that the shortest path has not been found, check whether the starting vertex numbered arc road arc in the vertex state table can be used as the previous point of the terminated vertex it points to: the number is arc The starting vertex of a road arc cannot be used as the previous point of the ending vertex it points to, and the following conditions should be met: (1) There is a current shortest path at the ending vertex pointed to by the road arc numbered arc, that is, the previous point is valid, and the current path length is valid; (2) The current path length of the terminating vertex pointed to by the road arc numbered arc is less than the path length when the vertex numbered r is taken as the previous point; that is, the road arc numbered arc is not on the shortest path of the terminating vertex it points to. When the above conditions are met, go directly to step 109 to process other road arcs.

Step 114: The road arc numbered arc is on the shortest path of the terminating vertex it points to, and the starting vertex of the road arc numbered arc, ie, the vertex numbered r, should be used as the previous point of the terminating vertex it points to. Change the previous point of the terminal vertex pointed to by the road arc numbered arc in the vertex state table to the vertex numbered r, and change the current path length of the terminal vertex pointed to by the road arc numbered arc to take the current vertex numbered r as the previous point This path length refers to the sum of the length of the path numbered as the r vertex and the length of the road arc numbered as arc; note that when performing calculations such as the priority of large roads, the road class numbered as arc should be based on the road level numbered as arc The length of the road arc is weighted, that is, the road grade numbered arc is used to adjust the weighting coefficient to calculate the weighted length of the road arc numbered arc, and the vertex state table is rewritten according to the weighted length of the road arc numbered arc instead of the length of the road arc numbered arc The number in the arc is the current path length of the terminal vertex pointed to by the arc road arc. The weighting coefficients of low-level roads are all greater than 1, and the weighted length of the road arc is obtained by multiplying the weighting coefficients with the length of the road arc, and the path length of the low-level roads is lengthened in a disguised form, thereby reducing the selection of such roads as the shortest in the sense of probability possible path. Finally, turn to step 109 and recycle to process other road arcs.

After the searcher 40 successfully exits the calculation, the previous point of each vertex on the shortest path to the destination vertex is saved in the vertex state table. The searcher 40 needs to trace back the previous point from the destination vertex to the starting vertex according to the vertex state table, and then arrange in reverse order to obtain the specific composition of each vertex on the shortest path.

After the searcher 40 completes the above work, it submits the obtained specific composition data of each vertex on the shortest path to form the shortest navigation path data in the form of road vertex sequence to the main controller 10 . Finally, the main controller 10 can easily obtain the position latitude and longitude value corresponding to each vertex from the electronic map according to the shortest path vertex number submitted by the searcher 40, and the steering information on the virtual turning arc where the steering occurs, according to the road path prompting module in the vehicle equipment. According to the request, the data is encapsulated into a certain format and transferred to the transceiver 20 in a serialized manner, and the transceiver 20 transmits it to the vehicle-mounted device that requires navigation information in a wireless communication manner.

In order to further illustrate how the searcher 40 uses the steering restriction feature information of each road vertex to perform a search operation during the search process, please refer to the example of searching for the shortest path from departure vertex 1 to destination vertex 5 shown in FIG. 10 .

In Figure 10, each small circle represents a vertex, and the number in the small circle represents the number of the vertex; each line segment with an arrow represents a road arc, if a line segment is drawn with a dotted line, it means that the road arc is impassable, each The value on the line segment represents the arc length of the road.

After the searcher 40 completes step 103, the specific content of the vertex state table is shown in FIG. 11 . In order to save space, the specific content of the road arc state table is not given separately. Please mark the road arc from Figure 10 to replace the road arc whenever a road arc is visited during the reading of the following instructions state table. Execute step 104, find out that there is a path (there is a previous point, and the path length is valid), but the state is the vertex with the smallest path length among the vertices that have not found the shortest path, which is obviously vertex 1 at this time, and the shortest path of vertex 1 can be Assuming that it has been calculated, execute step 6 and mark the state of vertex 1 in the vertex state table as the shortest path that has been obtained. Execute the loop from step 109 to step 114 twice, analyze the road arcs connected by vertex 1, and find vertex 2 and vertex 6 that are reachable from vertex 1. Since there is no path at the current vertex 2 and vertex 6, they can both generate paths with vertex 1 as the previous point, and then the content of the vertex state table changes as shown in Figure 12.

Returning to step 104, the vertex 6 can be found this time, and its state is marked as having obtained the shortest path. Execute the loop from step 109 to step 114 twice, analyze the road arcs connected by vertex 6, and find vertices 3 and 7 that are reachable from vertex 6. At present, neither vertex 3 nor vertex 7 has a path, so they can all use vertex 6 as the front The points generate paths respectively, and then the content of the vertex state table changes as shown in Figure 13.

Continue to return to step 104, this time vertex 2 can be found, and its state is marked as the shortest path has been obtained. Execute step 109, analyze the road arc connected by vertex 2, and find vertex 9 that is reachable from vertex 2. Since the road arc from vertex 2 to vertex 9 is impassable, a path for vertex 9 cannot be generated with vertex 2 as the previous point, and then Step 111 returns to step 109 . Analyze the road arc from vertex 2 to vertex 3, and use vertex 2 as the previous point to generate a path for vertex 3 (the path length is the current path length of vertex 2 plus the road arc length of vertex 2->vertex 3, which is 10) , the path length is less than the path length with vertex 6 as the previous point, so the current path of vertex 3 must be updated, the previous point number of vertex 3 in the vertex state table is changed to 2, and the current path length is changed to 10. Then the content of the vertex state table changes as shown in Figure 14.

Continue to return to step 104, this time vertex 7 can be found, and its status is marked as the shortest path has been obtained. Execute the loop from step 109 to step 114 twice, analyze the road arc connected by vertex 7, and find vertex 4 and vertex 8 that are reachable from vertex 7. At present, neither vertex 4 nor vertex 8 has a path, so we can use 7 as the previous point respectively Generate path. Then the content of the vertex state table changes as shown in Figure 15.

Returning to step 104, vertex 3 can be found this time, and its state is marked as having obtained the shortest path. Execute step 109, analyze the road arc connected by vertex 3, find vertex 4 reachable from vertex 3, vertex 4 currently has a path (length 20) with vertex 7 as the previous point, and the length of the path with vertex 3 as the previous point It is 10+6=16, which is shorter, so step 114 needs to change the previous point number of vertex 4 in the vertex state table to 3, and the current path length to 16. Then the content of the vertex state table changes as shown in Figure 16.

Execute step 104, this time the vertex 8 can be found, and its state is marked as having obtained the shortest path. Execute step 109, analyze the road arcs connected to vertex 8, and find vertex 5 that is reachable from vertex 8. At present, vertex 5 has no path, and a path can be generated with vertex 8 as the starting point. After step 114, the content of the vertex state table changes to graph 17.

Continue to return to step 104, this time vertex 4 can be found, and its status is marked as the shortest path has been obtained. Execute step 109, analyze the road arc connected by vertex 4, and find vertex 5 reachable from vertex 4, vertex 5 currently has a path (length 24) with vertex 8 as the previous point, and the length of the path with vertex 4 as the previous point It is 16+2=18, which is shorter, so step 114 needs to update the previous point number of vertex 5 to 4, and the current path length to 18, and then the content of the vertex state table changes to that shown in FIG. 18 .

Returning to step 104, vertex 5 can be found this time. Since vertex 5 is the destination vertex, step 6 determines that the search calculation of the shortest path from vertex 1 to vertex 5 is completed, and then go to step 107 to exit the search calculation.

The searcher 40 utilizes the content of the vertex state table shown in Figure 18 to start backtracking from the vertex 5 to obtain the vertex 5->vertex 4->vertex 3->vertex 2->vertex 1, and reverse the order to obtain the shortest The path vertex 1->vertex 2->vertex 3->vertex 4->vertex 5 is submitted to main controller 1.

Looking back at Figure 10, we can intuitively see that if vertex 2->vertex 9 is passable, the shortest path should be vertex 1->vertex 2->vertex 9->vertex 4->vertex 5, and the path length is 17. In this example, vertex 2->vertex 9 is impassable, and the shortest path obtained by the searcher 40 completely conforms to the situation in FIG. 10 .

The above are only preferred embodiments of the present invention, and do not limit the implementation scope of the present invention. Equivalent changes and modifications made according to the technical solutions of the present invention and the contents of the description shall fall within the scope of the present invention.

Claims (4)

1. the device that road navigation track is provided comprises master controller, transceiver, data-carrier store, searcher; Data-carrier store has electronic chart; The guidance path data that vehicle current location and the destination information that transceiver receives car-mounted terminal under main controller controls provide deliver master controller, obtain master controller send to car-mounted terminal; Searcher extracts the electronic map data of data-carrier store and submits master controller to by the guidance path data that vehicle current location and destination calculate the link vertex sequence form under main controller controls; It is characterized in that: comprise in the electronic chart of described data-carrier store to each intersection locate each road road port enter this road junction go into summit record and each road road port is gone into the road arc record that turns to limited features having of summit correspondence; It comprises that also load module and map repair coder; Map is repaiied coder under the control of master controller, and the restricted information that turns to of each road road port of the intersection that the reception load module provides is revised the road arc record that this intersection correspondence of electronic chart is gone into the summit in the editing data storer; Searcher utilizes each road road port to go into the limited features that turns to of summit road corresponding arc record, uses the DijkStra algorithm to obtain having the intersection and turns to short-range missile bit path data under the restrictive condition.

2. a kind of device that road navigation track is provided according to claim 1 is characterized in that: map edit formatted data and route searching computation scheme data are arranged in the electronic chart of described data-carrier store; The map edit formatted data has the road record of each bar road and the road junction record at each road junction, and the road record of every road comprises the numbering at each road junction in the number, road at road junction in road name, road number, the road; The road junction at each road junction record comprises the numbering of respectively going into the summit in the number of going into the summit in road junction title, road junction numbering, the road junction, the road junction; Route searching computation scheme data have the record of the record of respectively going into the summit and each road arc; Each record of going into the summit is incorporated into summit numbering, longitude, latitude, be the road arc number of starting point with it, be the numbering of each road arc of starting point with it; The record of each road arc comprises road arc numbering, initial vertex numbering, stops summit numbering, the sign of can passing through, road arc length degree; The process that map is repaiied intersection data of coder modification editing electronic map comprises:

A. obtain the road junction title through master controller from load module, the perhaps title in the two road at this place, road junction is taken out this road junction record the map edit formatted data from electronic chart;

B. point out each numbering of going into the summit and vehicle ' of going into the numbering on summit and needing modification to edit of this road junction to turn to restrictive condition through the main controller controls load module from the load module extraction;

C. go into the road arc record that the summit is a starting point with find a way out that of this road junction in the path search computation scheme data of that numbering of going into the summit at this road junction of map edit format data, turn to restrictive condition to select road corresponding arc record and will turn to corresponding the passed through identification-state of restrictive condition to write in this road arc record of electronic chart route searching computation scheme data with vehicle ' by vehicle '.

3. a kind of device that road navigation track is provided according to claim 2 is characterized in that: the search of described searcher has the intersection and turns under the restrictive condition processing procedure of short-range missile bit path to comprise:

Step S1: write down the set out numbering on summit and the numbering on summit, road junction, destination, all that extract in the electronic chart route searching computation scheme data are gone into summit record and road arc record, set up a summit state table and a road arc state table; In the electronic chart, each goes into the summit as the hurdle in the state table of summit, data item in this hurdle have the numbering on this summit, preceding some numbering, initial vertex to the current path length on this summit, whether calculate the state of shortest path, preceding point wherein is that summit before this summit in the shortest path; In the electronic chart, each road arc is as the hurdle in the road arc state table, and the data item in this hurdle has length, this road arc that initial vertex numbering, this road arc of this road arc stop summit numbering, this road arc accessed state in calculating;

Step S2: in the state table of initialization summit the preceding point on all summits be numbered invalid value, current path length for just infinite and state for not calculating shortest path; All road arcs of initialization road arc state table be visit;

Step S3: the preceding point on the summit of setting out in the state table of initialization summit is the summit self of setting out, and current path length is 0;

Step S4: take out the summit that does not calculate shortest path and current path length minimum in the state table of summit as yet, if the failure of this step, then searching and computing is withdrawed from the search failure; If the summit of taking out is the summit, destination, then is to search for successfully to change step S12;

Step S5: the state on the summit that markers step 4 is taken out in the state table of summit is for obtaining shortest path;

Step S6: searching one in road arc state table is the starting point and the road arc of accessed mistake not with the summit of taking out, and then returns step S4 and handles other summit in the state table of summit if can not find;

Step S7: the state of this road arc of mark is for visiting in road arc state table;

Step S8: whether the passed through identification data item of checking this road arc is to pass through, if impassability is then abandoned the further search of this road arc is handled, directly changes step S6 other road arc is handled;

Step S9: check the termination summit that this road arc points in the state table of summit, if its state for obtaining shortest path, directly changes step S6 other road arc is searched for processing;

Step S10: whether the initial vertex of checking this road arc in the state table of summit can be used as the preceding point on the termination summit that its points to, and point does not then directly change step S6 other road arc is searched for processing before not can be used as;

Step S11: the current path length that the preceding point of rewriting the termination summit that this road arc points in the state table of summit is numbered the initial vertex numbering of this road arc, termination summit that this road arc points to adds the length of this road arc for the current path length of the initial vertex of this road arc, and changes S6 over to other road arc is searched for processing;

Step S12: recall preceding point by the summit state table from the summit, destination to the initial vertex, do inverted sequence again and arrange the concrete composition that obtains each summit on the shortest path.

4. a kind of device that road navigation track is provided according to claim 3 is characterized in that: the category of roads that comprises this road arc in the described road arc record; Searcher has the intersection in search and turns among the step S11 of the processing procedure of short-range missile bit path under the restrictive condition, category of roads with this road arc is adjusted the weighting length that weighting coefficient calculates this road arc, and the length of pressing alternative this road arc of weighting length of this road arc is rewritten the current path length on the termination summit that this road arc points in the state table of summit.

Images