Method and apparatus for backtracking a path

• US 6,459,987 B1
• Filed: 11/15/1996
• Issued: 10/01/2002
• Est. Priority Date: 11/15/1996
• Status: Expired due to Term

• Current Assignee: Garmin Corporation (Garmin Limited)
• Original Assignee: Garmin Corporation (Garmin Limited)
• Inventors: Beesley, Darin J., Krull, Jay Dee
• Primary Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/751,125
• Time in Patent Office: 2,146 Days
• Field of Search: 701/200, 701/201, 701/202, 701/207, 701/208, 701/209, 701/213, 701/211, 701/214, 340/988, 340/990, 340/995, 342/357, 342/451, 342/457
• US Class Current: 701/213
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A method for automatically generating a point-reduced backtrack route is provided, using the aid of Global Positioning System technology. The method begins by recording a potentially very large series of data points using GPS technology and a user-selected point recording algorithm into a forward-track route. A point-reducing algorithm is then used to reduce the forward track to a backtrack route which preserves the topological essence of the original route, but with far fewer data points. This reduced backtrack route is then suitable for storage in a memory constrained device, and is suitable for backtrack navigation without the need for the large set of original route points. Storage of a number of such backtrack routes is thus made available to the end user.

Claims

1. A method for generating a backtrack from a plurality of data points which have been stored in a memory of a Global Positioning System, said data points having a first, last and intermediate data points corresponding to geographic positions, the method comprising the steps of:

initializing a counter C to a value of 1, said counter C corresponding to a memory location on a memory stack;

storing said last data point in said memory stack at a first memory location;

assigning said last data point to a variable E;

initializing a stack counter N to a value of 2;

assigning said first data point to a variable B;

comparing said counter C to zero;

conducting the following steps if said counter C is greater than zero;

computing a straight line from said variable B to said variable E;

computing a shortest distance for each of said intermediate data points from said straight line, thereby having a plurality of shortest distances corresponding in a one to one relationship to said intermediate data points;

determining the longest of each of said shortest distances and assigning said intermediate data point corresponding to said longest distance to a variable L and assigning said longest distance to a variable D;

comparing said variable D to a threshold value;

increasing the value of counter N by one, storing said variable L in said memory stack at memory location S(C), assigning the value of variable L to variable E, and returning to said comparing said counter C to zero step;

if D is greater than said threshold value;

decreasing the value of counter C by one, assigning the value of variable E to variable B and assigning the value of stack memory location S(c−

1) to variable E, and returning to said comparing said counter C to zero step;

if D is less than or equal to said threshold value;

conducting the following steps if variable C is less than or equal to zero;

comparing N to a predetermined memory limit;

increasing said threshold value by a predetermined value, and returning to initializing a counter C step;

if N is greater than said memory limit; and

navigating to said first position utilizing said positions stored in said stack as way-points for said global positioning system.

2. The method recited in claim 1, wherein said threshold value is entered by a user in an input device to said global positioning system.

3. The method recited in claim 1, wherein said shortest distance is computed by:

computing a plurality of line perpendicular to said straight line and intersecting each of said intermediate data points, and computing the distance of each of said perpendicular lines between an intersection of said straight line each respective intermediate data point.

4. The method recited in claim 1, wherein said intermediate data points are stored at predetermined time intervals.

5. The method recited in claim 1, wherein said intermediate data points are entered by a user in an input device to said global positioning system.

6. The method recited in claim 1, wherein said intermediate data points are stored by:

acquiring a first data point corresponding to a first geographic position;

storing a first data point corresponding in said memory;

acquiring a second data point corresponding to a second geographic position;

storing said second data point in said memory;

acquiring a current data point corresponding to a current geographic position;

computing a straight line from said first data point to said second data point;

computing the shortest distance from said current data point and said line;

comparing said shortest distance to a threshold value;

discarding said current data point if said shortest distance is less than said threshold value; and

storing said current data point in said memory if said shortest distance is greater than or equal to said threshold value.

7. A method for generating a backtrack path from a set of data points stored in a memory of a global positioning system device, said data points corresponding to geographic positions on a forward path, said method comprising:

selecting a subset of said set of data points; and

storing said subset of data points in said memory as the backtrack path.

8. The method as set forth in claim 7, wherein said set of data points includes a first data point corresponding to a beginning of the forward path and a last data point corresponding to an end of said forward path, said method further comprising:

computing a straight line between said beginning and said end of said forward path, wherein said step of selecting a subset of said data points is a function of the distance from the geographical position corresponding to each said data point and said computed straight line.

9. A global positioning system receiver device comprising:

memory having stored therein a set of data points, each said data point of said set corresponding to a geographic position on a forward path; and

a processor, connected to said memory, for computing a backtrack path by selecting a subset of said data points of said set.

10. The global positioning system receiver device as set forth in claim 9, wherein said subset of data points comprises at least one less data point than is comprised in said set of data points.

11. The global positioning system receiver device as set forth in claim 9, wherein said set of data points includes a first data point corresponding to a beginning of the forward path and a last data point corresponding to an end of said forward path, and wherein said processor determines when to include each data point of said set in said subset of data points based upon a distance from the geographic position represented by the data point and a computed straight line between said beginning and said end of said forward path.

12. A method for generating a backtrack path from a set of data points stored in a memory of a global positioning system device, said data points corresponding to geographic positions on a forward path, said method comprising:

automatically selecting a subset of said set of data points; and

automatically storing said subset of data points in said memory as the backtrack path.

13. The method as set forth in claim 12, wherein said set of data points includes a first data point corresponding to a beginning of the forward path and a last data point corresponding to an end of said forward path, said method further comprising:

computing a straight line between said beginning and said end of said forward path, wherein said step of selecting a subset of said data points is a function of the distance from the geographical position corresponding to each said data point and said computed straight line.

14. A global positioning system receiver device comprising:

a memory having stored therein a set of data points, each said data point of said set corresponding to a geographic position on a forward path; and

a processor, connected to said memory, for automatically computing a backtrack path by selecting a subset of said data points of said set.

15. The global positioning system receiver device as set forth in claim 14, wherein said subset of data points comprises at least one less data point than is comprised in said set of data points.

16. The global positioning system receiver device as set forth in claim 14, wherein said set of data points includes a first data point corresponding to a beginning of the forward path and a last data point corresponding to an end of said forward path, and wherein said processor determines when to include each data point of said set in said subset of data points based upon a distance from the geographical position represented by the data point and a computed straight line between said beginning and said end of said forward path.