System and method for placing labels on a computer-generated map

• US 6,724,392 B1
• Filed: 03/02/1999
• Issued: 04/20/2004
• Est. Priority Date: 03/02/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sedluk, Martin John, Wiley, John-Michael
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): Sajous, Wesner
• Application Number:
  US09/260,774
• Time in Patent Office: 1,876 Days
• Field of Search: 345/130, 345/117, 345/118, 345/436, 345/438, 345/326, 345/581, 345/584, 345/586, 345/587, 345/588, 345/648, 345/630, 345/677, 345/641, 345/632, 345/638, 382/276, 382/293, 382/298, 701/116, 701/200, 701/2.1, 715/512, 703/2
• US Class Current: 345/581
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

A system and method for selecting a cartographically-preferred label position from a plurality of potential label positions for a feature on a computer-generated map. The mechanism analyzes each pixel within each potential label position to determine the presence of a colliding label or a colliding feature, and calculates a total penalty for each potential label position. Then, based on the several total penalties, the mechanism determines which of the potential label positions is the cartographically-preferable label position and places the label in that label position.

Claims

1. A computer-readable medium having computer-executable instructions for determining a preferred label position from a plurality of label positions, which when executed perform steps comprising:

(a) associating a characteristic of a pixel with a feature class, the feature class being associated with features to be displayed on a computer-generated map;

(b) analyzing each label position within the plurality of label positions to determine a number of pixels within each label position which bear the characteristic; and

(c) calculating a penalty for each label position of the plurality of label positions based on a percentage of pixels within each label position which bear the characteristic,

(d) collaring each of the label positions in the plurality of label positions to determine a preferred label position, the preferred label having a lowest penalty; and

(e) placing a label in the preferred label position, wherein some overlap may occur between the label and a feature in the preferred label position.

2. The computer-readable medium of claim 1, wherein the characteristic is color.

3. The computer-readable medium of claim 1, wherein the step of calculating the penalty further comprises:

determining if the number of pixels which bear the characteristic exceeds a preconfigured percentage of a total number of pixels within each label position.

4. The computer-readable medium of claim 1, wherein the step of analyzing each label position further comprises:

counting the number of pixels within each label position which bear the characteristic; and

counting a second number of pixels within each label position which bear a second characteristic, the second characteristic being associated with a second feature class.

5. The computer-readable medium of claim 4, wherein the step of calculating the penalty for each label position further comprises:

calculating a first penalty associated with the number of pixels within each label position which bear the characteristic;

calculating a second penalty associated with the second number of pixels within each label position which bear the second characteristic; and

combining the first penalty and the second penalty for a total penalty associated with each label position.

6. The computer-readable medium of claim 5, wherein the step of calculating the first penalty further comprises:

determining if the number of pixels which bear the characteristic exceeds a preconfigured percentage of a total number of pixels within each label position; and

wherein the step of calculating the second penalty further comprises;

determining if the second number of pixels which bear the second characteristic exceeds a second preconfigured percentage of a total number of pixels within each label position.

7. The computer-readable medium of claim 1, wherein the step of calculating the penalty further comprises:

multiplying the number of pixels within each label position which bear the characteristic by a first per-pixel penalty associated with the feature class; and

wherein the step of calculating the second penalty further 5 comprises;

multiplying the number of pixels within each label position which bear the characteristic by a first per-pixel penalty associated with the feature class.

8. The computer-readable medium of claim 5, wherein the step of calculating the first penalty flier comprises:

multiplying the number of pixels within each label position which bear the characteristic by a per-pixel penalty

associated with the feature class; and

wherein the step of calculating the second penalty further comprises;

multiplying the number of pixels within each label position which bear the second characteristic by a second per-pixel penalty associated with a second feature class.

9. In a computer system, a computer-implemented method for selecting a preferred label position from a plurality of potential label positions for display on a computer-generated map, comprising the steps of:

(a) associating a display color with a feature class, a penalty being associated with the feature class;

(b) determining a pixel color displayed by a pixel within a first label position within the plurality of potential label positions;

(c) in response to the pixel color matching the display color associated with the feature class, counting the pixel toward a penalty for the first label position, wherein counting the pixel towards a penalty comprises associating the penalty with the pixel;

(d) repeating steps (b) and (c) for each pixel within the first label position to calculate a total penalty for the first label position; and

(e) repeating steps (b), (c), and (d) for each potential label position in the plurality of label positions to determine a preferred label position, the preferred label position having a lowest calculated total penalty.

10. The computer-implemented method of claim 9, further comprising the step of:

displaying a label in the preferred label position, the label being associated with a feature displayed on the computer-generated map.

11. The computer-implemented method of claim 9, wherein the step of counting the pixel toward a penalty further comprises:

incrementing a counter associated with the feature class, the counter being operative to tabulate a number of pixels within the first label position which display the display color.

12. The computer-implemented method of claim 11, wherein a penalty is associated with the feature class, and the step of repeating steps (b) and (c) further comprises associating the penalty with the 5 number of pixels within the first label position which display the display color.

13. The computer-implemented method of claim 9, wherein the feature class comprises a plurality of types of features which may be displayed on a computer-generated map, and the feature class.

14. A computer-readable medium having computer-executable instructions for determining a preferred label position from a plurality of label positions, which when executed perform steps comprising:

(a) associating a display color with a first feature class;

(b) associating a penalty with the first feature class;

(c) examining each pixel in a plurality of pixels within a first label position in the plurality of label positions to determine a pixel color for each pixel;

(d) determining a number of pixels in the plurality of pixels for which the pixel color is the display color;

(e) based on the number of pixels in the plurality of pixels for which the pixel color is the display color, assigning a total penalty to the first label position;

(f) repeating steps (c) through (e) for each of the label positions in the plurality of label positions; and

(g) picking one label position from step (f) as the preferred label position, the one label position having the lowest total penalty.

15. The computer-readable medium of claim 14, wherein the step of determining the number of pixels in the plurality of pixels further comprises:

determining a second number of pixels within the 25 plurality of pixels for which the pixel color is a second display color, the second display color being associated with a second feature class.

16. The computer-readable medium of claim 15, wherein the step of assigning the total penalty to the first label position further comprises:

calculating a first penalty associated with the number of 5 pixels within the first label position for which the pixels color is the display color; and

calculating a second penalty associated with the second number of pixels within the first label position for which the pixel color is the second display color; and

combining the first penalty and the second penalty for a total penalty associated with the first label position.

17. The computer-readable medium of claim 16, wherein the step of calculating the first penalty further comprises:

determining if the number of pixels for which the pixel color is the display color exceeds a preconfigured percentage of a total number of pixels within the first label position; and

wherein the step of calculating the second penalty further comprises;

determining if the second number of pixels for which the pixel color is the second display color exceeds a second preconfigured percentage of a total number of pixels within the first label position.

18. The computer-readable medium of claim 14, further comprising computer-executable steps for displaying a label in the preferred label position.