Polar coordinate-based isochrone generation

• US 20030074132A1
• Filed: 10/11/2001
• Published: 04/17/2003
• Est. Priority Date: 10/11/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sutanto, Herry
• Granted Patent: US 6,668,226 B2
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B

Abstract

The present invention utilizes a novel polar coordinate grid to improve the processes of calculating and generating isochrones. Isochrones are lines on a map connecting places of equal travel time from a particular departure point. Calculating accurate isochrones is time consuming especially for large maps, because of the large number of data points to be processed. Data sampling is used to expedite the generation of isochrones, while maintaining acceptable accuracy. The present invention uses polar coordinate grid sampling for data sampling. Advantageously, polar coordinate grids have higher granularity at the center of a mapped region and lower granularity in regions farther away from the center in radial direction. Polar coordinate sampling reduces the amount of memory used and decreases the isochrone calculation time without perceptible degradation in isochrone accuracy.

Claims

1. A method for generating an isochrone in a mapped region having a departure point and a predetermined travel time, the method comprising the steps of:

associating a travel time with each of a plurality of routing nodes in the mapped region;

creating at least one travel time data point corresponding to a polar grid cell in which at least one of the plurality of routing nodes resides;

drawing a line between a first travel time data point and a second travel time data point, wherein the first travel time data point can be reached from the departure point within the predetermined travel time and the second travel time data point cannot be reached from the departure point within the predetermined travel time.

2. The method of claim 1, wherein the routing node is a street intersection.

3. The method of claim 1, further comprising the step of storing the travel time associated with each of the plurality of routing nodes in the mapped region.

4. The method of claim 3, further comprising the step of storing the travel time data point associated with the polar grid cell.

5. The method of claim 4, wherein the step of storing the travel time data point further comprises the step of replacing the stored travel time with the travel time data point.

6. The method of claim 1, wherein the step of drawing the line comprises the steps of creating a Voronoi diagram to separate the first travel time data point and the second travel time data point.

7. The method of claim 1, wherein the polar grid cell is one of a plurality of polar grid cells having the departure point as an origin.

8. The method of claim 7, wherein the polar grid cells have different dimensions along a radial axis (r axis).

9. The method of claim 1, wherein the travel time data point represents the highest travel time associated with the at least one routing node residing in the polar grid cell.

10. A method for generating an isochrone in a mapped region having a departure point and a predetermined travel time, the method comprising the steps of:

associating a travel time with each of a plurality of intersections in the mapped region;

overlaying a polar coordinate grid on the mapped region, the polar coordinate grid comprising a plurality of polar grid cells;

creating a plurality of travel time data points, each travel time data point corresponding to one of the plurality of polar grid cells in which at least one of the plurality of intersections resides;

drawing a line between a first group of travel time data points and a second group of travel time data points, wherein the first group of travel time data points can be reached from the departure point within the predetermined travel time and the second group of travel time data points cannot be reached from the departure point within the predetermined travel time.

11. The method of claim 10, wherein the step of drawing the line comprises the step of creating a Voronoi diagram to separate the first group of travel time data points and the second group of travel time data points.

12. The method of claim 10, further comprising the step of storing the travel time associated with each of the plurality of intersections in the mapped region.

13. The method of claim 12, further comprising the step of storing the travel time data point corresponding to one of the plurality of polar grid cells.

14. The method of claim 13, wherein the step of storing the travel time data point further comprises the step of replacing the stored travel time with the travel time data point.

15. A system for generating an isochrone for a mapped region having a departure point and a predetermined travel time, comprising:

a mapping module operative to retrieve map data, to associate a travel time with each of a plurality of routing nodes in the mapped region, and to create at least one travel time data point corresponding to a polar grid cell in which at least one of the plurality of routing nodes resides;

a rendering module operative to draw a line between a first travel time data point and a second travel time data point, wherein the first travel time data point can be reached from the departure point within the predetermined travel time and the second travel time data point cannot be reached from the departure point within the predetermined travel time.

16. The system of claim 15, wherein the map data is retrieved from a map data module.

17. The system of claim 15, wherein the map data is retrieved from a second program module in the form of an instruction.

18. The system of claim 15, wherein the routing node is a street intersection.

19. The system of claim 15, wherein the line is drawn according to a Voronoi diagram process.

20. The system of claim 15, wherein the polar grid cell is one of a plurality of polar grid cells having the departure point as an origin.

21. The system of claim 20, wherein the polar grid cells have different dimensions along a radial axis (r axis).

22. The system of claim 21, wherein a first polar grid cell is located closer to the origin than a second polar grid cell and wherein the r axis dimension of the first polar grid cell is shorter than the r axis dimension of the second polar grid cell.

23. The system of claim 15, wherein the travel time data point represents the highest travel time associated with the at least one routing node residing in the polar grid cell.

24. The system of claim 23, wherein the travel time associated with each of the plurality of routing nodes in the mapped region, is stored in a memory module in association with a location of each of the plurality of routing nodes.

25. The system of claim 24, wherein the time associated with each of the plurality of routing nodes in the mapped region is replaced in the memory module by the travel time data point.

26. The system of claim 15, wherein the travel time data point represents the average travel time associated with the at least one routing node residing in the polar grid cell.

27. The system of claim 26, wherein the travel time associated with each of the plurality of routing nodes in the mapped region, is stored in a memory module in association with a location of each of the plurality of routing nodes.

28. The system of claim 27, wherein the time associated with each of the plurality of routing nodes in the mapped region is replaced in the memory module by the travel time data point.