CN101162150B - Calculating method for searching multi-city multi-province route using framing data in networking vehicle mounted guidance apparatus - Google Patents

Abstract

The present invention is a calculation method for searching cross-city and cross-province routes using framed data in a networked vehicle navigation device. First, the map is framed and cut, and then the road navigation data of the starting point map and the end point map are loaded into the memory; Based on Dijkstra's path algorithm, starting from the starting point, the shortest path of each path point on the map is calculated divergently until reaching the end point. If the value is set, only the data of high-level roads will be loaded to participate in the calculation; if all the path points in the road data loaded in a map frame have calculated the shortest path that can be reached from the starting point, the navigation road data of the map frame will be loaded from the memory. During unloading, the present invention only loads relevant map frame data for calculation, and can dynamically load and unload data, thus reducing unnecessary memory occupation and achieving the purpose of using small-capacity memory to calculate large data.

Description

A calculation method for searching cross-city and cross-provincial routes using framing data in a networked vehicle navigation device

technical field

The invention divides the navigation data into a plurality of small units for processing, so as to solve the problem that the embedded vehicle navigation device cannot process large-scale navigation data due to insufficient memory space, and thus cannot search for a large-scale cross-city and cross-province navigation path.

Background technique

Embedded vehicle navigation devices have become more and more widely used. However, many navigation devices only provide navigation functions for a certain city or a certain region, and cannot yet provide the function of national road navigation. The reason is that China has a vast territory and road information is huge. If traditional methods are used to process all the data, it is necessary to load all the data into the memory. In this way, tens of megabytes or even hundreds of megabytes of memory may be required. For It is not feasible for memory-constrained embedded car navigation devices.

Contents of the invention

The purpose of the present invention is to provide a calculation method for searching cross-city and cross-province routes using framing data in a networked vehicle navigation device, which can divide large-scale road data into small unit data blocks, load them when needed, and unload them when they are not needed. Path calculations are accomplished by reading blocks of data from geographically connected cells on demand.

The present invention is a calculation method for searching cross-city and cross-provincial routes using framed data in a networked vehicle navigation device. First, the map is framed and cut, and the longitude of the starting point or end point is subtracted from the longitude of the left boundary of the leftmost frame of the national map. , divide the difference obtained by the width of the map frame, then you can calculate which column the point is located in the national map frame, subtract the latitude of the starting point or end point from the latitude of the upper boundary of the topmost map frame of the national map, and divide Based on the height of the map frame, it can be calculated which row the starting point or end point is located in the national map frame, so that according to the numbering rules of the map frame, the number of the map frame where the starting point and the end point are located can be obtained, thereby obtaining the address of the road navigation data area of the map frame; Then load the road navigation data of the starting point map and the end point map into the memory; use the path algorithm based on Dijkstra, start from the starting point, and calculate the shortest path of each path point on the map in a divergent manner, and when encountering the map frame boundary, turn according to the adjacency information , load the navigation road data of the corresponding adjacent map frame and continue the calculation until the end point is reached. During the calculation process, if the straight-line distance between the center point of the newly loaded map frame and the starting point or the end point exceeds the preset value, only the high level will be loaded The road data is involved in the calculation; if all the path points in the road data loaded in a certain map frame have calculated the shortest path that can be reached from the starting point, the navigation road data of the map frame will be unloaded from the memory, and the mark will be recorded to avoid Load the data calculation of this map again. After the calculation is completed, perform backtracking according to the path records in the calculation process, and finally generate a complete path.

According to the "National Basic Scale Topographic Map Framing and Numbering", the framing standard of 1:100,000 is selected, that is, every 7'30" of longitude difference and 5' of latitude difference is a frame size, and the nationwide rectangular area It is divided into 426 rows X 494 columns and numbered according to the "top-to-bottom, left-to-right" method.

The file format of the road navigation data is that an index area of map data is established at the beginning of the file, and the order of the map frames in the index area is arranged according to the order of numbers, and after the index area is the road navigation data area of each map frame.

For connecting roads between map frames, the adjacent turn information is used to record, and the main content of the adjacent turn information includes the number of the adjacent map frame and the number of the adjacent road inside the adjacent map frame.

Adopting the computing method of searching cross-city and cross-provincial routes using framed data in a networked vehicle navigation device of the present invention, the national navigation road data is framed and cut, and the road navigation data of the starting point map frame and the end point map frame are loaded into the memory; and In the process of calculation, only the road topological data of adjacent map frames encountered in the calculation is loaded, and there is no need to load the road topological data of all map frames; and in the middle area far from the starting point and the end point, only high-level roads can be loaded for further calculation. Calculation; data can be dynamically loaded and unloaded during the calculation process. In this way, the efficiency of memory usage is improved, the unnecessary occupation of memory is reduced, and the purpose of using small-capacity memory to calculate large data is achieved.

Description of drawings

Fig. 1 is a schematic diagram of national map framing and cutting among the present invention;

Fig. 2 is a schematic diagram of numbering of national map framing data in the present invention;

Fig. 3 is the storage schematic diagram of the navigation topological data that framing stores in the present invention;

Fig. 4 is a schematic diagram of the frame loading of navigation topology data during path calculation in the present invention;

Fig. 5 is a schematic diagram of hierarchical storage of navigation topology data in the map frame in the present invention;

FIG. 6 is a schematic diagram of the path calculation intermediate record used for path backtracking in the present invention—a map frame path table array.

Detailed ways

The present invention is a calculation method for searching cross-city and cross-province routes using framing data in a networked vehicle navigation device, wherein the route calculation method is still based on the classic Dijkstra single-source shortest path algorithm. The National Standard of the People's Republic of China "National Basic Scale Topographic Map Framing and Numbering—GB/T 13989-92" provides a reference basis for dividing unit data blocks for the present invention.

(1) Framing and cutting of navigation road data

Referring to the content of the national standard "National Basic Scale Topographic Map Framing and Numbering", a framing standard is selected as the size of the road data block unit. For example, choose the frame size of 1:100,000 topographic map, that is, every 7'30" of longitude difference and 5' of latitude difference is one frame size (other frame units can also be selected, but the frame unit should not be too large or If it is too small, if it is too large, the memory required for each loading is still too large, if it is too small, the number of times that the picture frame is read will be increased and the efficiency will be affected. What the present invention adopts when it is implemented is the above-mentioned frame size), like this, covering the whole country The navigable map area can be divided into 426 rows X 494 columns.

Cut the national road data according to the frame size, and regularly number the cut frames (such as numbering from top to bottom, then from left to right), and independently separate the road data in each frame Numbering, so that for the connection path between the map frames, the adjacency steering information can be used to record. The main content of the adjacency steering information is (specific content, see the description in (2) below):

①Number of adjacent drawing sheets.

②Number of adjacent roads inside the adjacent map frame.

In this way, as shown in FIG. 1 , the longitude range of the rectangular area covering the whole country is 73.375°-135.125°, and the latitude range is 18.0833333°-53.58343°. During the specific implementation of the present invention, according to "National Basic Scale Topographic Map Framing and Numbering", select the framing standard of 1: 100,000 (longitude difference 7' 30 ", latitude difference 5'), and the rectangular area nationwide is divided into There are 426 rows X 494 columns of picture frames, and they are numbered in a "top-to-bottom, left-to-right" manner, as shown in Figure 2.

Then, the road navigation data file is established. At the beginning of the file, a map data index area is established. The order of the map frames in the index area is arranged according to the order of the map frame numbers. After the index area is the road navigation data area of each map frame.

(2) Storage method and content of framing data

Although the national data is framed, the data of all map frames can be combined in a navigation topology file. In this case, in order to quickly jump to the data of each map frame for reading, each map frame is added to the header of the file Index information. The basic format of the navigation topology file is shown in Figure 3 and explained as follows:

Quick index of each map frame data, that is, the starting address of the navigation topology data of each map frame in the file.

The navigation topology detailed data in the map mainly includes: the number of roads of each level (higher level first), the weight information and steering information of all road arcs, the organization method is shown in Figure 5, and the description is as follows:

The number of roads at level 1, the number of roads at level 2, ..., the number of roads at level m;

[Road arc 1 weight, point number, point set..., number of turns, turn 1 arc ID, turn 1 turn weight, (the ID of the frame where the turn 1 arc ID is located) note, turn 2 exit Arc ID, turn 2 turn weight, ...], [road arc 2 weight, point number, point set..., turn number, turn 1 arc ID, turn 1 turn weight, Turn 2 arc ID, turn 2 turn weight, ...], ........., [road arc n weight, number of points, point set..., Number of turns, turn 1 arc ID, turn 1 turn weight, turn 2 arc ID, turn 2 turn weight...]

The arrangement order of the road arc data is arranged according to the order of the road level, that is, the high-level roads come first, the low-level roads follow, and the arrangement order of the same-level roads is random. This hierarchical organization method lays the foundation for the hierarchical loading of data when calculating across cities and provinces, which will be explained later.

Moreover, if the turning arc is a road arc in another map frame, it is represented in a special way. For example, if the road arc ID is represented by a 4-byte unsigned integer, the maximum value of the ID will not exceed 0x7fffffff in fact. That is, the highest binary bit of the ID must be 0. If the turning arc is an ID in the adjacent map frame, the highest binary bit of the ID is set to 1 to indicate that the turning arc is a road arc in the adjacent map frame. Resetting the highest binary position of the ID to 0 can restore it to the real ID, which is the ID of the adjacent road arc in the adjacent map frame.

Note: The data in brackets, such as "(the ID of the map frame where the road arc 1 turns to 1 exit arc ID)" will appear only when the road arc turned out is in the adjacent map frame, that is, in the adjacent turn information. Appear.

(3) The trade-off of data loading when cross-city and cross-provincial calculations—gradually call road data

When calculating the route between two places across cities and provinces, it is necessary to call many map data in the middle area between the starting point and the end point. If the distance between the starting point and the end point is very far, you can read it on the map frame near the starting point and the end point. Take all the data, and only need to read some high-level road data (expressways, urban expressways, urban main roads, national roads, provincial roads, etc.) When you are far away, you generally choose to drive on the main road.

As shown in Figure 4, the map frames that intersect with the circular areas near the starting point and the end point can be calculated by loading all the navigation road data, while the map frames outside the two circular areas only need to load high-level roads navigation data. During implementation, during the calculation process, if the straight-line distance between the center point of the newly loaded map frame and the start point or end point exceeds the preset value, that is, the radius of the circular area (for example, 50km), only the data of high-level roads will be loaded for participation calculate.

How to load only high-level road data, that is, the specific method of hierarchical loading and calculation, is described below.

(4) Hierarchical loading and calculation of navigation road data in the map frame

As mentioned in (2) above, in order to easily load only high-level road data during calculation, the organization of navigation road data in the map is sorted by level. information, as shown in Figure 5.

In this way, the road number information of roads of each level is first read, and then, according to the number of levels to be loaded, the total number of roads to be loaded is calculated, and the loading is stopped after the total number of road data is loaded. For example, the number of roads of each level in a map is: 50, 100, 200, 500, 800, 50, ..., now to load the road data of the first three levels, the total number of roads to be loaded is 350, after reading 350 navigation road data, the loading is completed. At this time, the loaded road ID range is 1 to 350. If the steering arc ID of a certain road exceeds this range during calculation, the steering will be executed. Information masking, so that only the loaded high-level navigation road data will be transferred to the calculation.

(5) Determination of the map frame where the start point and end point are located

Subtract the longitude of the starting point (end point) from the longitude of the left boundary of the leftmost frame of the national map, and divide the obtained difference by the width of the frame, then you can calculate which column the point is located in the national map frame, and divide the starting point or end point Subtract the latitude from the latitude of the upper boundary of the topmost map sheet of the national map, and divide the obtained difference by the height of the map sheet, then you can calculate which row the starting point or end point is located in the national map sheet, so according to the sheet number in Figure 2 According to the law, the number of the map frame where the point is located can be deduced, and then according to the storage location index of each map frame data in Figure 3, the navigation topology data of the map frame where the point is located can be loaded.

(6) Framing method for path calculation

The path calculation algorithm of the present invention is based on the classic Dijkstra algorithm.

During path calculation in the present invention, first load the road topology data of the starting map frame, and start path calculation from the starting point road; ID, then load the road topology data of the adjacent map (maybe only load part of the high-level navigation road data), and then continue the calculation with the adjacent road as the starting road, until the data of the end map is loaded and the shortest path to the end is found. . In this way, in the calculation process, only the road topology data of the adjacent maps encountered in the calculation need to be loaded, and there is no need to load the road topology data of all maps in the country.

If the shortest path has been calculated for all the route points in a map frame, the road topology data of the map frame loaded during calculation can be unloaded from the memory to save space.

When loading images that are far away from the starting point (end point), because the vehicle usually chooses a large road when it is far away from the starting point or end point, it can only load high-level roads for calculation, which saves memory. The role of space.

During the calculation process, the intermediate data of the path has been calculated and should be recorded so that the path can be traced back to form a complete path. The record of the intermediate path data can be stored in memory or temporarily stored in a temporary file. Take the data form stored in memory as an example, as shown in Figure 6.

(7) Backtracking to generate path results

In the process of calculating the path by the framing method, it is necessary to save the map frame path table array so that the path can be generated by backtracking at the end. As shown in Figure 6, each map frame has its own map frame path table, and the contents of the path table are:

①Number of roads involved in the calculation

②Path information array pointer

Initially, the number of roads is 0, and the array pointer is NULL. Once the road topology data of the map frame is loaded, the path information array of the map frame is generated and the path table content of the map frame is filled. The path table of each map frame is organized into an array structure according to the order of the map frame numbers. It is initialized before calculation, filled with content during calculation, and after calculation, the content of the path table of each map frame is cleared, and the path information array pointed to by the path table is released.

The path information array of each map frame records the previous road arc information on the path of each road arc in the map frame. The previous road arc may be on this map frame or on an adjacent map frame. When the path information array is initialized, the front arc ID of each road arc is set to -1, indicating that the path has not been calculated; during the calculation process, the front arc information of the road is filled at any time, for example, if it is determined during the calculation that arc A -> arc B , then the previous arc of arc B is arc A.

After the calculation is completed, according to the path information array, start with the road arc that reaches the end point, backtrack to generate a path. When backtracking, if the front arc of a road is in the adjacent map frame, read the path table of the adjacent map frame according to the path table pointer of the map frame where the road’s front arc is located, and then continue backtracking from its front arc; Backtracking ends when the path emanating from the origin is reached.

In a word, the core content of the present invention is: the map is cut into frames, the longitude of the starting point or the end point is subtracted from the longitude of the left border of the leftmost frame of the national map, and the obtained difference is divided by the width of the frame, then the value can be calculated. Which column is the point located in the national map? Subtract the latitude of the starting point or end point from the latitude of the upper boundary of the topmost map of the national map, and divide the obtained difference by the height of the map. Then it can be calculated that the starting point or end point is located in the national map In this way, according to the numbering rule of the map frame, the number of the map frame where the start point and the end point are located is obtained, so as to obtain the address of the road navigation data area of the map frame, and then load the road navigation data of the start point map frame and the end point map frame to the memory Middle; use the path algorithm based on Dijkstra, start from the starting point, calculate the shortest path of each path point on the map in a divergent manner, when encountering the border of the map frame, load the navigation road data of the corresponding adjacent map frame according to the adjacency index information and continue to calculate until Until the end point is reached, during the calculation process, if the straight-line distance between the center point of the newly loaded map frame and the starting point or the end point exceeds the preset value, only the data of high-level roads will be loaded to participate in the calculation; if the road data loaded in a certain map frame If all the waypoints in the map have calculated the shortest path that can be reached from the starting point, the navigation road data of the map frame is unloaded from the memory, and the mark is recorded to avoid loading the data calculation of the map frame again. After the calculation is completed, trace back according to the path records in the calculation process, and finally generate a complete path.

Claims (4)

1. use framing data to search the computing method in trans-city path transprovincially in a networking vehicle mounted guidance equipment; It is characterized in that: at first map is carried out the framing cutting; The longitude of beginning or end and the left margin longitude of national map Far Left map sheet are subtracted each other, and the difference that obtains then can be calculated which row that this point is positioned at national map sheet divided by the map sheet width; The latitude of beginning or end and the coboundary latitude of national map the top map sheet are subtracted each other; The difference that obtains then can be calculated which row that this beginning or end is positioned at national map sheet, like this according to the sheet designation rule divided by the map sheet height; Obtain the numbering of starting point and terminal point place map sheet, thereby obtain the road guide address data area of this map sheet; The road guide data that load starting point map sheet and terminal point map sheet then are in internal memory; Use is based on the routing algorithm of Dijkstra, and from the off, divergence expression calculates the shortest path of each path point on the map; Run into the map sheet border,, load the navigation road data continuation calculating of corresponding adjacent sheet according in abutting connection with direction information; Till reaching home; In calculation process, if the new map sheet central point that loads surpasses preset value apart from the air line distance of beginning or end, the data that then only load advanced road participate in calculating; If all path points have all been calculated the shortest path that can arrive from starting point in the road data that certain map sheet loads; Then the navigation road data with this map sheet unloads from internal memory; And record mark is in order to avoid load the data computation of this map sheet, after calculating is accomplished once more; Paths record according in the computation process is recalled, and generates fullpath at last.

2. use framing data to search the computing method in trans-city path transprovincially in a kind of networking vehicle mounted guidance equipment according to claim 1; It is characterized in that: according to " national primary scale topomap framing and numbering "; Select 1: 10 ten thousand framing standard; Promptly every at a distance from through differing from 7 ' 30 ", the meridional difference 5 ' be 1 framing size, nationwide rectangular area is divided into 426 _OKX 494 _RowIndividual map sheet, and number according to the mode of " from top to bottom, from left to right ".

3. use framing data to search the computing method in trans-city path transprovincially in a kind of networking vehicle mounted guidance equipment according to claim 1; It is characterized in that: the file layout of described road guide data does; Set up map sheet data directory district in the file beginning; The map sheet order of index area is arranged according to number order, promptly is the road guide data field of each map sheet behind the index area.

4. use framing data to search the computing method in trans-city path transprovincially in a kind of networking vehicle mounted guidance equipment according to claim 1; It is characterized in that: for the UNICOM's road between map sheet and the map sheet; Employing is carried out record in abutting connection with direction information, comprises adjacent sheet numbering and the numbering of Frontage road in adjacent sheet inside in abutting connection with the main contents of direction information.

Images