Data processing: presentation processing of document – operator i – Presentation processing of document – Layout
Reexamination Certificate
1999-02-11
2003-05-20
Feild, Joseph H. (Department: 2176)
Data processing: presentation processing of document, operator i
Presentation processing of document
Layout
C345S619000, C345S215000
Reexamination Certificate
active
06565610
ABSTRACT:
REFERENCE TO MICROFICHE APPENDIX
Included with and forming part of this specification is an a micofiche appendix including one sheet of 30 frames.
REFERENCE TO COPYRIGHTED MATERIAL
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
The present invention relates to forming maps and more particularly, the present invention relates to an improved process and system for placement of text on a map image to denote names of displayed features, such as roads.
Computer-generated map images have various uses. Some navigation systems, such as in-vehicle navigation systems, include display screens upon which map images can be shown to end users. Computer-generated map images are also generated and shown on other types of computing systems and platforms, including personal computers (including desktop and notebook computers), dedicated electronic devices (such as hand-held portable navigation systems), pagers, PalmPilot®-type devices, telephones, and networks (including the Internet).
Some map images are generated by software programs using geographic databases. A geographic database stores information about features located in a geographic region. The information included in a geographic database may include the geographic coordinates of the represented features such as roads and intersections, the names and highway numbers of the represented roads, the geographic coordinates of represented points of interests, the names of points of interests, and so on. Using the information in the geographic database and suitable software programming, a map image can be generated and rendered on a display screen. Alternately, using the information in the geographic database and appropriate software, a map can be printed or saved to a disk file for later use.
Persons who use maps are accustomed to the presentation of information in certain conventional ways. For example, it is expected that a line rendered on a map image represents a road and that the name of a road represented by a line be placed immediately adjacent to the line on the map image. It is preferable that maps generated from geographic databases conform to users' expectations.
Using a geographic database and appropriate software to generate a map image provides important, useful advantages for end users. When using a geographic database to generate a map on a display, the software program may allow the end user to select the area to be displayed, the scale, the level of detail, the kinds of points of interest to be displayed, and so on. Because these factors are selectable by the end user, the placement of the names of roads or other geographic features is not necessarily determined beforehand. Instead, the placement of the names of roads or other geographic features may not be determined until the boundaries of the map to be displayed are selected, the level of detail selected, and other configurable factors set. Accordingly, a means is required in the software programming to determine suitable locations for the placement of the names of the represented geographic features as part of the process of rendering the map image for display.
Programs that determine where to place names of geographic features on maps are known. However, prior programs are relatively slow and therefore require relatively long times to determine where to place the names of displayed geographic features on a map image. Because these prior programs for placement of names on a map image are relatively slow, they may be unsuitable for use on computing platforms that have relatively limited resources, such as some kinds of navigation systems, hand-held devices, and so on.
Accordingly, there is a need to provide an improved and faster means to determine the locations for placement of text, such as names of geographic features, on a map image.
SUMMARY OF THE INVENTION
To address these and other objectives, the present invention comprises a text placement program. The text placement program provides for placement of text, such as the names of geographic features, on a map image. A plurality of candidate locations for text placement are identified and provided to the text placement program. The text placement program evaluates each candidate location for text placement using an expression that includes a weighted clause of a first type indicative of whether the represented geographic feature is named at least once on the map image. If a candidate location being evaluated for text placement overlaps another candidate location, the expression for the candidate location being evaluated includes a weighted clause of a second type. For each candidate location, the text placement program evaluates the expression for two conditions: placement of text and no placement of text. The results of the two evaluations of the expression are compared and the condition that provides the greater result is selected. Optionally, the expression for each candidate location may include a third weighted clause that indicates a rank assigned to the represented geographic feature. The text placement program can be configured by adjusting the weightings assigned to the clause(s) of which it is formed. Each candidate location is evaluated in this manner until all the candidate locations are evaluated. Text is then placed in the selected candidate locations.
REFERENCES:
patent: 4527155 (1985-07-01), Yamaki et al.
patent: 4646089 (1987-02-01), Takanabe et al.
patent: 4757455 (1988-07-01), Tsunoda et al.
patent: 4812980 (1989-03-01), Yamada et al.
patent: 4914605 (1990-04-01), Loughmiller, Jr. et al.
patent: 4996645 (1991-02-01), Schneyderberg Van Der Zon
patent: 5297051 (1994-03-01), Arakawa et al.
patent: 5559938 (1996-09-01), Van Roekel et al.
patent: 5689717 (1997-11-01), Pritt
patent: 5724072 (1998-03-01), Freeman et al.
patent: 5988853 (1999-11-01), Kim et al.
patent: 6091424 (2000-07-01), Madden et al.
patent: 6092076 (2000-07-01), McDonough et al.
patent: 6154219 (2000-11-01), Wiley et al.
patent: 6226646 (2001-05-01), Geurts
patent: 6330858 (2001-12-01), McDonough et al.
Hirsch, Stephen A. An Algorithm for Automatic Name Placement Around Point Data. The American Cartographer, vol. 9, No. 1, 1982, pp. 5-17.*
Edmondson, Shawn, and Christensen, Jon. A General Cartographic Labeling Algorithm, Mitsubishi Electric Research Laboratories. Massachusetts: Jan. 1996. pp. 1-18.*
UMI Dissertation Services, Automatic Map Name Placement System, J. Ahn (1984).
Auto-Carto Six, Proceedings of the Sixth International Symposium on Automated Cartography, vol. II, Automated Cartography: International Perspective On Achievements and Challenges, A Program For Automatic Name Placement, J. Ahn and H. Freeman (1985).
Computer-Assisted Cartography Principles and Prospects, Mark S. Monmonier (1982).
Jasthi Shashi
Lampert David S.
Wang Yaoguang
Feild Joseph H.
Kaplan Lawrence
Kozak Frank J.
Navigation Technologies Corporation
Shutter Jon
LandOfFree
Method and system for text placement when forming maps does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for text placement when forming maps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for text placement when forming maps will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3043082