Cost zones

• US 5,729,458 A
• Filed: 12/29/1995
• Issued: 03/17/1998
• Est. Priority Date: 12/29/1995
• Status: Expired due to Term

• Current Assignee: Tele Atlas North America (TomTom NV)
• Original Assignee: Etak, Inc. (TomTom NV)
• Inventors: Poppen, Richard Frederick
• Primary Examiner(s): Cosimano, Edward R.
• Application Number:
  US08/581,169
• Time in Patent Office: 809 Days
• Field of Search: 340/989, 340/990, 340/995, 364/400, 364/424.02, 364/444, 364/464.01, 364/467, 364/424.027, 364/424.029, 364/424.031, 364/444.1, 364/444.2, 364/464.1, 364/464.27 , 364/464.28, 395/140, 395/141
• US Class Current: 705/400
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: G06Q 30/0284 Time or distance, e.g. usage of parking meters or taximeters
• CPC Class Codes: G07B 15/06 Arrangements for road pricing or congestion charging of vehicles or vehicle users, e.g. automatic toll systems

Abstract

A cost zone about an origin on an digital map includes the area on the map that can be traveled to, from the origin, which has a cost of travel less than a predetermined cost. The cost can be measured in distance, time of travel, ease of turning, tolls; etc. The steps of creating a cost zone include identifying a set of decision points on the map that are within a predetermined factor of the desired cost, triangulating the decision points to create a set of triangles and interpolating along a subset of the sides of the triangles to estimate the locations along the sides that can be traveled to at the desired cost.

Claims

1. A method of creating a cost zone about an origin on an electronic map, comprising the steps of:

identifying a set of nodes on said electronic map that are within a predetermined factor of a desired cost of said origin;

triangulating said set of nodes to create a set of triangles, said triangles having sides; and

interpolating along a subset of said sides of said triangles to estimate locations on said sides having said desired cost, said locations defining a boundary of said cost zone.

2. A method according to claim 1, further including the step of connecting said locations.

3. A method according to claim 1, wherein:

said desired cost is a traveling time.

4. A method according to claim 1, wherein:

said desired cost is a distance.

5. A method according to claim 1, wherein:

said desired cost is a cost of traveling away from said origin.

6. A method according to claim 1, wherein:

said desired cost is a cost of traveling toward said origin.

7. A method according to claim 1, wherein:

said step of triangulating includes creating Delaunay triangles.

8. A method according to claim 1, wherein:

each of said sides of said triangles have two end points, both end points being nodes; and

said step of interpolating includes the steps of;

finding one of said sides having one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost;

interpolating along said one side to find a first location along said one side having a cost equal to said desired cost;

choosing a triangle that includes said one side;

choosing a next side of said chosen triangle, said next side not being said one side, said next side including one end point with a cost less than said desired cost and a second end point having a cost greater than said desired costs; and

interpolating along said next side to find a second location along said next side having a cost equal to said desired cost.

9. A method according to claim 1, further including the step of:

determining an island inside said cost zone, said island representing an area not accessible within said desired cost.

10. A method according to claim 1, further including the step of:

determining an island outside said cost zone, said island representing an area accessible within said desired cost.

11. A method according to claim 1, further including the step of:

symbolically connecting said locations.

12. A method according to claim 1, further including the step of:

storing a list of said locations in a computer readable storage medium.

13. A method according to claim 2, wherein:

said list stores latitude and longitude data for said locations.

14. A method according to claim 1, wherein:

said step of identifying a set of nodes includes the steps of;

a) considering said origin as a head node of a priority queue;

b) determining, for each neighbor node of said head node, a travel cost of traveling from said origin, through said head node, to said neighbor node;

c) storing in said priority queue each neighbor node of said head node and said travel cost, if said neighbor node is not already stored in said queue with a lower travel cost; and

d) removing said head node from said queue such that said queue has a new head node.

15. A method according to claim 14, further including the step of

e) repeating steps b)-d) if said new head node'"'"'s travel cost stored in said queue is less than said predetermined factor of said desired cost.

16. A method according to claim 1, wherein:

said step of triangulating includes the steps of;

(a) adding three nodes to a data structure;

(b) creating a triangle out of said three nodes;

(c) adding an additional node to said data structure;

(d) connecting all three vertices of a surrounding triangle to said additional node, if said additional node is within said surrounding triangle;

(e) connecting said additional node to all nodes in said data structure that said additional node can be connected to by a straight line without intersecting any sides of triangle if said additional node is not within any triangles;

(f) connecting said additional node to a vertex opposite a particular side of a particular triangle, if said additional node is on said particular side; and

(g) determining whether at least a subset of triangles represented in said data structure are Delaunay triangles.

17. A method according to claim 16, wherein:

repeating steps (c)-(g) until all additional nodes have been added to said data structure.

18. A method according to claim 1, wherein:

said step of interpolating includes;

interpolating along a first side of a first triangle, said first side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost;

interpolating along a second side of a second triangle, said second side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said second triangle sharing said first side with said first triangle; and

interpolating along a third side of a third triangle, said third side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said third triangle sharing said second side with said second triangle.

19. A method according to claim 18, wherein:

said step of interpolating along a first side determines a first interpolated location;

said step of interpolating along a second side determines a second interpolated location;

said step of interpolating along a third side determines a third interpolated location; and

said method further includes the steps of connecting said first interpolated location with said second interpolated location, and connecting said second interpolated location with said third interpolated location.

20. A computer readable storage medium having computer readable code embodied on said computer readable storage medium, said computer readable code for creating a cost zone, said computer readable code comprising:

first program code, said first program code identifies a set of nodes on an electronic map that are within a predetermined factor of a desired cost of an origin;

second program code, said second program code triangulates said set of nodes to create a set of triangles, said triangles having sides; and

third program code, said third program code interpolates along a subset of said sides of said triangles to estimate locations on said sides having said desired cost, said locations defining a boundary of said cost zone.

21. A computer readable storage medium according to claim 20, wherein said computer readable code further comprises:

fourth program code, said fourth program code stores a list of said locations in a computer readable storage medium, said list stores latitude and longitude data for said locations.

22. A computer readable storage medium according to claim 20, wherein:

said second program code creates Delaunay triangles.

23. A computer readable storage medium according to claim 20, wherein:

said second program code;

adds three nodes to a data structure;

creates a triangle out of said three nodes;

adds an additional node to said data structure;

connects all three vertices of a surrounding triangle to said additional node, if said additional node is within said surrounding triangle;

connects said additional node to all nodes in said data structure that said additional node can be connected to by a straight line without intersecting any sides of triangle if said additional node is not within any triangles;

connects said additional node to a vertex opposite a particular side of a particular triangle, if said additional node is on said particular side; and

determines whether a subset of said triangles in said data structure is a Delaunay triangle.

24. A computer readable storage medium according to claim 20, wherein:

said third program code;

interpolates along a first side of a first triangle, said first side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost;

interpolates along a second side of a second triangle, said second side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said second triangle sharing said first side with said first triangle; and

interpolates along a third side of a third triangle, said third side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said third triangle sharing said second side with said second triangle.

25. A computer readable storage medium according to claim 20, wherein:

each of said sides of said triangles have two end points, both end points being nodes; and

said third program code;

finds one of said sides having one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost;

interpolates along said one side to find a first location along said one side having a cost equal to said desired cost;

chooses a triangle that includes said one side;

chooses a next side of said chosen triangle, said next side not being said one side, said next side including one end point with a cost less than said desired cost and a second end point having a cost greater than said desired costs; and

interpolates along said next side to find a second location along said next side having a third cost equal to said desired cost.

26. A computer readable storage medium according to claim 20, wherein:

said first program code;

a) considers said origin as a head node of a priority queue;

b) determines for each neighbor node of said head node, a travel cost of traveling from said origin, through said head node and to said neighbor node;

c) stores in said priority queue each neighbor node of said head node and said travel cost, if said neighbor node is not already stored in said queue with a lower travel cost; and

d) removes said head node from said queue such that said queue has a new head node.

27. A computer readable storage medium according to claim 26, wherein:

said first program code;

e) repeats steps b)-d) if said new head node'"'"'s travel cost stored in said queue is less than said predetermined factor of said desired cost.

28. An apparatus for creating a cost zone about an origin on an electronic map, comprising:

means for identifying a set of nodes on said electronic map that are within a predetermined factor of a desired cost of said origin;

means for triangulating said set of nodes to create a set of triangles, said triangles having sides; and

means for interpolating along a subset of said sides of said triangles to estimate locations on said sides having said desired cost, said locations defining a boundary of said cost zone.

29. An apparatus according to claim 28, wherein:

each of said sides of said triangles have two end points, both end points having a first cost associated with traveling from said origin to node; and

said means for interpolating includes;

means for interpolating along a fast side of a first triangle, said first side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost;

means for interpolating along a second side of a second triangle, said second side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said second triangle sharing said first side with said first triangle; and

means for interpolating along a third side of a third triangle, said third side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said third triangle sharing said second side with said second triangle.