Method and apparatus for searching a route

What is claimed is:

1. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes and separate link data obtained by separating each road on the map into a plurality of links; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

2. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and unified link data obtained by unifying part of the separate link data; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the unified link data and/or setting right/left-turn traffic regulations to the separate node data.

3. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and virtual link data obtained by connecting nodes separated from one intersection by a virtual link; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the virtual link data and/or setting right/left-turn traffic regulations to the separate node data.

4. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersection; and

wherein said searching for the optimum route, at the time of searching for the optimum route, also judges whether it is possible to pass through to a next point from the composite intersection traffic regulation information and arrival route information to a point to be searched for, and terminating a search to the next point if it is impossible.

5. A method as claimed in claim 4, wherein the map data records link information to be recorded as the composite intersection traffic regulation information with connection numbers of the links connecting to one node.

6. A method as claimed in claim 4, wherein the map data doubly records the composite intersection traffic regulation information having the same contents in a node or link on an entering side and in a node or link on an exit side, and wherein said searching for the optimum route performs search processing from both of the two points set for a search on the map data.

7. A method as claimed in claim 4, wherein a plurality of kinds of the composite intersection traffic regulation are previously expressed in patterns and different identifiers are set thereto respectively, and the map data records the composite intersection traffic regulation information of said composite intersection traffic regulation expressed in patterns with the identifiers.

8. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes and separate link data obtained by separating each road on the map into a plurality of links; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

9. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and unified link data obtained by unifying part of the separate link data; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the unified link data and/or setting right/left-turn traffic regulations to the separate node data.

10. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and virtual link data obtained by connecting nodes separated from one intersection by a virtual link; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the virtual link data and/or setting right/left-turn traffic regulations to the separate node data.

11. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data including at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersection;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein said route searching portion, at the time of searching for the optimum route, judges whether it is possible to pass through to a next point from the composite intersection traffic regulation information and arrival route information to a point to be searched for, and terminates a search to the next point if it is impossible.

12. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

said map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes and separate link data obtained by separating each road on the map into a plurality of links; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

13. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

said map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and unified link data obtained by unifying part of the separate link data; and

said map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the unified link data and/or setting right/left-turn traffic regulations to the separate node data.

14. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

said map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and virtual link data obtained by connecting nodes separated from one intersection by a virtual link; and

said map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the virtual link data and/or setting right/left-turn traffic regulations to the separate node data.

15. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersection; and

said map data records link information to be recorded as the composite intersection traffic regulation information with connection numbers of the links connecting to one node.

16. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersection; and

said map data doubly records the composite intersection traffic regulation information having the same contents in a node or link on an entering side and in a node or link on an exit side.

17. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersections;

a plurality of kinds of the composite intersection traffic regulation are previously expressed in patterns and different identifiers being set thereto respectively; and

said map data records the composite intersection traffic regulation information of said composite intersection traffic regulation expressed in patterns with the identifiers.

18. A method for selecting an optimum route between two arbitrary points on map data, said method comprising:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data;

wherein the map data includes at least node data indicating intersections on a map as nodes rod link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by replacing the node data or the link data composing an actual road network with a more complicated virtual road network to which information of new links or nodes are added; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the link data and/or setting right/left-turn traffic regulations to the node data.

19. An apparatus for selecting an optimum route between two arbitrary points on map data, said apparatus comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in said map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by said point setting portion based on the map data stored in said map data storage portion;

wherein the map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by replacing the node data or the link data composing an actual road network with a more complicated virtual road network to which information of new links or nodes are added; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the link data and/or setting right/left-turn traffic regulations to the node data.

20. A recording medium for recording map data for use in a route search, wherein:

said map data includes at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links;

wherein the map data represents an area where composite intersection traffic regulation over a plurality of intersections exists by replacing the node data or the link data composing an actual road network with a more complicated virtual road network to which information of new links or nodes are added; and

wherein the map data further represents the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to route selecting methods and apparatus and more particularly to a method and an apparatus for selecting the most suitable route between two arbitrary points on map data.

2. Description of the Background Art

As conventionally known, a car navigation system is a system for detecting and displaying a present point of a vehicle, automatically selecting for the most suitable route to a destination, and guiding the vehicle to the destination along the most suitable route by display guidance and/or audio guidance. In the car navigation system, a practical route which the vehicle can always pass through is required to guide the vehicle along the route. Therefore, route searching methods in which regulation information such as one-way traffic regulation and no-right/left-turn regulation is reflected have been considerably studied and suggested.

Conventionally, vehicle route guiding apparatus for selecting a route compliant with the traffic regulation using the steady regulation information as in the above include the one disclosed in Japanese Patent Laying-Open No. 62-82316, for example. In this document, the following method is shown as a method for reflecting the steady regulation information.

FIG. 21 is a diagram showing the structure of the conventional vehicle route guiding apparatus. In FIG. 21, the vehicle route guiding apparatus is composed of basic information storage means 22a for storing map data in which the next reachable adjacent intersection and a required time correlation amount for each intersection are written, considering traffic direction regulation such as do-not-enter and no-right/left-turn, and route searching means 22b for searching the minimum route from a starting intersection to a destination intersection under a certain condition referring to the map data which the basic information storage means 22a stores.

The above conventional method is characterized by a method of representing a road network of the map data recorded in the basic information storage means 22a. Only roads to the reachable intersections are stored in consideration of the traffic regulation, thereby allowing a search for a route compliant with the regulation without requiring a complicated processing by the route searching method 22b.

Here, described is an example of a representation of a road network of the conventional art. FIGS. 22(a) and 22(b) show an example of a representation of the road network (no-right/left-turn regulation). FIG. 22(a) shows an example of an intersection, and its road network is represented as in FIG. 22(b) when the no-right-turn regulation exists in each entering direction of the intersection in the above intersection. That is, a node is assumed for each entering direction of the intersection, and it is assumed that links exit only in passable straight-ahead/left-turn directions.

In this way, the conventional vehicle route guiding apparatus records the map data, using the road network on which the regulation information is reflected, to select a route which reflects the steady traffic regulation by applying the ordinary route search processing.

By the way, in the above-discussed conventional art, only the intersection traffic regulation in one intersection (right/left-turn regulation, for example) is an object to be represented. However, there exist complicated traffic regulations which cannot be represented only by the traffic regulation in one intersection. FIG. 23 shows an example of traffic regulation over a plurality of intersections which cannot be described by the conventional method (hereinafter referred to as composite intersection traffic regulation). In FIG. 23, it is presumed that only A.fwdarw.B and B.rarw.A are prohibited to be passed, and all of the others can be passed. FIG. 24 shows an example of representation of the composite intersection traffic regulation in FIG. 23 using the ordinary intersection traffic regulation on a general network. FIG. 24 represents the road network in FIG. 23 with two nodes (N1 and N2) and five links (L1 to L5). When the intersection traffic regulation shown as in FIG. 24 is applied, a passable route such as L1.fwdarw.N1.fwdarw.L2.fwdarw.N2.fwdarw.L5, for example, is disadvantageously not passable.

Therefore, in order to represent the above composite intersection traffic regulation, a method for unifying a plurality of intersections into one node (unified intersection method) is disclosed in Japanese Patent Laying-Open No. 8-75491. FIG. 25 shows an example of a unified intersection. Here, a node N1 and a node N2 are unified to be a new node NX1. The ordinary traffic regulation (no-straight-ahead regulation to L4.fwdarw.L5 and L5.fwdarw.L4) is written on the node NX1, thereby allowing representation of the regulation contents in FIG. 23.

When the conventional unified intersection method is used, in addition to the ordinary search processing, it is required to refer to cost information (time and distance) for passing through the unified intersection and route information in the unified intersection at the time of route display, thereby disadvantageously resulting in a complicated processing. Furthermore, when the cost in the unified intersection becomes large, the selected route is not necessarily the minimum cost route.

Here, described is an example of cases where the selected route is not the minimum cost route when the unified intersection method is used, using drawings. FIG. 26 is a diagram showing an example of a road network in a case where the selected route is not the minimum cost route when the conventional unified intersection method is used. FIG. 27 is a diagram representing the road network in FIG. 26 with the conventional unified

intersection method. In FIG. 26, assume that the minimum cost route from a starting direction to a node N4 is L1.fwdarw.N1.fwdarw.L4.fwdarw.N3.fwdarw.L7.fwdarw.N4 and the minimum cost route to a node N5 is L1.fwdarw.N1.fwdarw.L2.fwdarw.N2.fwdarw.L5.fwdarw.N5. In this case, the minimum cost route from the starting direction to the destination direction is L1.fwdarw.N1.fwdarw.L2.fwdarw.N2.fwdarw.L5.fwdarw.N5.fwdarw.L9. However, when the nodes N4 and N5 are unified in this road network into a unified node NX1 as shown in FIG. 27, the minimum cost route from the starting direction to the unified node NX1 is L1.fwdarw.N1.fwdarw.L4.fwdarw.N3.fwdarw.L7.fwdarw.NX1. Since searches expanse further on the basis of the results, the finally obtained route from the starting direction to the destination direction is L1.fwdarw.N1.fwdarw.L4.fwdarw.N3.fwdarw.L7.fwdarw.NX1.fwdarw.L9, which is different from the correct minimum cost route as shown in FIG. 26.

SUMMARY OF THE INVENTION

Accordingly, an object of the present invention is to provide a route searching method and an apparatus capable of providing the minimum cost route compliant with the complicated regulation information over a plurality of intersections as the most suitable route.

The present invention has the following features to achieve the object discussed above.

A first aspect of the present invention is directed to a method for selecting an optimum route between two arbitrary points on map data, comprising the steps of:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data.

The map data including at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links. The map data:

representing an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes and separate link data obtained by separating each road on the map into a plurality of links; and

further representing the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

A second aspect of the present invention is directed to a method for selecting an optimum route between two arbitrary points on map data, comprising the steps of:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data.

The map data including at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links. The map data:

representing an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and unified link data obtained by unifying part of the separate link data; and

further representing the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the unified link data and/or setting right/left-turn traffic regulations to the separate node data.

A third aspect of the present invention is directed to a method for selecting an optimum route between two arbitrary points on map data, comprising the steps of:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data.

The map data including at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links. The map data:

representing an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and virtual link data obtained by connecting nodes separated from one intersection by a virtual link; and

further representing the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the virtual link data and/or setting right/left-turn traffic regulations to the separate node data.

As described above, in accordance with the first to third aspects, it is possible to represent the composite intersection traffic regulation only with the network structure of the map data and select a route compliant with the composite intersection traffic regulation without specific processing at the time of search processing.

A fourth aspect of the present invention is directed to a method for selecting an optimum route between two arbitrary points on map data, the map data including at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersections. The method comprising the steps of:

setting the two points to be searched for on the map data; and

searching for the optimum route between the set two points based on the map data.

The step of searching for the optimum route, at the time of searching for the optimum route, judging whether or not it is possible to pass through to a next point from the composite intersection traffic regulation information and arrival route information to a point to be searched for, and terminating a search to the next point if it is impossible.

As described above, in accordance with the fourth aspect, at the time of searching for the optimum route, it is judged whether or not it is possible to pass through to a next point from the composite intersection traffic regulation information and arrival route information to a point to be searched for, to terminate the search to the next point if it is impossible, thereby allowing quick selecting of a route compliant with the composite intersection traffic regulation.

According to a fifth aspect of the present invention, in the fourth aspect, the map data records link information to be recorded as the composite intersection traffic regulation information with connection numbers of the links connecting to one node.

As described above, in accordance with the fifth aspect, since the number of links connectable to one node is generally limited, it is possible to specify the links with a small number of bits and compress the data size to be recorded.

According to a sixth aspect of the present invention, in the fourth aspect, the map data doubly records the composite intersection traffic regulation information having the same contents in a node or link on an entering side and in a node or link on an exit side, and the step of searching for the optimum route performs search processing from both of the two points set for a search on the map data.

As described above, in accordance with the sixth aspect, since the composite intersection traffic regulation with the same contents are doubly written in both of the exit side node or link and the entering side node or link, it is possible to refer to the regulation contents without going back to the exit side node or link for searching for the applicable composite intersection traffic regulation even at the time of the destination side search, thereby allowing search time savings.

According to a seventh aspect of the present invention, in the fourth aspect, a plurality of kinds of the composite intersection traffic regulation are previously expressed in patterns and different identifiers are set thereto respectively, and the map data records the composite intersection traffic regulation information of the composite intersection traffic regulation expressed in patterns with the identifiers.

As described above, in accordance with the seventh aspect, as to the typical composite intersection traffic regulation with a large number of regulations, by recording not all information but only the identifiers indicating kinds of regulation patterns, it is possible to compress the size of the data to be recorded.

An eighth aspect of the present invention is directed to an apparatus for selecting an optimum route between two arbitrary points on map data, comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in the map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by the point setting portion based on the map data stored in the map data storage portion.

The map data including at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links. The map data:

representing an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes and separate link data obtained by separating each road on the map into a plurality of links; and

further representing the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

A ninth aspect of the present invention is directed to an apparatus for selecting an optimum route between two arbitrary points on map data, comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two point to be searched for on the map data stored in the map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by the point setting portion based on the map data stored in the map data storage portion.

The map data including at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links. The map data:

representing an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and unified link data obtained by unifying part of the separate link data; and

further representing the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the unified link data and/or setting right/left-turn traffic regulations to the separate node data.

A tenth aspect of the present invention is directed to an apparatus for selecting an optimum route between two arbitrary points on map data, comprising:

a map data storage portion for storing the map data;

a point setting portion for setting the two points to be searched for on the map data stored in the map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by the point setting portion based on the map data stored in the map data storage portion.

The map data including at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links. The map data:

representing an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and virtual link data obtained by connecting nodes separated from one intersection by a virtual link; and

further representing the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the virtual link data and/or setting right/left-turn traffic regulations to the separate node data.

As described above, in accordance with the eighth to tenth aspects, it is possible to represent the composite intersection traffic regulation only with the network structure of the map data and select a route compliant with the composite intersection traffic regulation without specific processing at the time of search processing.

An eleventh aspect of the present invention is directed to an apparatus for selecting an optimum route between two arbitrary points on map data, comprising:

a map data storage portion for storing at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersections;

a point setting portion for setting the two points to be searched for on the map data stored in the map data storage portion; and

a route searching portion for searching for the optimum route between the two points set by the point setting portion based on the map data stored in the map data storage portion.

The route searching portion, at the time of searching for the optimum route, judging whether or not it is possible to pass through to a next point from the composite intersection traffic regulation information and arrival route information to a point to be searched for, and terminating a search to the next point if it is impossible.

Further, according to the eleventh aspect of the present invention, by recording the passage direction to be regulated (regulated direction) and the passage condition (regulating condition) for effecting the regulation in the intersection where the regulation is finally effective with the link number or the node number string, etc., judging whether it is possible to pass through to the next point from the composite intersection traffic regulation information and the arrival route information to the point to be searched at the time of the search processing, and not extending the search if impassable, it is possible to select the most suitable route compliant with the composite intersection traffic regulation with a relatively simple data map structure.

As described above, in accordance with the eleventh aspect, at the time of searching for the optimum route, it is judged whether or not it is possible to pass through to a next point from the composite intersection traffic regulation information and arrival route information to a point to be searched for, to terminate the search to the next point if it is impossible, allowing quick selection of a route compliant with the composite intersection traffic regulation.

A twelfth aspect of the present invention is directed to a recording medium for recording map data for use in a route search. The map data including at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links. The map data:

representing an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes and separate link data obtained by separating each road on the map into a plurality of links; and

further representing the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and/or setting right/left-turn traffic regulations to the separate node data.

A thirteenth aspect of the present invention is directed to a recording medium for recording map data for use in a route search. The map data including at least node data indicating intersections on a map as nodes

and link data indicating roads on the map as links. The map data:

representing an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and unified link data obtained by unifying part of the separate link data; and

further representing the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the unified link data and/or setting right/left-turn traffic regulations to the separate node data.

A fourteenth aspect of the present invention is directed to a recording medium for recording map data for use in a route search. The map data including at least node data indicating intersections on a map as nodes and link data indicating roads on the map as links. The map data:

representing an area where composite intersection traffic regulation over a plurality of intersections exists by a road network composed of separate node data obtained by separating each intersection on the map into a plurality of nodes, separate link data obtained by separating each road on the map into a plurality of links, and virtual link data obtained by connecting nodes separated from one intersection by a virtual link; and

further representing the composite intersection traffic regulation by setting one-way traffic regulations to the separate link data and the virtual link data and/or setting right/left-turn traffic regulations to the separate node data.

As described above, in accordance with the twelfth to fourteenth aspects, it is possible to represent the composite intersection traffic regulation only with the network structure of the map data and select a route compliant with the composite intersection traffic regulation without specific processing at the time of search processing.

A fifteenth aspect of the present invention is directed to a recording medium for recording map data for use in a route search. The map data including at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersections; and

the map data recording link information to be recorded as the composite intersection traffic regulation information with connection numbers of the links connecting to one node.

As described above, in accordance with the fifteenth aspect, since the number of links connectable to one node is generally limited, it is possible to specify the links with a small number of bits and compress the data size to be recorded.

A sixteenth aspect of the present invention is directed to a recording medium for recording map data for use in a route search.

The map data including at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersections; and

the map data doubly recording the composite intersection traffic regulation information having the same contents in a node or link on an entering side and in a node or link on an exit side.

As described above, in accordance with the sixteenth aspect, since the composite intersection traffic regulation with the same contents are doubly written in both of the exit side node or link and the entering side node or link, it is possible to refer to the regulation contents without going back to the exit side node or link for searching for the applicable composite intersection traffic regulation even at the time of the destination side search, allowing search time savings.

A seventeenth aspect of the present invention is directed to a recording medium for recording map data for use in a route search. The map data including at least node data indicating intersections on a map as nodes, link data indicating roads on the map as links, and composite intersection traffic regulation information indicating composite intersection traffic regulation over a plurality of intersections;

a plurality of kinds of the composite intersection traffic regulation being previously expressed in patterns and different identifiers being set thereto; and

the map data recording the composite intersection traffic regulation information of the composite intersection traffic regulation expressed in patterns with the identifiers.

As described above, in accordance with the seventeenth aspect, as to the typical composite intersection traffic regulation with a large number of regulations, by recording not all information but only the identifiers indicating kinds of regulation patterns, it is possible to compress the size of the data to be recorded.

These and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram showing the structure of a car navigation system according to an embodiment of the present invention;

FIG. 2 is a diagram showing an example of structure of map data recorded in a recording device in FIG. 1;

FIG. 3 is a functional block diagram showing an example of structure of the navigation device shown in FIG. 1;

FIG. 4 is a functional block diagram showing a first example of structure of a route selecting portion shown in FIG. 3;

FIG. 5 is a flow chart showing the operation of a point setting portion shown in FIG. 4;

FIG. 6 is a flow chart showing the route search processing of a route searching portion shown in FIG. 4;

FIG. 7 is a flow chart showing the route structuring processing executed by the route searching portion in FIG. 4;

FIG. 8 is a diagram showing a first example of network structure representing composite intersection traffic regulation shown in FIG. 23;

FIG. 9 is a diagram showing a second exa