System and method for placing labels on a computer-generated map
AssigneeMicrosoft Corporation
InventorsJohn-Michael Wiley, Martin John Sedluk
Life of this patent
Estimating the term…
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.
Claims18
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.
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.
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.
Dependencies are inferred from the claim text.