System and method for optimally placing labels on a map

• US 6,154,219 A
• Filed: 12/01/1997
• Issued: 11/28/2000
• Est. Priority Date: 12/01/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Atherton, Mark B., Wiley, John-Michael
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): Lee, Albert K.
• Application Number:
  US08/980,846
• Time in Patent Office: 1,093 Days
• Field of Search: 345/433, 345/435, 345/342, 345/344, 364/400
• US Class Current: 345/587
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G09B 29/007 using computer methods

Abstract

Labeling objects on a computerized map in an efficient manner while avoiding collisions with both more and less important objects. A first list contains objects to be labeled on the computerized map, the objects being both points and non-points. Each of the objects in the first list has a label selection priority. A second list contains the a collection of objects from the first list having the lowest label selection priority. The system can draw each object in the first list to the computerized map in ascending order of label selection priority. As each object is drawn, the system labels the object with a label while avoiding collisions between the label and objects in the second list having a higher label selection priority than the object.

Claims

1. A method for drawing map features and associated labels to be displayed on a map, comprising the steps of:

compiling a list of map features to be potentially displayed on a map, the map features comprising point features and non-point features, each feature comprising an associated label positionable in a plurality of potential label positions;

assigning a label selection priority to each feature in the list;

ordering the features in the list in priority order;

drawing the non-point features in the list to a representation of the map; and

selecting point features, labels associated with the point features, and labels associated with the non-point features for drawing to the representation of the map by;

a. retrieving a selected feature from the list in priority order;

b. if the label associated with the selected feature can be placed in one or more of the potential label locations for the selected feature without causing a collision with any of the features or associated labels having a higher priority, drawing the label for the selected feature to the representation of the map in one of those locations and, if the feature is a point feature, also drawing the feature to the representation of the map;

c. if the label associated with the selected feature cannot be placed in one of the potential label locations for the feature without causing a collision with any of the features or associated labels having a higher priority, deleting the selected feature from the first list;

d. if the label has been drawn for the selected feature, determining whether there is a collision between the label and one or more point features having a lower priority and, if so, removing the features involved in the collision having the lower priorities from the list; and

e. repeating steps a-d until labels for all of the features remaining in the list have been drawn.

2. The method of claim 1, wherein the list is a first list, further comprising the steps of:

compiling a second list comprising selected point features from the first list;

creating a weighted collision array for the features of the second list including a penalty for each feature in the second list; and

if there are multiple potential label positions for the selected feature that do not collide with features or labels having a higher priority, determining whether there are collisions between multiple available potential label positions and features having lower priorities, and if so,

for each of the available potential label positions, determining a penalty for the label position by identifying one or more features in collision with the label position, obtaining the penalties for the features in collision from the weighted collision array, and those penalties to the label position, and

drawing the label for the selected feature in the position having the lowest assigned penalty.

3. The method of claim 2, wherein step (d) further comprises the step of deleting the selected feature from the second list.

4. The method of claim 2, wherein the selected feature is a point feature, further comprising the step of deleting the selected feature from the first list if the selected feature cannot be placed in one of the potential label locations for the feature without causing a collision with any of the features or associated labels having a higher priority.

5. The method of claim 3, wherein step (d) further comprises the steps of:

creating a second representation of the map,

mapping all of the features from the second list to the second representation of the map,

determining whether there is a collision between the label and one or more point features having a lower priority with reference to the second representation of the map; and

the step of determining whether there are collisions between multiple available potential label positions and features having lower priorities comprises the step of referring to the second representation of the map.

6. The method of claim 1, wherein step (b) further comprises the steps of:

assigning cartographic penalties to potential label locations for the selected feature; and

selecting the location for drawing the label for the selected feature by selecting one of the label locations with the lowest cartographic penalty.

7. The method of claim 1 wherein the non-point features include area features and line features.

8. The method of claim 2 wherein, for each feature in the second list, the weighted collision array includes:

one or more potential label locations for the feature;

an initial label location for the feature;

a collision rectangle associated with each potential label location for the feature;

a cartographic penalty associated with each potential label location determined by the degree of deviation between its associated collision rectangle and the collision rectangle for the initial location; and

a collision penalty associated each potential label location determined by the degree of overlap between its associated collision rectangle and collision rectangles associated with other features.

9. The method of claim 3, wherein the steps for defining the collision rectangle include:

defining initial dimensions for a rectangular region concentric around the feature;

determining the priority assigned to the feature;

evaluating a density for the map;

increasing the size of the rectangular region in response to a relatively high priority assigned to the feature; and

decreasing the size of the rectangular region in response to a relatively high density for the map.

10. The method of claim 8, wherein the step for determining the label location using the weighted collision array further comprises the steps of:

comparing the penalty of the initial location with the penalty of other potential label locations and choosing the label location associated with a lowest penalty.

12. The method of claim 1, further comprising the step of storing the representation of the map in a computer memory.

14. The method of claim 1, further comprising the step of displaying the representation of the map on a display device.

16. The method of claim 1, further comprising the step of printing the representation of the map.

17. A computer storage medium storing computer executable instructions for performing the method of claim 1.

19. A computer-controlled device operable for performing the method of claim 1.

11. A method for drawing map features and associated labels to be displayed on a map, comprising the steps of:

compiling a first list of map features to be potentially displayed on a map, the map features comprising point features and non-point features, each feature comprising an associated label positionable in a plurality of potential label positions;

assigning a label selection priority to each feature in the first list;

ordering the features in the first list in priority order;

compiling a second list comprising selected point features from the first list;

creating a weighted collision array for the features of the second list including a penalty for each feature in the second list, and if there are multiple potential label positions for the selected feature, determining whether there are collisions, and

for each of the available potential label positions, determining a penalty for the label position by identifying one or more features in collision with the label position, obtaining the penalties for the features in collision from the weighted collision array, and those penalties to the label position, and

drawing the non-point features in the list to a representation of the map; and

selecting point features, labels associated with the point features, and labels associated with the non-point features for drawing to the representation of the map by;

a. retrieving a selected feature from the first list in priority order;

b. if there are multiple potential label positions for the selected feature that do not collide with features or labels having a higher priority, determining whether there are collisions between multiple available potential label positions and features having lower priorities, and if so,

c. if the label associated with the selected feature cannot be placed in one of the potential label locations for the feature without causing a collision with any of the features or associated labels having a higher priority, deleting the selected feature from the first and second lists;

d. if the label has been drawn for the selected feature, determining whether there is a collision between the label and one or more point features having a lower priority and, if so, removing the features involved in the collision having the lower priorities from the first and second lists; and

e. repeating steps a-d until labels for all of the features remaining in the list have been drawn.

13. The method of claim 11, further comprising the step of storing the representation of the map in a computer memory.

15. The method of claim 11, further comprising the step of displaying the representation of the map on a display device.

18. A computer storage medium storing computer executable instructions for performing the method of claim 11.

20. A computer-controlled device operable for performing the method of claim 11.