System and method for abstracting and visualizing a route map

• US 20050182605A1
• 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,542,882 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 positioning a plurality of labels in a route map, the method comprising, for each label in said plurality of labels:

associating a plurality of constraint definitions with said label;

each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style;

selecting an initial constraint definition from said plurality of constraint definitions;

positioning a center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; and

the method further comprising;

choosing a label in said plurality of labels;

determining a first score (S₁) using a target function;

wherein the score is determined by a position of said chosen label in said route map;

applying a different constraint definition, from the plurality of constraint definitions associated with said selected label;

said applying step including the step of repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition;

calculating a second score (S₂) using said target function;

wherein the score is determined by the repositioned label position;

accepting the new position for said label in accordance with a function that is determined by a comparison of S₁ and S₂;

repeating said choosing, determining, applying, calculating, and accepting steps until a first occurrence of an exit condition.

2. The method of claim 1 wherein said function comprises accepting the repositioned label position:

(1) when S₂ is less than S₁; and

(2) with the probability P(Δ

S), when S₂ is greater than S₁, where P(Δ

S) is a probability function that is dependent upon an effective temperature t that is reduced by an amount after each execution of said repeating step.

3. The method of claim 1 where:

P(Δ

S)=exp<sup>−

[(Δ

S)/(k*t)]</sup>

Δ

S=(S₁)-(S₂), and k is a constant.

4. The method of claim 1, wherein said positioning step further comprises fixing a label in said plurality of labels in said route map when said label does not intersect with any other label in said route map;

and said choosing step does not choose a label that has been fixed.

5. The method of claim 1, wherein each constraint definition in said plurality of constraint definitions includes a scoring strategy that is used by said target function in said determining and calculating steps.

6. The method of claim 1, wherein each said layout style is selected from the group consisting of a simple layout style, a combination of an arrow image with the primary name for a street or highway, a combination of a primary name for a street or highway with a mileage along the road, a highway number as text stacked on top of a shield image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.

7. 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 label placement module for positioning a plurality of labels in a route map, the label placement module comprising, for each label in said plurality of labels;

instructions for associating a plurality of constraint definitions with said label;

each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style;

instructions for selecting an initial constraint definition from said plurality of constraint definitions;

instructions for positioning a center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; and

the module further including;

instructions for choosing a label in said plurality of labels;

instructions for determining a first score (S₁) using a target function;

wherein the score is determined by a position of said chosen label in said route map;

instructions for applying a different constraint definition, from the plurality of constraint definitions associated with said selected label;

said instructions for applying including instructions for repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition;

instructions for calculating a second score (S₂) using said target function;

wherein the score is determined by the repositioned label position;

instructions for accepting the new position for said label in accordance with a function that is determined by a comparison of S₁ and S₂;

instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition.

8. The computer program product of claim 7 wherein said function comprises instructions for accepting the repositioned label position:

(1) when S₂ is less than S₁; and

(2) with the probability P(Δ

S), when S₂ is greater than S₁, where P(Δ

S) is a probability function that is dependent upon an effective temperature t that is reduced by an amount after each execution of said repeating step.

9. The computer program product of claim 7 where:

P(Δ

S)=exp<sup>−

[(Δ

S)/(k*t)]</sup>

Δ

S=(S₁)-(S₂), and k is a constant.

10. The computer program product of claim 7, wherein said instructions for positioning further comprises instructions fixing a label in said plurality of labels in said route map when said label does not intersect with any other label in said route map;

and said instructions for choosing includes instructions for not choosing a label that has been fixed.

11. The computer program product of claim 7, wherein each constraint definition in said plurality of constraint definitions includes a scoring strategy that is used by said target function coded by said instructions for determining and calculating.

12. The computer program product of claim 7, wherein each said layout style is selected from the group consisting of a simple layout style, a combination of an arrow image with the primary name for a street or highway, a combination of a primary name for a street or highway with a mileage along the road, a highway number as text stacked on top of shield image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.

13. A computer system for positioning a plurality of labels in 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 label refinement module for refining the plurality of labels in a route map, the label refinement module comprising, for each label in said plurality of labels;

instructions for associating a plurality of constraint definitions with said label;

each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style;

instructions for selecting an initial constraint definition from said plurality of constraint definitions;

instructions for positioning a center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; and

the label refinement module further including;

instructions for choosing a label in said plurality of labels;

instructions for determining a first score (S₁) using a target function;

wherein the score is determined by a position of said chosen label in said route map;

instructions for applying a different constraint definition, from the plurality of constraint definitions associated with said selected label;

said instructions for applying including instructions for repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition;

instructions for calculating a second score (S₂) using said target function;

wherein the score is determined by the repositioned label position;

instructions for accepting the new position for said label in accordance with a function that is determined by a comparison of S₁ and S₂;

instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition.

14. The computer system of claim 13 wherein said function comprises instructions for accepting the repositioned label position:

(1) when S₂ is less than S₁; and

(2) with the probability P(Δ

S), when S₂ is greater than S₁, where P(Δ

S) is a probability function that is dependent upon an effective temperature t that is reduced by an amount after each execution of said repeating step.

15. The computer system of claim 13 where:

P(Δ

S)=exp<sup>−

[(Δ

S)—

/(k*t)]</sup>

Δ

S=(S₁)-(S₂), and k is a constant.

16. The computer system of claim 13, wherein said instructions for positioning further comprises instructions fixing a label in said plurality of labels in said route map when said label does not intersect with any other label in said route map;

and said instructions for choosing includes instructions for not choosing a label that has been fixed.

17. The computer system of claim 13, wherein each constraint definition in said plurality of constraint definitions includes a scoring strategy that is used by said target function coded by said instructions for determining and calculating.

18. The computer system of claim 13, wherein each said layout style is selected from the group consisting of a simple layout style, a combination of an arrow image with the primary name for a street or highway, a combination of a primary name for a street or highway with a mileage along the road, a highway number as text stacked on top of a shield image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.