Systems, functional data, and methods for generating a route
First Claim
1. A navigation device comprising:
- a processor;
a memory in communication with the processor; and
a data structure residing in the memory, wherein the processor dynamically inserts selected available adjacent thoroughfare locations from a map into the data structure which are obtained from traversing from a starting thoroughfare location in the direction of an ending thoroughfare location, the data structure maintains a least cost thoroughfare location as its first index location during the inserts, the processor generates a route path by repetitively extracting the first index location from the data structure, the data structure updates the first index location during each extraction.
0 Assignments
0 Petitions
Accused Products
Abstract
Devices, systems, functional data and methods are provided for an improved route generation in navigational enabled devices. The navigational device with route generation capabilities includes a processor communicating with a memory. The memory includes a current location of the device, one or more available locations, and a destination of the device. A display communicates with the processor and is capable of communicating at least a portion of a generated route for the device.
In generating the route, the available locations are inspected repetitively and locations adjacent to a last selected location are inserted into a first data structure such that the first location of the first data structure is always a least cost location associated with all adjacent locations comprising the first data structure. The first location is then optionally inserted into a second data structure. The generated route includes the current location, one or more first locations, and the destination.
35 Citations
20 Claims
-
1. A navigation device comprising:
-
a processor;
a memory in communication with the processor; and
a data structure residing in the memory, wherein the processor dynamically inserts selected available adjacent thoroughfare locations from a map into the data structure which are obtained from traversing from a starting thoroughfare location in the direction of an ending thoroughfare location, the data structure maintains a least cost thoroughfare location as its first index location during the inserts, the processor generates a route path by repetitively extracting the first index location from the data structure, the data structure updates the first index location during each extraction. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A navigation system comprising:
-
a personal digital assistant (PDA);
a Global Positioning Satellite (GPS) receiver integrated with the PDA; and
a navigation application in communication with the PDA and the receiver;
wherein the navigation application dynamically generates a route path from a map in response to receiving a thoroughfare destination and resolving a starting thoroughfare position based on a current physical position of the PDA obtained from the receiver, the navigation application generates the route path by traversing the map from the starting thoroughfare position to the thoroughfare destination and inserting available adjacent thoroughfare locations from the map into a data structure, the data structure maintains its first index location as a least cost location, the navigation application generates the route path by repetitively extracting the first index location from the data structure upon completing the traversing. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A computer-readable medium encoded with functional data to produce an optimal route, comprising:
-
a beginning thoroughfare node;
a destination thoroughfare node; and
one or more intermediate thoroughfare nodes each having a cost;
wherein the medium is organized with the beginning thoroughfare node, the destination thoroughfare node and the one or more intermediate thoroughfare nodes, and a first index location of the medium maintains a least cost node as the one or more intermediate thoroughfare nodes are added to the medium and as a select number of the one or more intermediate thoroughfare nodes are removed from the medium, and wherein the beginning thoroughfare node is initially located at the first index location, and once the destination thoroughfare node is removed from the medium, removed nodes represent an optimal route from the beginning thoroughfare node to the destination thoroughfare node. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification