Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-10-11
2003-12-23
Chin, Gary (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S202000, C701S209000, C340S995100, C340S995190
Reexamination Certificate
active
06668226
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the generation of isochrones and more specifically relates to the improvement of isochrone generation by using polar coordinate-based sampling.
BACKGROUND OF THE INVENTION
Isochrones are lines on a map connecting places of equal travel time from a particular departure point. Isochrones are used by would-be travelers who want to determine what destinations are reachable from a departure point within a predetermined travel time. The calculation and generation of an isochrone can require the consideration and analysis of large amounts of data. While an isochrone can be generated by hand, more recently, isochrone generation has been automated and computerized. Computers are now commonly used to generate isochrones, because of the calculating power of modern computers and the recent availability of mapping data.
Conventional computerized methods of isochrone generation are time consuming especially for large maps, because of the large number of data points to be processed. One way of simplifying the isochrone generation process is to reduce the number of data points to consider for a given map. For example, for a drive time isochrone, only travel times to street intersections (i.e., routing nodes) are calculated, rather than every single point along an entire street. After travel times are associated with all of the intersections in a mapped region, the isochrone is then generated by creating a Voronoi diagram of those points. That is, an isochrone is created that includes all intersections reachable within the drive time and that excludes all intersections not reachable within the drive time. In a mapped region having a high road density (e.g., a city center), the number of intersections can significantly slow isochrone generation.
Creating a Voronoi diagram is an expensive process (i.e., consumptive of system resources), especially if the number of intersections (i.e., data points) is large. To expedite isochrone generation, the number of data points needs to be reduced, hopefully without affecting the shape of the boundary. One way to do this is to employ grid-based data sampling of the data points before Voronoi diagram is calculated.
Data sampling is used to increase the speed the generation of isochrones by reducing the number of points on a map that must be considered when determining the location of the isochrone. A uniform size rectangular grid can be used to sample the points. Thus, multiple data points inside a grid cell are replaced with one point at its center. Conventional isochrone generation methods use a Cartesian coordinate grid sampling. In such methods, a rectangular grid is laid over the mapped region and the isochrone is drawn to separate cells in the grid. While Cartesian-based grid sampling has made computerized isochrone generation more efficient, isochrone generation can still be highly consumptive of a computer's processor and memory resources.
Another approach to expediting isochrone generation involves adjusting the grid's cell size, based on the area of the requested isochrone. Typically, the larger the isochrone, the larger the grid cell size. However, a larger grid cell size reduces the accuracy (i.e., lowers the granularity) of the isochrone boundary. This is often acceptable because larger isochrones (i.e., longer drive time) can generally tolerate more error (i.e., the drive time for a longer distance is inherently less accurate).
However, this approach to expediting isochrone generation has some drawbacks: 1) the size of the overall mapped region must be determined before setting the grid size, and 2) the sampling done for a large isochrone cannot be used for calculating a smaller isochrone (i.e., the sampling must be re-created for every different size of isochrone).
Therefore, there is a need in the art for an isochrone generation system and method that utilizes a polar coordinate grid for data sampling to make isochrone generation faster and more efficient. The isochrone generation system and method also should reduce the amount of memory needed to perform isochrone generation by reducing the required number of data points for storage during the isochrone generation process.
SUMMARY OF THE INVENTION
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 speed the generation of isochrones, while maintaining acceptable accuracy. The present invention uses polar coordinate grid sampling for data sampling. Conventional Cartesian coordinate grid sampling processes use uniform rectangular grids. 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.
In one aspect of the invention, a method is provided for generating an isochrone in a mapped region, where the mapped region has a departure point and a predetermined travel time. A travel time is associated with each of a plurality of routing nodes in the mapped region. At least one travel time data point is created, where the travel time data point corresponds to a polar grid cell in which at least one of the plurality of routing nodes resides. A line is drawn between a first travel time data point and a second travel time data point, where the first travel time data point can be reached from the departure point within the predetermined travel time and where the second travel time data point cannot be reached from the departure point within the predetermined travel time.
In another aspect of the invention, a system is provided for generating an isochrone for a mapped region having a departure point and a predetermined travel time. The system has 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. The system also has a rendering module operative to draw a line between a first travel time data point and a second travel time data point, where 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.
The various aspects of the present invention may be more clearly understood and appreciated from a review of the following detailed description of the disclosed embodiments and by reference to the drawings and claims.
REFERENCES:
patent: 4745550 (1988-05-01), Witkin et al.
patent: 6401031 (2002-06-01), Ogawa
patent: 6424910 (2002-07-01), Ohler et al.
patent: 6587785 (2003-07-01), Jijina et al.
patent: 2003/0014286 (2003-01-01), Cappellini
Chin Gary
King & Spalding LLP
Petty W. Scott
LandOfFree
Polar coordinate-based isochrone generation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Polar coordinate-based isochrone generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polar coordinate-based isochrone generation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3172915