System and method for abstracting and visualizing a route map

• US 7,542,882 B2
• Filed: 12/06/2004
• Issued: 06/02/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 S
• Assistant Examiner(s): Luu; Cuong V
• Application Number:
  US11/005,952
• Publication Number:
  US 20050182605A1
• Time in Patent Office: 1,639 Days
• Field of Search: 715/762, 701/201, 701/14, 701/3, 348/113, 702/150
• 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, executed by a computing device for positioning a plurality of labels in a route map, the computer implemented method comprising, for each label in said plurality of labels:

associating by the computing device, 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, and wherein said plurality of constraint definitions constitute a continuous range of positions, and wherein a center of said label within each unique bounding box is located at a different point for each of the constraint definitions in the continuous range of positions, and wherein the plurality of constraint definitions are not limited by placement on the map to relation to a road;

selecting, by the computing device, an initial constraint definition from said plurality of constraint definitions;

positioning, by the computing device, the 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;

the computer implemented method further comprising;

choosing, by the computing device, a label in said plurality of labels;

determining, by the computing device, 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, by the computing device, 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, by the computing device, a second score (S₂) using said target function, wherein the score is determined by the repositioned label position;

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

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

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

(1) when S₂ is less than S_1;

(2) with a 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 computer implemented method of claim 2 where:

P(Δ

S)=exp<sup>−

[(Δ

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

Δ

S=(S₁)−

(S₂), and k is a constant.

4. The computer implemented 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 computer implemented 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 computer implemented 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 one of a street and a highway, a combination of a primary name for one of a street and a highway with a mileage along the road, a highway number as text stacked on top of a shielding image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.

19. The method of claim 1, further comprising extending the road when a length of the label exceeds the length of the road, wherein the road is extended by an amount equal to the length at which the length of the label exceeds the length of the road.

20. The method of claim 1, wherein the score determined by the target function includes a determination of at least one of:

a number of roads each label intersects, a number of labels each label intersects, a distance the label is from a center of the road associated with the label, whether the label is above the road, and whether the label is below the road.

7. A computer storage medium containing computer executable instructions that when executed by a computing device provide:

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, wherein said plurality of constraint definition constitute a continuous range of positions, wherein a center of said label within each unique bounding box is located at a different point for each of the constraint definitions in the continuous range of positions, and wherein the plurality of constraint definitions are not limited by placement on the map in relation to a road;

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;

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₂; and

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

8. The computer storage medium 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 storage medium of claim 8 where:

P(Δ

S)=exp<sup>−

[(Δ

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

Δ

S=(S₁)−

(S₂), and k is a constant.

10. The computer storage medium 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 choosing step does not choose a label that has been fixed.

11. The computer storage medium 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 steps.

12. The computer storage medium 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 one of a street and a highway, a combination of a primary name for one of a street and a highway with a mileage along the road, a highway number as text stacked on top of shielding 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, and wherein said plurality of constraint definitions constitute a continuous range of positions, wherein a center of said label within each unique bounding box is located at a different point for each of the constraint definitions in the continuous range of positions, and wherein the plurality of constraint definitions are not limited by placement on the map in relation to a road;

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

instructions for positioning the 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;

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₂; and

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 14 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 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 one of a street and a highway, a combination of a primary name for one of a street and a highway with a mileage along the road, a highway number as text stacked on top of a shielding image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.