Apparatus for road path searching applicable to car navigation system and operation method thereof

• US 5,036,471 A
• Filed: 04/16/1990
• Issued: 07/30/1991
• Est. Priority Date: 04/18/1989
• Status: Expired due to Term

• Current Assignee: Sanyo Electric Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Sanyo Electric Company Limited (Panasonic Holdings Corporation)
• Inventors: Kondo, Kazuhiko, Noro, Satoshi, Tamura, Yutaka, Hosokawa, Yoshio
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US07/509,991
• Time in Patent Office: 470 Days
• Field of Search: 340/990, 340/995, 364/443, 364/449, 73/178 R
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06F 30/15 Vehicle, aircraft or watercraft design
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

A road path searching apparatus applicable to a car navigation system is disclosed. Road map data with different level of detail for defining a predetermined area is stored previously in a memory device. First, nodes Nai and Nbj adjacent to each of the search nodes Pa and PB are detected based on map data having a high level of detail. When nodes Nai and Nbj exist on a map of a lower level of detail, a map of one lower level of detail is selected as a map to be used in the searching process. Accordingly, as following searching process is performed based on the map data of lower level of detail, required processing time is reduced.

Claims

1. In a navigation system for processing stored electrical data representative of pre-defined locations within a given geographic area, apparatus for searching through said data to find a path between first and second geographic points situated within said area and for displaying the path comprising:

storage means (2) for storing electrical data which repeatedly defines a map of the area but at first and second different display levels, the data for the first and second display levels defining node locations that collectively represent roads situated in the area that are to be depicted at said each display level such that the first and second display levels collectively represent said map at first and second pre-defined levels of detail with the first level having more detail than said second level, the data being organized into respective first and second data groups for, respectively, the first and second display levels such that the data group for the first level includes the data group for the second level,

processing means (1, 3, 5, 6, 7,

     8), operative in conjunction with the storage means, for determining the path between said first and second points comprising;

designating means (11), responsive to said first and second geographic points, for designating first and second positions on the first level of the map and corresponding to the first and second geographic points,

adjacent node detecting means (13), responsive to the first and second positions, for detecting a plurality of each of first and second node locations in the first level and respectively adjacent to said first and second positions so as to yield corresponding first and second pluralities of adjacent node positions,

existence detecting means (14,

     18), operative in response to said adjacent node detecting means, for detecting whether said second level contains at least one of each of the pluralities of said first and second adjacent node positions and for providing a result indicative thereof,

determining means (20, 21,

     22), responsive to said adjacent node detecting means and to the result provided by said existence detecting means, for selecting one of each of the pluralities of said first and second adjacent node positions as the first and second positions such that if the pluralities of the first and second adjacent node positions contain node locations existing in said second level then the first and second positions are taken, in a pre-defined manner, to be respective ones of said node locations existing in the second level in preference to node locations existing at the first level in the pluralities of said first and second adjacent node positions; and

changing means (19), operative in response to the result provided by said existence detecting means, for subsequently changing the level of the map used by said adjacent node detecting means from the first to the second level in the event said first and second positions exist in said second level,

decision means (17), responsive to said first and second positions, for invoking said adjacent node detecting means to detect next successive pluralities of said first and second node locations until the first and second positions satisfy a pre-determined criteria, and

display means (4), responsive to said processing means, for displaying paths between successive ones of said first positions and between successive ones of said second positions so as to depict the path between said first and second geographic points.

2. A path searching apparatus according to claim 1, wherein said determining means comprises:

selecting means (21) for respectively selecting first and second corresponding ones of adjacent node positions from the pluralities of the first and second adjacent node positions as respective new values of the first and second positions, wherein said first and second corresponding ones of the adjacent node positions respectively represent geographic points that are nearest to geographic points represented by immediately prior ones of said first and second positions.

3. A path searching apparatus according to claim 1, wherein said existence detecting means comprises:

means (14) for detecting whether said first plurality of adjacent node locations contains node location existing in said second data group; and

means (18) for detecting whether said second plurality or adjacent node locations contains node locations existing in said second data group.

4. A path searching apparatus according to claim 1,

wherein said path to be searched comprises a road path on which an automobile can travel, and

said respective first and second geographic points comprise a starting point and a destination, respectively.

5. In a navigation system for processing stored electrical data representative of pre-defined locations within a given geographic area, apparatus for searching through said data to find a path between first and second geographic points situated within said area and for displaying the path comprising:

storage means (2) for storing electrical data which repeatedly defines a map of the area but at first and second different display levels, the data for the first and second display levels defining node locations that collectively represent roads situated in the area that are to be depicted at said each display level such that the first and second display levels collectively represent said map at first and second pre-defined levels of detail with the first level having more detail than said second level, the data being organized into respective first and second data groups for, respectively, the first and second display levels such that the data group for the first level includes the data group for the second level,

processing means (1, 3, 5, 6, 7,

     8), operative in conjunction with the storage means, for determining the path between said first and second points comprising;

designating means (31), responsive to said first and second geographic points, for designating first and second positions on the first level of the map and corresponding to the first and second geographic points,

distance determining means (32) for determining a geographic distance between geographic points represented by said first and second positions on the first level of the map,

selecting means (34, 36, 37,

     38), responsive to a value of the distance, for selecting said first or second data groups corresponding to said first or second display levels as a selected data group in which to search for said path, and

searching means (40, 41, 42,

     43) for searching through said selected data group so as to locate successive ones of said node locations therein as successive ones of first and second positions in order to define a path therebetween, and

display means (4), responsive to said processing means, for displaying paths between successive ones of said first positions and between successive ones of said second positions so as to depict the path between said first and second geographic points.

6. A path searching apparatus according to claim 5 wherein said searching means comprises:

neighboring node detecting means (40) for detecting, in the event said second data group is selected, first and second node locations which are geographically situated closest to said first and second positions, respectively,

means (41) for defining, based on nodes locations in said first data group, respective paths between said first position and said first node location and between said second position and said second node location, and

means (42) for defining, based on node locations in said second data group, a path between said first and second node locations.

7. A path searching apparatus according to claim 5 wherein said selecting means comprises:

comparing means (33,

     35) for comparing a predetermined distance based on a diagonal line of a display screen with the distance detected by said distance detecting means so as to determine whether said predetermined distance is greater than or equal to said detected distance and to provide a result indicative thereof, and

means (34, 35,

     37), responsive to the result provided by said comparing means, for selecting said first or second data group.

8. A path searching apparatus according to claim 5,

wherein said path to be searched comprises a road path on which an automobile can travel, and

said respective first and second geographic points comprise a starting point and a destination, respectively.

9. In a navigation system for processing stored electrical data representative of pre-defined locations within a given geographic area, said system comprising storage means (2) for storing electrical data which repeatedly defines a map of the area but at first and second different display levels, the data for the first and second display levels defining node locations that collectively represent roads situated in the area that are to be depicted at said each display level such that the first and second display levels collectively represent said map at first and second pre-defined levels of detail with the first level having more detail than said second level, the data being organized into respective first and second data groups for, respectively, the first and second display levels such that the data group for the first level includes the data group for the second level, said system further comprising processing means (1, 3, 5, 6, 7, 8) operative in conjunction with said storage means for determining a path between first and second geographic points situated in said area, and display means (4) responsive to said processing means for displaying said path, a method for searching through said data to find the path between the first and second geographic points and for displaying the path comprising the steps of:

in said processing means;

designating, in response to said first and second geographic points, first and second positions on the first level of the map and corresponding to the first and second geographic points,

first detecting, in response to the first and second positions, a plurality of each of first and second node locations in the first level and respectively adjacent to said first and second positions so as to yield corresponding first and second pluralities of adjacent node positions,

second detecting, in response to said first detecting step, whether said second level contains at least one of each of the pluralities of said first and second adjacent node positions and providing a result indicative thereof,

selecting, in responsive to said first detecting step and to the result provided by said second detecting step, one of each of the pluralities of said first and second adjacent node positions as the first and second positions such that if the pluralities of the first and second adjacent node positions contain node locations existing in said second level then the first and second positions are taken, in a pre-defined manner, to be respective ones of said node locations existing in the second level in preference to node locations existing at the first level in the pluralities of said first and second adjacent node positions,

subsequently changing, in response to the result provided by said second detecting step, the level of the map used by said first detecting step from the first to the second level in the event said first and second positions exist in said second level, and

invoking, in response to said first and second positions, said first detecting step to detect next successive pluralities of said first and second node locations until the first and second positions satisfy a pre-determined criteria, and

in the display means;

displaying paths between successive ones of said first positions and between successive ones of said second positions so as to depict the path between said first and second geographic points.

10. A method according to claim 9, wherein said selecting step comprises the step of:

respectively selecting first and second corresponding ones of adjacent node positions from the pluralities of the first and second adjacent node positions as respective new values of the first and second positions, wherein said first and second corresponding ones of the adjacent node positions respectively represent geographic points that are nearest to geographic points represented by immediately prior ones of said first and second positions.

11. In a navigation system for processing stored electrical data representative of pre-defined locations within a given geographic area, said system comprising storage means (2) for storing electrical data which repeatedly defines a map of the area but at first and second different display levels, the data for the first and second display levels defining node locations that collectively represent roads situated in the area that are to be depicted at said each display level such that the first and second display levels collectively represent said map at first and second pre-defined levels of detail with the first level having more detail than said second level, the data being organized into respective first and second data groups for, respectively, the first and second display levels such that the data group for the first level includes the data group for the second level, said system further comprising processing means (1, 3, 5, 6, 7, 8) operative in conjunction with said storage means for determining a path between first and second geographic points situated in said area, and display means (4) responsive to said processing means for displaying said path, a method for searching through said data to find the path between the first and second geographic points and for displaying the path comprising the steps of:

in said processing means;

designating, in response to said first and second geographic points, first and second positions on the first level of the map and corresponding to the first and second geographic points,

determining a geographic distance between geographic points represented by said first and second positions on the first level of the map,

selecting, in response to a value of the distance, said first or second data groups corresponding to said first or second display levels as a selected data group in which to search for said path, and

searching through said selected data group so as to locate successive ones of said node locations therein as successive ones of first and second positions in order to define a path therebetween, and

in the display means;

displaying paths between successive ones of said first positions and between successive ones of said second positions so as to depict the path between said first and second geographic points.

12. A path searching apparatus according to claim 11 wherein said searching step comprises the steps of:

detecting, in the event said second data group is selected, first and second node locations which are geographically situated closest to said first and second positions, respectively,

defining, based on nodes locations in said first data group, respective paths between said first position and said first node location and between said second position and said second node location, and

defining, based on node locations in said second data group, a path between said first and second node locations.