Route determination method and apparatus for navigation system

• US 20060241854A1
• Filed: 04/20/2005
• Published: 10/26/2006
• 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
• Granted Patent: US 7,945,383 B2
• Time in Patent Office: Days
• 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, comprising the following steps of:

determining whether a non-digitized area exists between the start point and the destination;

creating a processing point that acts as an intermediary point between the start point and the destination;

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 claimed 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, comprising:

means for determining whether a non-digitized area exists between the start point and the destination;

means for creating a processing point that acts as an intermediary point between the start point and the destination;

means for 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;

means for 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

means for 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 means for determining the existence of the non-digitized area includes means for 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 means for establishing the processing point includes means for finding two furthest points of the non-digitized area.

13. An apparatus of calculating a route as defined in claim 10, wherein the means for establishing the processing point includes means for 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, further comprising means for 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 means for determining whether the route search operation using the processing point is necessary includes means for 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 means for determining whether the route search operation using the processing point is necessary includes means for 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 means for 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 claimed in claim 17, further comprising means for 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.