Cost zones

• US 6,026,384 A
• Filed: 10/21/1997
• Issued: 02/15/2000
• 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/954,534
• Time in Patent Office: 847 Days
• Field of Search: 340/989, 340/990, 340/995, 345/440, 345/441, 364/400, 701/23, 701/25, 701/26, 701/201, 701/202, 705/400, 705/417, 705/418
• 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 for implementing a cost zone using an electronic map, comprising the steps of:

storing an indication of an origin;

determining costs for traversing said electronic map from said origin to a set of locations in said electronic map; and

determining a subset of said set of locations in said electronic map that are approximately a predetermined cost from said origin, said subset of said set of locations defining boundary of said cost zone.

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

receiving an indication of said predetermined cost.

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

receiving an indication of a type of cost to be minimized.

4. A method according to claim 1, further including the step of storing said subset of said set of locations in a data structure.

5. A method according to claim 1, wherein:

said subset of said set of locations are vertices of a polygon, said polygon represents said boundary.

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

drawing said boundary.

7. A method according to claim 1, further including the steps of:

drawing at least a portion of said electronic map; and

drawing said boundary.

8. A method according to claim 1, further including the steps of:

receiving a query as to whether a particular address is within said cost zone; and

determining whether said particular address'"'"' location in said electronic map is in said cost zone.

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

receiving a query as to whether a particular business is within said cost zone; and

determining whether said particular business'"'"' location in said electronic map is in said cost zone.

10. 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 predetermined cost.

11. 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 predetermined cost.

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

receiving said indication of an origin.

13. A method according to claim 1, further including the steps of:

drawing at least a portion of said electronic map; and

highlighting said cost zone.

14. A method according to claim 13, wherein:

said step of highlighting includes showing said cost zone in a different color than other portions of said electronic map.

15. An apparatus for implementing a cost zone using an electronic map, comprising

a display,

a processor readable storage unit for storing at least part of said electronic map;

drawing said boundary.

16. An apparatus according to claim 15, wherein said method further comprising the step of:

receiving an indication of said predetermined cost.

17. An apparatus according to claim 15, wherein said method further comprising the step of:

receiving an indication of a type of cost to be minimized.

18. An apparatus according to claim 15, wherein said method further comprising the step of:

storing said set of locations in a data structure.

19. An apparatus according to claim 15, wherein said method further comprising the step of:

drawing said boundary.

20. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method comprising the steps of:

receiving an indication of an origin;

determining costs for traversing said electronic map from said origin to a set of locations in said electronic map; and

determining a subset of said set of locations in said electronic map that are approximately a predetermined cost from said origin, said subset of said set of locations defining a boundary of said cost zone.

21. A processor readable storage medium according to claim 20, wherein said method further comprises the step of:

receiving an indication of said predetermined cost.

22. A processor readable storage medium according to claim 20, wherein said method further comprises the step of:

receiving an indication of a type of cost to be minimized.

23. A processor readable storage medium according to claim 20, wherein said method further comprises the step of:

storing said subset of said set of locations in a data structure.

24. A processor readable storage medium according to claim 20, wherein said method further comprises the step of:

drawing said boundary.

25. A processor readable storage medium according to claim 20, wherein said method further comprises the steps of:

receiving a query as to whether a particular address is within said cost zone; and

determining whether said particular address'"'"' location in said electronic map is in said cost zone.

26. A method for implementing a cost zone using an electronic map, comprising the steps of:

storing an indication of an origin;

storing an indication of a predetermined cost;

storing costs for traversing said electronic map from said origin to a set of locations in said electronic map; and

determining a subset of said set of locations in said electronic map that are approximately a predetermined cost from said origin, said subset of said set of locations defining a boundary of said cost zone.

27. A method according to claim 26, further including the step of:

receiving an indication of a type of cost to be minimized.

28. A method according to claim 26, further including the step of:

storing said subset of said set of locations in a data structure.

29. A method according to claim 26, further including the step of:

receiving said indication of said origin.

30. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method comprising the steps of:

storing an indication of an origin;

storing an indication of a predetermined cost;

storing costs for traversing said electronic map from said origin to a set of locations in said electronic map; and

determining a subset of said set of locations in said electronic map that are approximately a predetermined cost from said origin, said subset of said set of locations defining a boundary of said cost zone.