Method and system for route calculation in a navigation application

A route calculation tool program for use in a navigation system used with a map database that represents a road network in a geographic region, wherein said road network is said may database by data that represent each segment of road between endpoints thereof that correspond to intersections of said segment of road with other segment of roads, said route calculation tool program comprising:

• a first search tree associated with an origin and a second search tree associated with a destination, wherein each of said search trees includes gate data structures each of which represents a position on a road network represented by said map database and a direction by which said position is accessible in a desired direction of travel, and wherein one of said gate data structures in said first search tree is a seed gate data structure that represents said origin as a first position along a first segment of a road between endpoints thereof and a direction from said position along said first segment of a road and wherein one of sad gate data structures in said second search tree is a seed gate data structure that represents the destination as a second position along a second segment of a road between endpoints thereof and a direction from said second position along said second segment of a road;
• wherein the route calculation tool program includes at least one priority queue that references one of said gate data structures in one of said search trees;
• and
• wherein said route calculation tool program expands said one gate data structure referenced by said priority queue to form successor gate data structures thereof whereby a solution route is obtained by at least one gate data structure in said first search tree corresponding to at least one gate data structure in said second search tree.

A method of performing a route calculation function using a navigation system that uses a map database that includes road segment records that represent portions of roads in a road network in a geographic region, comprising the steps of:

• identifying at least one seed gate associated with a first location in said geographic region through which a solution route is constrained to pass, wherein said seed gate comprises an associated locus representing a position along a portion of a road represented by a road segment record and a seed gate target node corresponding to a node of the road segment record, said seed gate target node representing an endpoint of the portion of a road represented by said road segment record by which said location is accessible in a desired direction of travel;
• expanding said at least one seed gate to form at least one successor gate, wherein each successor gate so formed comprises an associated node corresponding to the target node of the seed gate which was expanded to form said successor gate and a successor gate target node, said successor gate target node corresponding to a node of a road segment record that represents a portion of a road which is accessible in the desired direction of travel between the positions represented by the associated node and the target node of the successor gate;
• comparing each successor gate formed by said expanding step to corresponding gates associated with a second location in said geographic region through which said solution route is constrained to pass and outputting a solution route if a match is found;
• if a match is not found in said comparing step, evaluating each successor gate to determine one successor gate having a higher priority than any other successor gate;
• expanding said one successor gate having the higher priority than any other successor gate to form at least one additional successor gate, wherein each additional successor gate comprises an associated node corresponding to the target node of the successor gate which was expanded to form said additional successor gate and a target node of the successor gate, said target node of said successor gate corresponding to a node of a road segment record that represents a portion of a road which is accessible in the desired direction of travel between the positions represented by the associated node and the target node of the additional successor gate;
• comparing each successor gate formed by said expanding step to said second location in said geographic region through which said solution route is constrained to pass and outputting a solution route if a match is found;
• and
• if a match is not found in said second comparing step, continuing to perform said evaluating, expanding, and comparing steps until a match is found.

A method of providing partial solution routes using a navigation system that uses a map database that includes road segment records that represent portions of roads in a road network in a geographic region, comprising the steps of:

• identifying at least one seed gate associated with a first location in said geographic region through which a solution route is constrained to pass, wherein said seed gate comprises an associated locus representing a position along a portion of a road represented by a road segment record and a seed gate target node corresponding to a node of the road segment record, said seed gate target node representing an endpoint of the portion of a road represented by said road segment record by which said location is accessible in a desired direction of travel;
• expanding said at least one seed gate to form at least one successor gate, wherein each successor gate so formed comprises an associated node corresponding to the target node of the seed gate which was expanded to form said successor gate and a successor gate target node, said successor gate target node corresponding to a node of a road segment record that represents a portion of a road which is accessible in the desired direction of travel between the positions represented by the associated node and the target node of the successor gate;
• comparing each successor gate formed by said expanding step to a second location in said geographic region through which said solution route is constrained to pass;
• evaluating each successor gate to determine one successor gate having a higher priority than any other successor gate;
• expanding said one successor gate having the higher priority than any other successor gate to form at least one additional successor gate, wherein each additional successor gate comprises an associated node corresponding to the target node of the successor gate which was expanded to form said additional successor gate and a target node of the successor gate, said target node of said successor gate corresponding to a node of a road segment record that represents a portion of a road which is accessible in the desired direction of travel between the positions represented by the associated node and the target node of the additional successor gate;
• and
• prior to finding a match when comparing each successor gate formed by said expanding step to said second location in said geographic region through which said solution route is constrained to pass, outputting a partial solution route comprised of a list of segments corresponding to at least some of the gates which had been expanded based upon having a higher priority than any other gate.

A route calculation tool program for use in a navigation system and adapted to calculate a route between a first location and a second location, said route calculation tool program comprising:

• object logic operatively executed by a processor of said navigation system, the object logic comprising a plurality of independent program objects, wherein each program object receives input data and provides output data according to a property of the program object, wherein said route calculation tool program comprises:
• at least one of the program objects comprising a route calculation program object operatively adapted to receive a first waypoint program object representing said first location and a second waypoint program object representing said second location;
• wherein said route calculation program object further comprises:
• an outbound search tree program object including at least one seed gate and successor gates thereof, wherein said at least one seed gate represents a position along a road segment from which the first location can be exited, said position derived from said first waypoint program object;
• an inbound search tree program object including said at least one seed gate and successor gates thereof, wherein said at least one seed gate represents a position along a road segment into which the second location can be entered, said position derived from said second waypoint program object;
• an outbound priority queue program object including prioritized references to unexpanded gates in said outbound search tree program object;
• and
• an inbound priority queue object including prioritized references to unexpanded gates in said inbound search tree program object;
• and
• wherein at least one of said search tree program object is adapted to grow by expanding the gates therein to find a solution route when said search tree program objects include at least one common gate.