Data processing: presentation processing of document – operator i – Presentation processing of document – Layout
Reexamination Certificate
1999-03-02
2003-12-16
Feild, Joseph H. (Department: 2176)
Data processing: presentation processing of document, operator i
Presentation processing of document
Layout
C715S252000, C715S252000, C345S587000, C345S619000, C345S648000
Reexamination Certificate
active
06665840
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to computer software application programs for creating and displaying computer-generated maps. More particularly, the present invention relates to a mapping program or software module for generating potential label positions for polygons at run time.
BACKGROUND OF THE INVENTION
Printed maps have been in existence for many centuries. However, the use of computer mapping programs to display maps has only achieved widespread acceptance in the most recent years. Today, there are many such mapping programs capable of creating and displaying a map in real-time. Mapping programs have many helpful uses, such as locating a business or home, or planning a route for a vacation.
To make a computer mapping program usable, labels must be displayed on-screen associated with important features, such as countries, cities, lakes, rivers, and the like. The developers of computer mapping programs are faced with many unique problems, one of which is the problem of placing labels on polygons displayed on a computer-generated map. Polygons are often used by mapping programs to represent areas, such as islands, lakes, large rivers, and the like. Unlike on printed maps, a polygon is sometimes only partially visible on a computer-generated map, depending on what portion of the map is currently on-screen. Unlike printed maps, it may be necessary to alter the position of a label for the polygon if less than the entire polygon is visible.
Before now, developers of mapping programs have not adequately addressed the need to move a label for a polygon depending on which part of the polygon is currently displayed. Existing mapping programs typically use a single, pre-configured position for the label of a polygon. If that label position happens to be off-screen, the label for the polygon is not displayed. The only known attempt to address this concern is to increase the number of pre-configured label positions. However, that solution typically falls short of presenting the polygon on-screen with the label in a cartographically preferable or aesthetically pleasing position.
Consequently, there is a need in the art for a system and method for dynamically generating multiple potential label positions for a polygon at run time. The potential label positions should provide the mapping application with a number of options from which to choose a preferable label position. The potential label positions should also be generated based on the visible portion of the polygon in order to achieve a more aesthetically pleasing result when displayed on the map.
SUMMARY OF THE INVENTION
The present invention meets the above described needs by providing a system and method for generating multiple potential label positions for a polygon at run time, rather than selecting from pre-configured label positions. The present invention analyzes the visible portion of the polygon to generate potential label positions dynamically based on the visible portion of the polygon, rather than by using pre-configured label positions. The present invention creates as many rectangles as can fit within the visible portion of the polygon, and which can support the placement of a label. The rectangles are sized in accordance with the size of the label to be displayed. Once the rectangles are created, the present invention allows for the selection of one of the rectangles as a preferred label position for the polygon.
In accordance with one embodiment of the present invention, the system begins by determining the outline of the polygon displayed on-screen. All of the polygon may or may not be visible. Once the outline of the polygon is determined, the system begins measuring horizontal lines in the first row of pixels within the polygon. Beginning at the leftmost pixel in the first row of pixels within the polygon, the length of a horizontal line is measured by counting the number of pixels displayed on-screen within the polygon and extending horizontally to the right from the beginning point. Likewise, the polygon itself may have an irregular shape, and the horizontal line may terminate at an edge of the polygon. Each horizontal -line in the first row of pixels is measured. The length and beginning point of each horizontal line is maintained.
Once the length and beginning point is determined for each horizontal line in the first row of pixels, the system proceeds to the second row of pixels. Again, the system determines the length and starting point of each horizontal line in the second row of pixels. This procedure is repeated until the system has determined the length and starting point for each, horizontal line in each row of pixels contained within the visible portion of the polygon.
Once each of the horizontal lines is known, the system generates potential label positions. Each potential label position is created by forming a rectangle around portions of the horizontal lines which overlap. In order to support a potential label position, a certain number of rows of pixels must contain a horizontal line. In other words, there must be enough overlap between horizontal lines in successive rows of pixels that a rectangular box can be constructed which outlines the potential label position. The number of rows necessary to support a label position is a function of the font size of the label to be displayed. For instance, a particular font size may require that fourteen rows of pixels all contain overlapping horizontal lines. Likewise, the length of the shortest horizontal line in the rectangle may determine the width of the rectangle forming the potential label position.
In this manner, several potential label positions may be generated at run time. Each potential label position is based on the portion of the polygon which is currently displayed on screen. By generating several potential label positions at run time, a preferred (most cartographically or aesthetically preferable) label position can be identified for any view of the map. Several methods to identify the preferred label position from a plurality of label positions are known to those skilled in the art, and are the subject of related patents. Once the preferred label position is identified, the label is placed on the polygon. The resulting map contains labels placed in a superior position of cartographic preference in most cases. Other aspects, benefits, and uses of the present invention will become apparent to those skilled in the art upon a reading of the following detailed description taken in conjunction with the attached drawings and appended claims.
REFERENCES:
patent: 5428733 (1995-06-01), Carr
patent: 5684940 (1997-11-01), Freeman et al.
patent: 5689717 (1997-11-01), Pritt
patent: 5724072 (1998-03-01), Freeman et al.
patent: 5734386 (1998-03-01), Cosman
patent: 5988853 (1999-11-01), Kim et al.
patent: 6154219 (2000-11-01), Wiley et al.
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
Feild Joseph H.
King & Spalding LLP
Microsoft Corporation
Singh Rachna
LandOfFree
System and method for run time generation of potential label... 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 run time generation of potential label..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for run time generation of potential label... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3165576