JP3390342B2 - Route search device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route search device which sets a starting point and a destination point, obtains a route between them, and displays them on a screen.

[0002]

2. Description of the Related Art In a route search apparatus, a starting point, a destination, and a transit point are set as set points prior to the route search. When the set point is set, the road link closest to the set point is selected, and the route between the selected road links is calculated. The route obtained as a result of the calculation is displayed on the display device in an overlapping manner with the map.

Here, the road data used for the route search is
CD-for each map mesh divided into multiple rectangles
It is stored in a storage medium such as a ROM. When selecting the road link closest to the set point, the conventional route search device selects the road link closest to the set point in the map mesh including the set point for simplicity.

[0004]

However, the road link actually closest to the set point does not always exist in the map mesh including the set point. That is, a road link in another map mesh (surrounding map mesh) around the map mesh may be closer to the set point than a road link in the map mesh including the set point. In this case, selecting a road link in the surrounding map mesh is more likely to be an appropriate route. However, in the conventional route search device, since the road link is selected only within the map mesh including the set point, there is a case where an appropriate route is not selected.

It is an object of the present invention to provide a route search device that can reliably obtain a road link closest to a set point in a route search device that performs a route search using a map mesh divided into a plurality of parts. To do.

[0006]

The present invention has been made to achieve the above object. The present invention provides a starting point,
It has a point setting means for setting a destination as a set point, an extracting means for extracting a road link from a map mesh including the set point, and a route calculating means for calculating a route between the road links extracted by the extracting means. In the route search device, the extraction unit extracts the road link from the map mesh including the set point, and as a result, determines whether or not the surrounding map mesh around the map mesh satisfies a specific condition. Provide means. When the determining means determines that the specific condition is satisfied, the extracting means also extracts the road links of the peripheral map mesh existing around the map mesh including the set point.

There are various specific conditions. As one of them, there is a possibility that the road link is not extracted from the map mesh including the set point and there is a road link close to the surrounding map mesh. In this case, in the conventional route search device, the search is terminated because there is no road link near the set point, but according to the present invention, the extraction means targets the road link of the surrounding map mesh for extraction. , Can find a reasonable route.

As described above, when the road link is not extracted from the map mesh including the set point, it is desirable to search the road link of the surrounding map mesh.
If the distance between the set point and the road link is too large, the validity of the searched route cannot be guaranteed. Therefore, when searching the surrounding map mesh forms a road link extracted region of finite size around the set point, extracts a surrounding map mesh part also least the road link extracted regions overlap Can be targeted. As a result, road links at a distance equal to or greater than the predetermined value will not be selected. In addition, the time required for the road link extraction processing is shortened.

Another specific condition is that the distance between the set point and the surrounding map mesh is shorter than the distance between the road link extracted from the map mesh including the set point and the set point. There may be a map mesh. By searching for a road link in the surrounding map mesh with this as a specific condition, even if the road link can be extracted in the map mesh including the set point, the road link in the surrounding map mesh is closer to the set point. In this case, it becomes possible to extract a closer road link.

Further, the extraction means, when there are a plurality of relevant peripheral map meshes when extracting the road links of the peripheral map mesh, the peripheral map mesh having a short distance between the set point and the peripheral map mesh is selected. Road link extraction processing is performed with priority. As a result, the time for searching for the road link closest to the set point is shortened, and the processing can be performed efficiently.

By the way, in the map mesh, road links are represented by coordinates, and these coordinates are a coordinate system closed for each map mesh. When calculating the distance between the set point and the road link in the surrounding map mesh, the distance cannot be calculated between map meshes having different coordinate systems. Therefore, in the present invention, the coordinate system of each map mesh is set to a common coordinate. By using a system, the distance can be calculated correctly.

Specifically, when extracting the road links of the peripheral map mesh, the extracting means sets the coordinates of the road links of the peripheral map mesh to relative coordinates with reference to the coordinate system of the map mesh including the set points. Convert or convert the coordinate system of the set point into relative coordinates based on the coordinate system of the peripheral map mesh. The present invention, as described above,
If there is a surrounding map mesh that meets certain conditions,
The extraction means sets a peripheral map mesh that satisfies a specific condition as an extraction target, and ends the road link extraction processing when there is no peripheral map mesh that satisfies the specific condition. This makes it possible to efficiently extract road links.

When the road link extraction processing is performed on the peripheral map mesh satisfying a specific condition, the map mesh is read from the storage medium each time. On this occasion,
To read the address of the map mesh required for each reading from the storage medium, it is necessary to read through the data management unit and the like, and therefore the data reading process becomes unnecessarily large. In the present invention, when the map mesh including the set point is read, the address of the peripheral map mesh stored as additional information in the data is read at the same time and stored in the map mesh address storage means.

As a result, when the peripheral map mesh is read, the storage medium can be directly accessed based on the address stored in the map mesh address storage means, and the peripheral map mesh can be efficiently read.

[0015]

DESCRIPTION OF THE PREFERRED EMBODIMENTS A route guidance device to which the present invention is applied will be described with reference to the drawings. The route guidance device of this example is installed in an automobile and guides the route to the user. FIG. 1 is a diagram showing a circuit configuration of a route search device. The control unit 11 includes a CPU 12, a ROM 13, and a RAM 14. An input device 16 for a user to set a starting point, a passing point, and a destination point is connected to the data bus 15 of the control unit 11.

A CD-ROM 17 storing map data is loaded into a CD-ROM driver 18. CD-ROM
The driver 18 is connected to the data bus 15 via the CD-ROM decoder 19. A direction sensor 21, an angular velocity sensor 22, a distance sensor 23, and a GPS 24 are connected to the data bus 15 via an interface 25 in order to detect the current position of the vehicle.

The graphic memory 26 is connected to the data bus 15 via the graphic controller 27. The display device 28 is connected to the data bus 15 via the display controller 29. The control unit 11 operates according to a program stored in the ROM 13. In the route search, the starting point, the passing point, input from the input device 16,
The destination point etc. is input as the set point. Control unit 11
Reads the map mesh from the CD-ROM 17, extracts the road link closest to the set point, and calculates the distance between the road links. The calculated route is displayed on the screen of the display device 28 so as to overlap with the map. This map is CD-
It is created based on the map data read from the ROM 17 and the graphic data stored in the graphic memory 26.

The map mesh will be described with reference to FIG. In the following example, the setting point will be described as the starting point. As shown in FIG. 2, the map data (road data) stored in the CD-ROM 17 is divided into rectangular map meshes 31, 32, ... 39 and stored for each map mesh. Now, the map mesh 31 includes road links 51, 52, 53, and nodes 61, 6
2, 63, 64 are included, and the map mesh 36 includes a road link 54 and nodes 65, 66.

If the starting point 41 is set in the map mesh 31, the starting point 4 is set in the map mesh 31.
53 is selected as the road link closest to 1. However, in reality, the road link 54 in the map mesh 36 on the right side is the road link closest to the set point 41. In addition, in this specification, a map mesh around the map mesh 31 including the set point is referred to as a peripheral map mesh. Further, the peripheral map mesh is not always adjacent to the map mesh 31.

In the situation shown in FIG. 2, as the route search,
It is preferable to select the road link 54 of the peripheral map mesh 36. Therefore, in the present invention, the condition that a road link having a peripheral map mesh may be closer to the set point is defined as a “specific condition”, and a road link having a peripheral map mesh that satisfies this specific condition is also included. Target for extraction.

A specific example of the specific condition will be described below with reference to the drawings. FIG. 3 is a diagram illustrating a first example of the specific condition. The first example is a map mesh 31 including a starting point 41.
This is the case when there is no road link inside. In this case, it is highly possible that there is a road link closest to the departure point 41 in the surrounding map meshes 32 to 39. Therefore, in this example, the specific condition is that there is no road link in the map mesh including the set point. In the illustrated example, the surrounding map meshes 32 to 39 are set as road link extraction targets.
As a result, the road link 54 in the surrounding map mesh 39
Is selected.

FIG. 4 is a diagram for explaining a second example of the specific condition. When there is no road link in the map mesh 31 including the starting point 41 as in the example of FIG. 3, it is often preferable to search for a road link in the surrounding map mesh. However, in the example shown in FIG. 4, the distance between the departure point 41 and the road link 54 of the surrounding map mesh 36 becomes too large. Therefore, in the example of FIG. 4, even if the road link 54 is selected, the validity as the search route cannot be guaranteed.

On the other hand, in this example, a road link extraction area 42 of a finite size is provided with the starting point 41 as the center, and when there is a possibility that a road link is included in this road link extraction area 42. Only the surrounding map mesh is the extraction target. That is, when the road link is not extracted in the map mesh 31 including the starting point 41 and there is a peripheral map mesh that partially overlaps the road link extraction area 42, the corresponding peripheral map mesh is specified as a specific condition. Target for extraction.

In the example of FIG. 4, with the starting point 41 as the center,
A road link extraction area 42 having a size in a range where validity can be expected for the search route is set. Peripheral map meshes 33 and 38 partially overlap the area 42, and the peripheral map mesh 39 does not overlap. Therefore, the peripheral map meshes 33 and 38 are the targets of road link extraction. On the other hand, since the peripheral map mesh 39 is not the extraction target,
Road links 54 that are less relevant are not selected.

FIG. 5 is a diagram for explaining a third example of the specific condition. The third example is a case where the road link 53 having the shortest distance L in the map mesh 31 including the starting point 41 can be extracted. Even if the road link 53 can be selected in this way, there is a possibility that a short road link having a distance shorter than the distance L exists in the peripheral map meshes 32 to 39. In the example of FIG. 5, the road link 54 in the surrounding map mesh 36
Is that.

Here, the distance from the starting point 41 to each of the peripheral map meshes 32 to 39 is represented by L2 to 9. Of these, the distances L3, L4, L6, L8, and L9 are shorter than the distance L between the starting point 41 and the road link 53. Therefore, since there is a possibility that a road link exists in the peripheral map meshes 33, 34, 36, 38, 39 at a distance shorter than the distance L, these peripheral map meshes are used as peripheral map meshes satisfying a specific condition. It becomes the extraction target.

Further, in the example of FIG. 5, there are a plurality of peripheral map meshes to be extracted. in this case,
The extraction process is preferentially performed from the peripheral map mesh (the peripheral map mesh 36 of the distance L6 in the example of FIG. 5) having the shortest distance among the corresponding peripheral map meshes. By doing so, when a road link with a short distance Ln is found, the peripheral map meshes located at a distance shorter than the distance Ln are gradually limited. Therefore, there is a high possibility that a desired road link will be found before the extraction processing is performed for all the peripheral map meshes, and the processing can be completed in a short time.

The overall flow of the processing from setting the set point to extracting the road link will be described with reference to the flowchart of FIG. First, the overall flow is briefly explained. The operator inputs the starting point 41 from the input device 16 (step S11). The control unit 11 reads the map mesh 31 including the set starting point 41 from the CD-ROM 17, which is a storage medium that stores map data (step S1).
2).

In the read map mesh 31, a process for extracting the road link closest to the set point is performed (step S13). It is determined whether or not the extraction result satisfies the specific condition (step S14), and then it is determined whether or not there is a surrounding map mesh satisfying the specific condition (step S15). Here, when there is no surrounding map mesh satisfying a specific condition, that is, the road link 53 is extracted in the map mesh 31 including the departure point 41, and the distance L between the departure point 41 and the road link 53 is L.
If there is no surrounding map mesh within a shorter distance, it is considered that the optimum road link is extracted here, and the process ends.

On the other hand, if there is a peripheral map mesh satisfying a specific condition in step S15, the flow advances to step S16 to read the corresponding peripheral map mesh from the CD-ROM 17. Then, the road link is extracted from the read peripheral map mesh (step S17). Road links are extracted here, and the road links and starting points 4
If the distance to 1 is shorter than the distance to the already extracted road link, the road link is updated to a new road link.

Thereafter, the process returns to step S14, and it is determined whether or not the extraction result satisfies the specific condition, and then it is determined whether or not there is a peripheral map mesh satisfying the specific condition (step S15). . Here, if there is no next peripheral map mesh that satisfies the specific condition, this process is terminated, and if there are still peripheral map meshes that satisfy the specific condition, the processes from step S16 are executed.

When the extraction of the road links of the peripheral map mesh is completed by the above processing, the starting point 4 is the maximum at that point.
Road links that are said to be close to 1 are adopted. next,
Details of the processing in FIG. 6 will be described. FIG. 7 shows details of the map mesh reading process in steps S12 and S16 of the process of FIG.

In step S121, it is determined whether the address of the map mesh is stored in the map mesh address storage section provided in the RAM 14. In step S12 of FIG. 6, since the map mesh is read for the first time, the result here is No, and step S12
At 122, an address is obtained from the data management section of the CD-ROM 17, and the map mesh 31 is read according to the address.

Usually, the map mesh stores address information of the peripheral map mesh as additional information. Therefore, at the time of reading in step S122, the address information of the peripheral map mesh is also read, and
At 124, this is stored in the map mesh address storage unit. Here, the address information stored in the map mesh address storage unit includes the address to the map mesh on the CD-ROM 17, the size of the map mesh, and the distance from the starting point 41 to the map mesh. Further, instead of the distance from the starting point 41 to the map mesh, even if the absolute coordinates (latitude, longitude) of the map mesh are stored, the distance can be calculated correctly, which is acceptable.

Next, in the case of reading the peripheral map mesh in step S16 of FIG. 6, the address is often stored in the map mesh address storage unit. Therefore, if the address of the peripheral map mesh to be read is stored here, the process proceeds from step S121 to step S123. In step S123, the peripheral map mesh is directly read from the CD-ROM 17 by the address stored in the map mesh address storage unit. Therefore, the time taken to read the map mesh is shortened, and extraction can be performed efficiently. Even if the peripheral map mesh is read, if the address is not stored in the map mesh address storage unit in step S121, the process proceeds to step S121.

FIG. 8 shows details of the road link extraction processing of step S13 of FIG. 6, that is, the road link extraction processing of the map mesh including the starting point 41. Step S131
Then, it is determined whether or not the road links have been searched for all the roads in the map mesh. If it has not been completed, in step S132, an unsearched road link is searched.
For this road link search process, the process used in the conventional route search device can be directly adopted, and therefore the description thereof is omitted here.

In step S133, it is determined whether or not the searched road link is closer to the road link that has been searched so far and is said to be closest to the departure point 41 at the present time. Here, if the road link searched this time is closer, the closest road link is updated in step S134, and the process returns to step S131. If No in step S133, the process directly returns to step S131.

When the search is completed for all the road links in the map mesh, the processing of FIG. 8 is completed. here,
The processing of steps S14 and S15 of FIG. 6 will be described. In step S14, it is determined whether or not the specific condition is satisfied by the method described with reference to FIGS. When the specific condition is satisfied, it is determined in step S15 whether or not there is a surrounding map mesh that satisfies the specific condition. Here, if there is a peripheral map mesh satisfying a specific condition, the process proceeds to step S16.

In this step S15, it may be determined that there are a plurality of peripheral map meshes satisfying a specific condition. In this case, the surrounding map mesh with the smallest distance from the starting point 41 is preferentially selected, and the road links after step S16 are extracted. In the example of FIG. 5 described above, the surrounding map mesh satisfying the specific condition is 33,3.
Since these are 4, 36, 38 and 39, these peripheral map meshes are to be extracted. In addition, here, the starting point 41
The road link of the surrounding map mesh 36 located at the distance L6 closest to is the first extraction target. As a result, the road link 54 is extracted as the closest road link. Figure 9
The state where the road link 54 is extracted is shown.

In FIG. 9, starting point 41 and road link 5
The distance from 4 is L '. Distance L shorter than this distance L '
The peripheral map meshes 38 and 39 located at 8 and L9 are left as extraction targets, but the peripheral map meshes 33 and 34 located at longer distances L3 and L4 are excluded from extraction targets. In this way, as the extraction process proceeds, the number of surrounding map meshes to be extracted decreases. Then, when there are no more surrounding map meshes to be extracted, the processing ends at that point. As described above, when there are a plurality of peripheral map meshes to be extracted, the efficiency can be improved by preferentially performing the road link extraction process from the peripheral map mesh having a smaller distance from the starting point 41.

FIG. 10 is a flow chart for explaining the details of the road link extraction processing of the peripheral map mesh in step S17 in FIG. Since the flow chart of FIG. 10 is almost the same as the flow chart of FIG. 8 described above, steps having the same functions as steps in FIG. 8 are assigned the same step numbers as in FIG. As is apparent from this, in FIG. 10, step S131 and step S131 are performed.
Since only step S171 is inserted between 132, only the coordinate conversion of step S171 will be described here.

Road links are each map mesh 31-39.
If is displayed in absolute coordinates such as latitude and longitude, the distance between each map mesh can be easily calculated. However, the road link is often a coordinate system closed for each map mesh 31 to 39. In this case, from the starting point 41 in the map mesh 31 to the surrounding map meshes 32 to 3
When calculating the distance to the road link within 9, it is necessary to convert to a common coordinate system in step S17.

FIG. 11 shows an example thereof, and (A) shows a state before the coordinate system is converted. The map mesh of the starting point 41 has four coordinates (0,0) (X, 0) (0, Y).
It is represented by (X, Y). The surrounding map mesh 36 is also represented by the same coordinates (0,0) (0, Y) ...
4 is represented by two coordinates (X1,0) (X2, Y2).

When converting to the common coordinate system, in the example of FIG. 11, the coordinates of the peripheral map mesh 36 are changed to the map mesh 3
It is converted to the coordinate system of 1. As shown in FIG. 11 (B),
In the peripheral map mesh 36, the two coordinates on the left side are (X,
0) (X, Y), and the road link coordinates are (X + X)
1,0) (X + X2, Y). In this way, by converting to the common coordinate system, it becomes possible to directly calculate the distance from the starting point 41 to the road link 54.

FIG. 12 shows a modification of the example of FIG. FIG. 12A shows the state before conversion, which is the same as FIG. 11A. (B) is a map mesh 3 including the starting point 41
The coordinate system of 1 is converted into the coordinate system of the peripheral map mesh 36, and the coordinates of the starting point 41 are (X1-X, Y1). This allows the distance from the starting point 41 to the road link 54 to be calculated directly, as in the example of FIG.

[0046]

According to the present invention, in a route search device for performing route search using a map mesh divided into a plurality of parts, not only a map mesh including a set point but also a surrounding map mesh as a road link extraction target. Therefore, a proper route can be obtained.

[Brief description of drawings]

FIG. 1 is a diagram showing a circuit configuration of a route search device to which the present invention is applied.

FIG. 2 is a diagram illustrating a map mesh.

FIG. 3 is a diagram (part 1) explaining specific conditions in the embodiment of the present invention.

FIG. 4 is a diagram (part 2) explaining specific conditions in the embodiment of the present invention.

FIG. 5 is a diagram (part 3) explaining specific conditions in the embodiment of the present invention.

FIG. 6 is a flowchart illustrating an overall flow of road link extraction processing according to the embodiment of the present invention.

7 is a flowchart showing details of a map mesh reading process in FIG.

FIG. 8 is a flowchart showing details of road link extraction processing in FIG.

9 is a diagram showing a method of determining a specific condition in FIG.

10 is a flowchart showing details of road link extraction processing of the peripheral map mesh in FIG.

11 is a diagram illustrating coordinate conversion in FIG.

FIG. 12 is a diagram showing a modification of FIG. 11.

[Explanation of symbols]

11 ... Control unit 12 ... CPU 13 ... ROM 14 ... RAM 15 ... Data bus 16 ... Input device 17 ... CD-ROM 18 ... CD-ROM driver 19 ... CD-ROM decoder 21 ... Direction sensor 22 ... Angular velocity sensor 23 ... Distance sensor 24 ... GPS 25 ... Interface 26 ... Graphic memory 27 ... Graphic controller 28 ... Display device 29 ... Display controller 31 ... Map mesh including the starting point 32-39 ... Surrounding map mesh 41 ... Starting point 42 ... Road link extraction area 51-54 ... Road links 61-65 ... nodes

─────────────────────────────────────────────────── ─── Continuation of front page (58) Fields surveyed (Int.Cl. ⁷ , DB name) G01C 21/00 G08G 1/0969

Claims (5)

(57) [Claims] 1. A point setting means for setting a starting point and a destination as setting points, an extracting means for extracting a road link from a map mesh including the setting point, and a route between the road links extracted by the extracting means. In a route search device having a route calculation means for calculating a road link, the extraction means extracts a road link from a map mesh including the set point, and as a result, a distance between the extracted road link and the set point is A determination means for determining whether or not there is a surrounding map mesh that satisfies the condition that the distance between the set point and the surrounding map mesh is shorter; When it is determined that a map mesh exists, the route search device is characterized in that the road link of the corresponding surrounding map mesh is extracted. 2. Set the starting point and destination as set points
Point setting means and a map mesh that includes the set point.
Means for extracting road links from the
Route calculation to calculate the route between road links extracted by
And a map message including the set point by the extracting means.
Extract road links from the map, and
The surrounding map mesh around the shoe meets certain conditions.
A determination means for determining whether or not to add is provided, and the extraction means is such that the determination means satisfies the condition.
When it is determined that the road map of the corresponding surrounding map mesh
Link is extracted, and the map message that holds the address information to the map mesh is
An address storage means is provided, and the set point is included.
When reading the map mesh from the storage medium,
Of the surrounding map mesh included in the additional information
Store dress information in the map mesh address storage means
A route search device characterized by: 3. The extracting means extracts the data from the storage medium.
When reading the edge map mesh, the surrounding map mesh
Address information is stored in the map mesh address storage means.
If it is stored in
The process according to claim 2, wherein the map mesh is read from the storage medium.
Road search device. 4. A map mesh as the address information
Address on the storage medium, size, and
Claim that the distance from the fixed point to the map mesh is stored
2. The route search device described in 2. 5. A map mesh as the address information
Address on the storage medium, size, and map
The route search according to claim 2, wherein the absolute coordinates of the shoe are stored.
apparatus.