Transmission of routes between client and server using route IDs
First Claim
1. A method for creating an abbreviated description of an original navigation route, the navigation route having an originating point and a destination point, and represented by a plurality of links, each link joining a plurality of nodes, the method comprising:
- for each node reached by an incoming link on the original route and having multiple exiting links, each exiting link having a heading;
determining, by at least one computer, a heading of the incoming link;
determining, by the computer, the heading of the exiting link along the route exiting the node;
scoring, by the computer, each of the multiple exiting links using a scoring system;
responsive to a determination by the computer that the exiting link along the route is not the highest scoring exiting link, placing, by the computer, a breadcrumb in the abbreviated description of the route, the breadcrumb including coordinates of a point represented by the node, a representation of a heading of the incoming link, and a representation of a heading of the exiting link along the original route; and
placing, by the computer, a breadcrumb at the end of the abbreviated description of the original route, the breadcrumb including coordinates of a node representing a point at the end of the route and a representation of a heading of an incoming link to the node.
10 Assignments
0 Petitions
Accused Products
Abstract
Dehydration of routes enables transmitting a description of a route requiring much less space than full specification of the route. A series of “breadcrumbs” and hints are used for dehydration. A breadcrumb includes coordinates of a point, a heading at which the route enters the breadcrumb, and a heading at which the route leaves the breadcrumb. A dehydration module places a breadcrumb at the location marking the beginning of the route, and having a leaving heading identifying the link in the original route. The node at the end of each link in the original route is examined. If the link leaving the node is the most parallel link to the link entering the node, nothing is added to the dehydrated route. If not, a breadcrumb is added to the dehydrated route, specifying the coordinates of the point, the entering heading of the breadcrumb and the leaving heading of the breadcrumb.
-
Citations
19 Claims
-
1. A method for creating an abbreviated description of an original navigation route, the navigation route having an originating point and a destination point, and represented by a plurality of links, each link joining a plurality of nodes, the method comprising:
-
for each node reached by an incoming link on the original route and having multiple exiting links, each exiting link having a heading; determining, by at least one computer, a heading of the incoming link; determining, by the computer, the heading of the exiting link along the route exiting the node; scoring, by the computer, each of the multiple exiting links using a scoring system; responsive to a determination by the computer that the exiting link along the route is not the highest scoring exiting link, placing, by the computer, a breadcrumb in the abbreviated description of the route, the breadcrumb including coordinates of a point represented by the node, a representation of a heading of the incoming link, and a representation of a heading of the exiting link along the original route; and placing, by the computer, a breadcrumb at the end of the abbreviated description of the original route, the breadcrumb including coordinates of a node representing a point at the end of the route and a representation of a heading of an incoming link to the node. - View Dependent Claims (2, 3, 4, 10, 11, 12)
-
-
5. A method for determining an original navigation route from an abbreviated route description, the abbreviated description including a plurality of breadcrumbs, each breadcrumb including coordinates of a location along the route and at least one of an entering heading and a leaving heading, the method comprising:
-
determining, by at least one computer, an origination point for the original route as a point identified by coordinates of a breadcrumb in the abbreviated route and notated as representing the origination point; selecting as a link in the original route a link most closely parallel to a leaving heading specified by the breadcrumb representing the origination point; for each node at the end of a link selected as a link in the original route; inserting, by the computer, a node at the end of the selected link into the original route; responsive to no breadcrumb in the abbreviated route having coordinates identifying the node, calculating, by the computer, a score for the links leaving the node using a scoring system and selecting, by the computer, as the next link in the original route a link leaving the node receiving the highest score in the scoring system; responsive to one of the breadcrumbs in the abbreviated route having coordinates identifying the node, selecting, by the computer, as the next link in the original route a link leaving the node most parallel to the leaving heading of the matching breadcrumb; and displaying the original route in a user interface of a navigation device. - View Dependent Claims (6, 7, 8, 13, 14, 15)
-
-
9. A method for creating an abbreviated description of an original navigation route, the navigation route having an originating point and a destination point, and represented by a plurality of links, each joining a plurality of nodes, the method comprising:
for each node reached by an incoming link on the original route and having multiple exiting links, each exiting link having a heading; determining, by at least one computer, a heading of the incoming link; determining, by the computer, the heading of the exiting link along the route exiting the node; and responsive to a determination by the computer that the exiting link along the route is not the most parallel exiting link to the incoming link, placing, by the computer, a breadcrumb in the abbreviated description of the route, the breadcrumb including coordinates of a point represented by the node, a representation of a heading of the incoming link, and a representation of a heading of the exiting link along the original route.
-
16. A system for creating an abbreviated description of an original navigation route, the navigation route having an originating point and a destination point, and represented by a plurality of links, each joining a plurality of nodes, the system comprising:
-
a database storing a set of nodes and a set of links, each link joining a plurality of nodes; and a dehydration module configured to create the abbreviated description by, for each node reached by an incoming link on the original route and having multiple exiting links, each exiting link having a heading; determining a heading of the incoming link; determining the heading of the exiting link along the route exiting the node; scoring each of the multiple exiting links using a scoring system; responsive to a determination that the exiting link along the route is not the highest scoring exiting link, place, a breadcrumb in the abbreviated description of the route, the breadcrumb including coordinates of a point represented by the node, a representation of a heading of the incoming link, and a representation of a heading of the exiting link along the original route; and place a breadcrumb at the end of the abbreviated description of the original route, the breadcrumb including coordinates of a node representing a point at the end of the route and a representation of a heading of an incoming link to the node.
-
-
17. A system for determining an original navigation route from an abbreviated route description, the abbreviated description including a plurality of breadcrumbs, each breadcrumb including coordinates of a location along the route and at least one of an entering heading and a leaving heading, the system comprising:
-
a user interface; a processor configured to execute instructions; a memory including instructions, which when executed by the processor cause the processor to; determine an origination point for the original route as a point identified by coordinates of a breadcrumb in the abbreviated route and notated as representing the origination point; select as a link in the original route a link most closely parallel to a leaving heading specified by the breadcrumb representing the origination point; for each node at the end of a link selected as a link in the original route; insert a node at the end of the selected link into the original route; responsive to no breadcrumb in the abbreviated route having coordinates identifying the node, calculate a score for the links leaving the node using a scoring system and select as the next link in the original route a link leaving the node receiving the highest score in the scoring system; responsive to one of the breadcrumbs in the abbreviated route having coordinates identifying the node, select as the next link in the original route a link leaving the node most parallel to the leaving heading of the matching breadcrumb; and display the original route in the user interface.
-
-
18. A system for reducing communication overhead of transmitting navigation route information, comprising:
-
a route dehydration system configured to dehydrate an original navigation route having an originating point and a destination point and represented by a plurality of links joining a plurality of nodes to form an abbreviated route description; and a route rehydration system configured to receive the abbreviated route description and rehydrate the abbreviated route description to form a rehydrated route; wherein dehydrating the original navigation route comprises, for each node reached by an incoming link on the original route and having multiple outgoing links, scoring each of the outgoing links using a scoring methodology and, responsive to the outgoing link corresponding to the original navigation route not being the highest scoring link of the multiple outgoing links, adding a breadcrumb to the abbreviated route description, the breadcrumb including coordinates of a point represented by the node, a representation of a heading of the incoming link, and a representation of a heading of the outgoing link corresponding to the original navigation route; and wherein rehydrating the abbreviated route description comprises, for each node at the end of a link selected as belonging to the rehydrated route, adding a node at the end of the selected link to the rehydrated route, and responsive to the node not corresponding to a breadcrumb in the abbreviated route description, scoring outgoing links at the node using the scoring methodology and selecting a highest-scoring link as the next link. - View Dependent Claims (19)
-
Specification