Method and system for reducing shape points for a navigation system

• US 6,567,741 B1
• Filed: 11/01/2001
• Issued: 05/20/2003
• Est. Priority Date: 11/01/2001
• Status: Active Grant

• Current Assignee: General Motors LLC (General Motors Company)
• Original Assignee: General Motors Corporation (Motors Liquidation Co. GUC Trust)
• Inventors: Aloi, Daniel N., Stefan, Jeffrey M., Kacel, Richard J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): MANCHO, RONNIE M
• Application Number:
  US10/002,323
• Publication Number:
  US 20030083805A1
• Time in Patent Office: 565 Days
• Field of Search: 701/200-203, 701/205-215, 340/988, 340/989, 340/991-994, 707/100, 342/357.01, 342/357.06, 342/357.08, 342/357.12
• US Class Current: 701/206
• CPC Class Codes: G01C 21/3626 Details of the output of route guidance instructions traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

The present invention provides a system, a method and a computer usable medium including a program for generating navigation instructions for a vehicle. This may be done by determining a number of shape points between a set of primary maneuver points and determining whether the number of shape points exceeds a cardinal threshold; determining a great circle distance and a bearing between a first shape point and a second shape point, determining whether the bearing exceeds an angular threshold and eliminating the second shape point if it is determined that the bearing exceeds the angular threshold.

Claims

1. A method of determining navigation instructions for a vehicle, comprising:

determining a number of shape points between a set of primary maneuver points for navigating a vehicle;

determining whether the number of shape points exceeds a cardinal threshold;

determining a bearing between a first shape point and a second shape point, if it is determined that the number of shape points exceeds the cardinal threshold;

determining whether the bearing exceeds an angular threshold; and

eliminating the second shape point if it is determined that the bearing exceeds the angular threshold.

2. The method of claim 1, further comprising:

eliminating remaining second shape points within consecutive pairs of shape points between primary maneuver points, if associated bearings exceed the angular threshold.

3. The method of claim 1, further comprising:

determining a bearing between a third shape point and one of the first shape point and the second shape point.

4. The method of claim 3, further comprising:

eliminating the third shape point if the second bearing exceeds the angular threshold.

5. The method of claim 1, wherein the set of primary maneuver points is one of a plurality of sets of primary maneuver points in the navigation route.

6. The method of claim 1, wherein the anglular threshold value is predetermined.

7. The method of claim 1, wherein the cardinal threshold is predetermined.

8. A computer usable medium including a program for determining instructions for a vehicle, comprising:

computer readable program code that determines a number of shape points between a set of primary maneuver points for navigating a vehicle;

computer readable program code that determines whether the number of shape points exceeds a cardinal threshold;

computer readable program code that determines a bearing between a first shape point and a second shape point, if it is determined that the number of shape points exceeds the cardinal threshold;

computer readable program code that determines whether the bearing exceeds an angular threshold; and

computer readable program code that eliminates the second shape point, if it is determined that the bearing exceeds the angular threshold.

9. The computer usable medium of claim 8, further comprising:

computer readable program code that eliminates remaining second shape points within consecutive pairs of shape points between primary maneuver points, if associated bearings exceed the angular threshold.

10. The computer usable medium of claim 8, further comprising:

computer readable program code that determines a bearing between a third shape point and one of the first shape point and the second shape point.

11. The computer usable medium of claim 10, further comprising:

computer readable program code that eliminates the third shape point, if the second bearing exceeds the angular threshold.

12. The computer usable medium of claim 8, wherein the set of primary maneuver points is one of a plurality of sets of primary maneuver points in the navigation route.

13. The computer usable medium of claim 8, wherein the cardinal threshold value is predetermined.

14. The computer usable medium of claim 8, wherein the angular threshold value is predetermined.

15. A system for determining navigation instructions for a vehicle, comprising:

means for determining a number of shape points between a set of primary maneuver points for navigating a vehicle;

means for determining whether the number of shape points exceeds a cardinal threshold;

means for determining a bearing between a first shape point and a second shape point, if it is determined that the number of shape points exceeds the cardinal threshold;

means for determining whether the bearing exceeds an angular threshold; and

means for eliminating the second shape point if it is determined that the bearing exceeds the angular threshold.

16. The system of claim 15, further comprising:

means for eliminating remaining second shape points within consecutive pairs of shape points between primary maneuver points if associated bearings exceed the angular threshold.

17. The system of claim 15, further comprising:

means for determining a bearing between a third shape point and one of the first shape point and a second shape point.

18. The system of claim 17, further comprising:

means for eliminating the third shape point if the second bearing exceeds the angular threshold.