Method and system for text placement when forming maps

• US 6,565,610 B1
• Filed: 02/11/1999
• Issued: 05/20/2003
• Est. Priority Date: 02/11/1999
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Lampert, David S., Jasthi, Shashi, Wang, Yaoguang
• Primary Examiner(s): Feild, Joseph H.
• Application Number:
  US09/248,600
• Time in Patent Office: 1,559 Days
• Field of Search: 707/512, 707/517, 701/200, 701/207-213, 340/995, 345/581, 345/587, 345/619, 345/634-641, 345/855
• US Class Current: 715/210
• CPC Class Codes: G01C 21/3673 Labelling using text of road map data items, e.g. road names, POI names
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

A text placement program is disclosed. The text placement program provides for placement of text, such as 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. One additional weighted clause of the second type is included for each occurrence of the candidate location overlapping another candidate location. For each candidate location, the text placement program evaluates the expression for two conditions: placement of text and no placement. The results of the two evaluations of the expression are compared and the condition that provides the greater result is selected. Optionally, the expression may include an additional weighted clause including 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.

Claims

1. A text placement program contained on a storage medium, the program comprising:

a first routine that receives data identifying a plurality of candidate locations for placement of text associated with a plurality of represented geographic feature on a map image;

a second routine that evaluates each candidate location of said plurality of candidate locations using an expression that provides a result, wherein the expression comprises;

a clause of a first type indicative of whether a represented geographic feature is named at least once on the map image by considering whether the represented geographic feature has been previously named in another candidate location;

if a candidate location being evaluated for text placement overlaps another candidate location, a clause of a second type indicative of an occurrence of the candidate location not overlapping another candidate location; and

a third routine that determines whether to place text in the candidate location based upon the result provided by the expression.

2. The invention of claim 1 wherein the clause of the first type is weighted.

3. The invention of claim 1 wherein the clause of the second type is weighted.

4. The invention of claim 1 wherein the clause of the first type and the clause of the second type are weighted.

5. The invention of claim 1 wherein the expression further comprises:

a clause of a third type comprised of a term corresponding to a rank assigned to the represented geographic feature.

6. The invention of claim 5 wherein the clause of the third type is weighted.

7. The invention of claim 1 wherein, for each candidate location of said plurality of candidate locations, the text placement program evaluates the expression for two conditions, wherein said two conditions comprise placement of text and no placement in the candidate location.

8. The invention of claim 1 wherein said clause of a first type is comprised of a weighted disjunction of variables, wherein each of said variables represents a separate one of one or more candidate locations for placement of a same name along a represented geographic feature, and wherein each of said variables assumes one of two values, one of said two values indicative of placement of text in the represented candidate location and the other of said two values indicative of no placement of text in the represented candidate location.

9. The invention of claim 1 wherein said clause of a second type is comprised of a weighted disjunction of two complemented variables, wherein each of said variables represents a respective one of two overlapping candidate locations for placement of text, and wherein each of said variables assumes one of two values, one of said two values indicative of placement of text in the represented candidate location and the other of said two values indicative of no placement of text in the represented candidate location.

10. A method performed by a computing platform for forming a map image that represents a plurality of geographic features comprising the steps of:

determining whether to place text at each of a plurality of candidate locations, wherein said plurality of candidate locations comprise locations in the map image at which text can be placed, and wherein each of said plurality of candidate locations is associated with a geographic feature, and wherein each of said plurality of candidate locations is associated with a text string, and wherein the text string associated with a candidate location is also associated with the represented geographic feature associated therewith;

wherein said step of determining comprises;

for each one of said plurality of candidate locations, evaluating placement of text at said one of said plurality of candidate locations, wherein said evaluation produces a first result;

evaluating not placing text at said one of said plurality of candidate locations, wherein said evaluation produces a second result;

comparing said first result and said second result; and

determining whether to place text at said one of said plurality of candidate locations based upon said comparing step.

11. A method for forming a map image performed by a computing platform, said map image represents a plurality of geographic features, the method-comprising the steps of:

identifying a plurality of candidate locations in the map image at which text can be placed, wherein each of said plurality of candidate locations is associated with a geographic feature represented in the map image, and wherein each of said plurality of candidate locations is associated with a text string, and wherein the text string associated with a candidate location is also associated with the represented geographic feature associated therewith;

for each represented geographic feature, identifying all the candidate locations associated therewith that are also associated with an identical text string and forming a first type of clause indicative thereof;

for each candidate location, identifying all the other candidate locations overlapping therewith and forming a second type of clause indicative thereof; and

for each candidate location, determining whether to include text based upon an evaluation that includes the first type of clause formed by identifying all the candidate locations associated with a represented geographic feature that are also associated with an identical text string being evaluated by considering a probability of whether the text will also be included with another candidate location for the represented geographic feature and evaluating the second type of clause formed by identifying all the other candidate locations overlapping with the candidate location.

12. A method performed with a computing platform for forming a map image that represents a plurality of geographic features comprising the steps of:

determining whether to place text at a plurality of candidate locations, wherein said plurality of candidate locations comprise locations in the map image at which text can be placed, and wherein each of said plurality of candidate locations is associated with a geographic feature represented in the map image, and wherein each of said plurality of candidate locations is associated with a text string, and wherein the text string associated with a candidate location is also associated with the represented geographic feature associated therewith;

wherein for each of said plurality of candidate locations, said step of determining is based upon at least two factors,

wherein a first factor favors placement of the text string associated with a represented geographic feature at least once in a candidate location associated with the represented geographic feature by considering whether the text string may be also placed in another of said plurality of candidate locations in addition to the one of said plurality of candidate locations; and

wherein a second factor favors not overlapping a text string associated with one of said plurality of candidate locations with a text string associated with another of said plurality of candidate locations.

13. The method of claim 12 wherein said step of determining is based upon three factors, wherein a third factor favors placement of each text string associated with a represented geographic feature having a higher rank.

14. The method of claim 12 wherein said first factor includes a statistical probability of placement of text in all other candidate locations associated with the geographic feature that is associated with the one of the plurality of candidate locations for which the step of determining whether to place text is being performed.

15. The method of claim 12 wherein said second factor includes a statistical probability of placement of text in each other candidate location that overlaps the one of the plurality of candidate locations for which the step of determining whether to place text is being performed.

16. The method of claim 12 wherein said first factor includes a statistical probability of placement of text in all other candidate locations associated with the geographic feature that is associated with the one of the plurality of candidate locations for which the step of determining whether to place text is being performed and for which a determination has not already been made whether or not to place text.

17. A method for forming a map image that represents a plurality of geographic features, the method performed on a computing platform comprising the steps of:

determining whether to place text at each of a plurality of candidate locations, wherein said plurality of candidate locations comprise locations in the map image at which text can be placed, and wherein each of said plurality of candidate locations is associated with a geographic feature, and wherein each of said plurality of candidate locations is associated with a text string, and wherein the text string associated with a candidate location is also associated with the represented geographic feature associated therewith;

wherein said determining step comprises;

for each one of said candidate locations, determining whether text placed at said candidate location would overlap with text placed in another candidate location, and evaluating placement of text at said one of said candidate locations taking into account both whether text placed at said one of said candidate locations would overlap with text placed in another candidate location and whether the text string associated with the represented geographic feature included in at least one of the candidate locations associated with the represented geographic feature by considering whether the text string is also placed in the other candidate locations.

18. The method of claim 17 wherein the step of determining whether text placed at said candidate location would overlap with text placed in another candidate location is performed only in an area immediately around the candidate location being evaluated.

19. The method of claim 17 wherein the step of determining whether text placed at said candidate location would overlap with text placed in another candidate location, further comprises the steps of:

defining a plurality of intervals in said map image, wherein each of said plurality of intervals represents a section of the map image extending from one edge to an opposite edge; and

wherein all the candidate locations within any interval so defined are evaluated for placement of text prior to evaluation of any candidate locations in any interval in which all the candidate locations have not already been evaluated.

20. The method of claim 17 wherein the step of determining whether text placed at said candidate location would overlap with text placed in another candidate location, further comprises the steps of:

defining a plurality of intervals in said map image, wherein each of said plurality of intervals represents a section of the map image extending from one edge to an opposite edge; and

wherein all the candidate locations within an interval are evaluated in order from the one edge of the map image to the opposite edge.