Route determination method and apparatus for navigation system

• US 7,945,383 B2
• Filed: 04/20/2005
• Issued: 05/17/2011
• Est. Priority Date: 04/20/2005
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Schaaf, David, Vu, Tien, Tu, Ihung
• Primary Examiner(s): Tran; Khoi
• Assistant Examiner(s): Broadhead; Brian J
• Application Number:
  US11/109,991
• Publication Number:
  US 20060241854A1
• Time in Patent Office: 2,218 Days
• Field of Search: 701/202, 701/201, 701/208, 701/209, 701/210, 701/211, 701/217, 340/990, 340/995.2, 340/995.17, 340/995.21, 340/995.23, 340/995.24, 340/988, 709/243
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A navigation system is able to find an optimum route to a destination even when a large non-digitized area exists between a starting point to the destination. The navigation system produces processing points based on a particular shape and size of the large non-digitized area and determines whether such processing points should be used for route search operations. When it is determined that the route search operation is effective, the navigation system performs A* algorithm search operations with respect to the start point, processing points and the destination and detects an optimum route to detour the large non-digitized area.

Claims

1. A method of calculating a route from a start point to a destination based on map database, comprising the following steps of:

determining whether a non-digitized area exists between the start point and the destination, where the non-digital area is an area in which no road segments are available in the map database;

automatically creating a processing point that acts as an intermediary point between the start point and the destination if the non-digitized area exists;

performing a first route search using an A* algorithm between the start point and the processing point to produce a first part of a calculated route;

performing a second route search using an A* algorithm between the destination and the processing point to produce a second part of the calculated route; and

combining the first part and second part to complete the calculated route that connects the start point and the destination.

2. A method of calculating a route as defined in claim 1, wherein the step of determining the existence of the non-digitized area includes a step of finding polygon data representing the non-digitized area through map data from a map storage medium.

3. A method of calculating a route as defined in claim 1, wherein the step of establishing the processing point includes a step of finding two furthest points of the non-digitized area.

4. A method of calculating a route as defined in claim 1, wherein the step of establishing the processing point includes a step of creating a rectangle each side of which contacts with farthest point of the non-digitized area or is apart from the farthest points of the non-digitized area by a predetermined distance.

5. A method of calculating a route as defined in claim 1, further comprising the step of determining whether a route search operation using the processing point is necessary based on a particular shape, size, and location of the non-digitized area relative to the locations of the start point and the destination.

6. A method of calculating a route as defined in claim 5, wherein the step of determining whether the route search operation using the processing point is necessary includes a step of comparing the length of a straight line from the start point to the destination and a straight line between two furthest points of the non-digitized area.

7. A method of calculating a route as defined in claim 5, wherein the step of determining whether the route search operation using the processing point is necessary includes a step of determining whether a straight line connecting the start point and the destination and a longest line connecting two farthest points of the non-digitized area cross with one another, and a step of determining whether the longest line connecting the farthest points of the non-digitized area is longer than the straight line connecting the start point and the destination.

8. A method of calculating a route as defined in claim 1, wherein two calculated routes that roundabout the non-digitized area are produced by applying the route search operations to two processing points.

9. A method of calculating a route as defined in claim 8, further comprising the step of comparing the two calculated routes with respect to predetermined criteria and selecting one of the routes as an optimum route between the start point and the destination.

10. An apparatus of calculating a route from a start point to a destination based on map database, comprising:

a map storage medium having the map database which stores road segments data and other map data related to determining a preferable route between a start point and a destination;

a monitor for displaying information and images related to operations of determining the preferable route and route guidance to the destination;

a route search controller for controlling overall operations of a route search process for determining the preferable route between the start point and the destination and a route guidance process for guiding a user to the destination through the preferable route;

a memory for temporally storing data necessary for the route search process;

wherein the route search controller controls the following operations of;

determining whether a non-digitized area exists between the start point and the destination, where the non-digital area is an area in which no road segments are available in the map database;

automatically creating a processing point that acts as an intermediary point between the start point and the destination if the non-digitized area exists;

performing a first route search using an A* algorithm between the start point and the processing point to produce a first part of a calculated route;

performing a second route search using an A* algorithm between the destination and the processing point to produce a second part of the calculated route; and

combining the first part and second part to complete the calculated route that connects the start point and the destination.

11. An apparatus of calculating a route as defined in claim 10, wherein the route search controller further controls an operation of finding polygon data representing the non-digitized area through map data from a map storage medium.

12. An apparatus of calculating a route as defined in claim 10, wherein the route search controller further controls an operation of finding two furthest points of the non-digitized area.

13. An apparatus of calculating a route as defined in claim 10, wherein the route search controller further controls an operation of creating a rectangle each side of which contacts with farthest point of the non-digitized area or is apart from the farthest points of the non-digitized area by a predetermined distance.

14. An apparatus calculating a route as defined in claim 10, wherein the route search controller further controls an operation of determining whether a route search operation using the processing point is necessary based on a particular shape, size, and location of the non-digitized area relative to the locations of the start point and the destination.

15. An apparatus of calculating a route as defined in claim 14, wherein the route search controller further controls an operation of comparing the length of a straight line from the start point to the destination and a straight line between two furthest points of the non-digitized area.

16. An apparatus of calculating a route as defined in claim 14, wherein the route search controller further controls operations of determining whether a straight line connecting the start point and the destination and a longest line connecting two farthest points of the non-digitized area cross with one another, and determining whether the longest line connecting the farthest points of the non-digitized area is longer than the straight line connecting the start point and the destination.

17. An apparatus of calculating a route as defined in claim 10, wherein two calculated routes that roundabout the non-digitized area are produced by applying the route search operations to two processing points.

18. An apparatus of calculating a route as defined in claim 17, wherein the route search controller further controls an operation of comparing the two calculated routes with respect to predetermined criteria and selecting one of the routes as an optimum route between the start point and the destination.