System and method for abstracting and visualizing a route map

• US 7,496,484 B2
• Filed: 12/06/2004
• Issued: 02/24/2009
• Est. Priority Date: 03/17/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Stolte, Chris, Agrawala, Maneesh
• Primary Examiner(s): Shah; Kamini
• Assistant Examiner(s): Luu; Cuong V
• Application Number:
  US11/005,862
• Publication Number:
  US 20050182604A1
• Time in Patent Office: 1,541 Days
• Field of Search: 701/213, 701/209, 701/208, 340/995.22, 340/995.14, 707/3, 342/357.09
• US Class Current: 703/2
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G01C 21/3673 Labelling using text of road map data items, e.g. road names, POI names
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

A system and method for making computer-generated maps includes a different scale factor for each road in a route. The scale factors are used to optimize the route map against a target function that considers factors such as the number of false intersections in the route and the number of roads falling below a minimum length threshold. A refinement technique such as simulated annealing is used to find a solution to the target function. Each road in the scaled map is rendered to provide a finished product having the appearance of a hand-drawn map. The finished product includes context roads that intersect the main route but are not part of the main route. Furthermore, the hand-drawn map is optimized to the characteristics of the viewport used to visualize the map.

Claims

1. A computer-implemented method of preparing a route map that describes a path between a start and an end, said method comprising:

obtaining said path from said start to said end, said path comprising an initial set of elements wherein each said element comprises a portion of said path, each said element including information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

estimating a ratio of a total width to a total height of the route map that includes a rendering of each element in said scaled set of elements;

selecting, based on a function of said ratio of said total width to said total height, an image template from a plurality of image templates, wherein the plurality of image templates comprise different image template sizes to accommodate route maps of different sizes; and

outputting a rendering of each element in said scaled set of elements to said image template.

2. The method of claim 1, wherein, in said selecting step:

when said ratio of said total width to said total height is less than 0.60, a first image template is selected;

when said ratio of said total width to said total height is greater than 2.0, a second image template is selected; and

when said first image and said second image template is not selected, a third image template is selected.

3. The method of claim 1, wherein said image template is selected based on said function as well as a number of elements in said scaled set of elements.

4. A computer readable storage medium encoding computer readable instructions executable by a processor for preparing a route map that describes a path between a start and an end, the computer-readable instructions comprising:

instructions for obtaining said path from said start to said end, the path comprising an initial set of elements wherein each said element comprises a portion of said path, each said element including information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

instructions for independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

instructions for estimating a ratio of a total width to a total height of the route map that includes a rendering of each element in said scaled set of elements;

instructions for selecting, based on a function of said ratio of said total width and said total height, an image template from a plurality of image templates, wherein the plurality of image templates comprise different image template sizes to accommodate route maps of different sizes; and

instructions for outputting a rendering of each element in said scaled set of elements to said image template.

5. The computer readable storage medium of claim 4, wherein, said instructions for selecting further include:

instructions for selecting a first image template when said ratio of said total width to said total height is less than 0.60;

instructions for selecting a second image when said ratio of said total width to said total height is greater than 2.0; and

instructions for selecting a third image template when said first image and said second image template is not selected.

6. The computer readable storage medium of claim 4, wherein said image template is selected based on said function as well as a number of elements in said scaled set of elements.

7. A computer system for preparing a route map, the computer system comprising:

a central processing unit;

a memory, coupled to said central processing unit;

a viewport for displaying said route map;

a map module stored in the memory comprising instructions, executable by said central processing unit, for preparing said route map, the route map describing a path between a start and an end, the map module further comprising;

instructions for obtaining said path from said start to said end, the path comprising an initial set of elements wherein each said element comprises a portion of said path, each said element including information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

instructions for independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

instructions for estimating a ratio of a total width to a total height of the route map that includes a rendering of each element in said scaled set of elements;

instructions for selecting an image template from a plurality of image templates, the plurality of image templates comprise different image template sizes to accommodate route maps of different sizes, wherein the image template is selected based on a function of said ratio of said total width to said total height; and

instructions for outputting a rendering of each element in said scaled set of elements to said image template.

8. The computer system of claim 7, wherein, said instructions for selecting further include:

instructions for selecting a first image template when said ratio of said total width to said total height is less than 0.60;

instructions for selecting a second image template when said ratio of said total width to said total height is greater than 2.0; and

instructions for selecting a third image template when said first image and said second image template is not selected.

9. The computer system of claim 7, wherein said image template is selected based on said function as well as a number of elements in said scaled set of elements.