Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1999-03-02
2004-04-20
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S587000
Reexamination Certificate
active
06724392
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to computer software application programs for placing labels on computer generated maps. More particularly, the present invention relates to a mapping program or software module for using display properties of various feature classes to assist in locating a cartographically-preferable label position for a feature on a computer generated map.
BACKGROUND OF THE INVENTION
Computer mapping products are achieving widespread acceptance. To make a computer mapping product usable, labels must be displayed on-screen associated with important features, such as countries, cities, lakes, mountains, rivers, and the like. One problem facing the developers of computer mapping products is how to place labels on the map in a visually appealing or cartographically-preferable manner. Printed map makers spend many hours placing labels in specific locations to maximize the aesthetics of the printed map. Unfortunately, the designers of computerized mapping applications are faced with a different operating environment which creates special problems. First, the displayed map itself may change from moment to moment. A user of the mapping application may alter the displayed view, which may require moving some labels on the screen. The user may also select different features to display on the computer-generated map, a problem alien to the printed-map maker. Accordingly, designers of computer mapping programs strive to develop improved means for placing labels in cartographically-preferable positions on a computer-generated map.
To place a label on a computer-generated map, current mapping technologies typically analyze interferences between a potential label position and a feature displayed on the map (collisions). For instance, before placing a label on the map, potential label positions are first tested to determine if they collide with other features or labels, and then compared to determine the best of the potential label positions. One example of such a collision-analysis technology is described in patent application Ser. No. 08/980,846, filed on Dec. 1, 1997, entitled “SYSTEM AND METHOD FOR OPTIMALLY PLACING LABELS ON A MAP,” and assigned to the same assignee as the present application.
One problem with such mapping programs is that they generally fail to determine the degree to which a collision interferes with a potential label position. In other words, current mapping programs do not analyze how much of a potential label position is interfered with by another feature, such as land, water edges, streets, state borders, etc. The result may sometimes be less than aesthetically pleasing.
Thus, current label positioning technologies fail to consider the degree to which a potential label position is interfered. Consequently, a need exists for a system or method for identifying a cartographically-preferable label position for a feature from a plurality of potential label positions for the feature. In addition, the system or method should be capable of determining the degree to which a potential label position is interfered with by another label position or another feature. Moreover, the system or method should be capable of computing a penalty for each potential label position in the plurality of potential label positions based both on the quality and quantity of a collision between the potential label position and another label position or feature.
SUMMARY OF THE INVENTION
The present invention meets the above-described needs by providing a mechanism for selecting a cartographically-preferred label position from a plurality of potential label positions for a feature. The mechanism analyzes each pixel within each potential label position to determine the presence of 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.
In accordance with one embodiment of the present invention, each feature or feature class to be displayed on a computer-generated map is assigned a penalty. A feature class is a family of features of the same type. For example, all roads may be in one class, all lakes may be in another class, all rivers may be in a third class, etc. In addition, for the purpose of this discussion, a feature class may include features which are not of the same type, but which share a similar penalty weighting. The penalty may be associated with a desirability that the feature not be obstructed by a label or another feature. The desirability may be based on cartographic conventions well known in the art. In other words, all roads in a road feature class may have the same penalty, all rivers in a river feature class may have another penalty, all lakes in a lake feature class may have a third penalty, etc.
When a map is displayed on-screen by a mapping program, it is generally displayed in color. By assigning a particular color to each feature class, the displayed map is given visual characteristics. In other words, the different colors allow the viewer of the map to distinguish between different features. Accordingly, each feature or feature class is identifiable by a display color.
In this embodiment, the present invention associates each feature class penalty with that feature class' color. Prior to placing labels on the map for any feature requiring a label, the mapping program determines which of each potential label positions for the feature is the most cartographically preferable.
To help determine the most cartographically-preferable label position, the mapping program examines each pixel within each potential label position. Based on the color, the mapping program counts the number of pixels associated with each feature which coincides with the potential label position. For instance, if the first pixel examined is blue, and blue is associated with a “lake” feature class, then the mapping program associates the pixel with the lake feature class and its corresponding penalty. The mapping program tabulates the number of pixels which correspond to each of the possible feature classes. Once it has examined each of the pixels in a potential label position, the mapping program calculates a total penalty for that potential label position, and then repeats the process for the remaining potential label positions. Finally, the mapping program places the label in the label position having the lowest total penalty.
REFERENCES:
patent: 5684940 (1997-11-01), Freeman
patent: 5724072 (1998-03-01), Freeman
patent: 5798923 (1998-08-01), Laskowski
patent: 5848373 (1998-12-01), DeLorme et al.
patent: 5890808 (1999-04-01), Neff et al.
patent: 6154219 (2000-11-01), Wiley
patent: 6424933 (2002-07-01), Agrawala et al.
patent: 04240556 (1991-01-01), None
Edmondson etal.,A General Cartographic Labeling Algorithm. Mitsubishi Electric Research Laboratories. Jan. 1996.
Christensen et al.,Labeling Point Features on Maps and Diagrams. Harvard University Center for Research in Computer Technology. Jun. 1994.
Doerschler et al.,System for Dense-Map Name Placement. Communications of the ACM, vol.35, No. 1, pp. 70-79, Jan. 1992.
Yoeli, Pinhas.The Logic of Automated Map Lettering. pp. 99-108, 1972.
Freeman et al.,On the Problem of Placing Names in a Geographic Map. pp. 121-140. 1987.
Hirsch, Stephen.An Algorithm for Automatic Name Placement Around Point Data. The American Cartographer, vol. 9, No.1 pp. 5-17. 1982.
Sedluk Martin John
Wiley John-Michael
Bella Matthew C.
King & Spalding LLP
Microsoft Corporation
Sajous Wesner
LandOfFree
System and method for placing labels on a computer-generated... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for placing labels on a computer-generated..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for placing labels on a computer-generated... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3217578