System and method for abstracting and visualizing a route map

• US 20050182604A1
• Filed: 12/06/2004
• Published: 08/18/2005
• Est. Priority Date: 03/17/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Stolte, Chris, Agrawala, Maneesh
• Granted Patent: US 7,496,484 B2
• Time in Patent Office: Days
• 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 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, each said element including sufficient 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 total height and a total width of a rendering of each element in said scaled set of elements;

selecting, based on a function of said total height and said total width, an image component; and

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

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

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

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

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

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

4. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a map module for preparing a route map that describes a path between a start and an end, the map module comprising;

instructions for obtaining said path from said start to said end, the path comprising an initial set of elements, each said element including sufficient 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 total height and a total width of a rendering of each element in said scaled set of elements;

instructions for selecting, based on a function of said total height and said total width, an image component; and

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

5. The computer program product of claim 4, wherein, said instructions for selecting further include:

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

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

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

6. The computer program product of claim 4, wherein said image component 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 program module, executable by said central processing unit, said program module comprising;

a map module for preparing said route map, the route map describing a path between a start and an end, the map module comprising;

instructions for obtaining said path from said start to said end, the path comprising an initial set of elements, each said element including sufficient 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 total height and a total width of a rendering of each element in said scaled set of elements;

instructions for selecting, based on a function of said total height and said total width, an image component; and

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

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

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

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

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

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