Method and apparatus for backtracking a path
DCFirst Claim
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 Assignments
Litigations
1 Petition
Accused Products
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.
-
Citations
16 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. - View Dependent Claims (2, 3, 4, 5, 6)
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. - View Dependent Claims (8)
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. - View Dependent Claims (10, 11)
-
-
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. - View Dependent Claims (13)
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. - View Dependent Claims (15, 16)
-
Specification