SYSTEM AND METHOD FOR LABELING MAPS

• US 20140218396A1
• Filed: 04/05/2014
• Published: 08/07/2014
• Est. Priority Date: 06/16/2003
• Status: Abandoned Application

• Current Assignee: Theodore J. Gelber
• Original Assignee: Theodore J. Gelber
• Inventors: Gelber, Theodore J.
• Application Number:
  US14/246,038
• Publication Number:
  US 20140218396A1
• Time in Patent Office: Days
• US Class Current: 345/629
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B

Abstract

A system and method for label placement is disclosed that achieves the twin goals of practical efficiency and high labeling quality by employing cartographic heuristics. A caller defines map and label properties. Then labels are pulled within a map boundary. Labels are next ordered by priority in descending importance. The order of testing labels is determined. Attempts are made to move overlapping labels. This is an iterative process; therefore there must be criteria that halt the procedure. Upon reaching an acceptable solution, the label properties are adjusted to reflect the new label placements.

Claims

1. A method for determining when to invoke a computer routine to halt label movement of a group of labels on a map utilizing a computer system comprising the computer implemented steps of:

determining for the group of labels a collision score;

determining for the group of labels an iteration count;

determining for the group of labels a slow change count; and

determining for the group of labels an oscillation count;

wherein the routine to halt label movement is invoked when the collision score indicates there are no label collisions, or the iteration count is greater than a first given value, or the slow change count is greater than a second given value, or the oscillation count is greater than a third given value.

2. The method of claim 1 wherein determining the collision score comprises calculating for each overlapping pair of labels i and j, where i and j are not equal to each other, the following formula:

3. The method of claim 1 wherein determining the iteration count comprises incrementing the iteration count upon each iteration in the collision score.

4. The method of claim 1 wherein determining the slow change count comprises incrementing the slow change count upon each iteration in the collision score according to the following calculation:

slow change count=slow change count+1 when (collision score<

=previous collision score) and (collision score>

X*previous collision score) where X is close to but less than one;

wherein else slow change count=zero.

5. The method of claim 1 wherein determining the oscillation count comprises incrementing the oscillation count upon each iteration in the collision score according to the following calculation:

oscillation count=oscillation count+1 when ((collision score>

previous collision score and previous collision score<

previous previous collision score) or (collision score<

previous collision score and previous collision score>

previous previous collision score));

wherein else oscillation count=zero.

11. A non-transitory computer storage medium storing computer executable instructions for performing the method of claim 1.

12. The medium of claim 11 wherein determining for the group of labels the collision score comprises calculating for each overlapping pair of labels i and j, where i and j are not equal to each other, the following formula:

13. The medium of claim 11 wherein determining for the group of labels the iteration count comprises incrementing the iteration count upon each iteration in the collision score.

14. The medium of claim 11 wherein determining for the group of labels the slow change count comprises incrementing the slow change count upon each iteration in the collision score according to the following calculation:

slow change count=slow change count+1 when (collision score<

=previous collision score) and (collision score>

X*previous collision score) where X is close to but less than one;

wherein else slow change count=zero.

15. The medium of claim 11 wherein determining for the group of labels the oscillation count comprises incrementing the oscillation count upon each iteration in the collision score according to the following calculation:

oscillation count=oscillation count+1 when ((collision score>

previous collision score and previous collision score<

previous previous collision score) or (collision score<

previous collision score and previous collision score>

previous previous collision score));

wherein else oscillation count=zero.

6. A computer system for determining the iteration to invoke a computer routine to halt label movement of a group of labels on a map, said computer system comprising:

input means for inputting map data and label data;

memory means for storing the iteration;

processor means responsive to a control program for generating digital signals corresponding to the iteration, the processor means being adapted to;

determining for the group of labels a collision score;

determining for the group of labels an iteration count;

determining for the group of labels a slow change count; and

determining for the group of labels an oscillation count;

wherein the iteration to invoke the computer routine to halt label movement is determined when the collision score indicates there are no label collisions, or the iteration count is greater than a first given value, or the slow change count is greater than a second given value, or the oscillation count is above a third given value.

7. The system of claim 6 wherein determining for the group of labels the collision score comprises calculating for each overlapping pair of labels i and j, where i and j are not equal to each other, the following formula:

8. The system of claim 6 wherein determining for the group of labels the iteration count comprises incrementing the iteration count upon each iteration in the collision score.

9. The system of claim 6 wherein determining for the group of labels the slow change count comprises incrementing the slow change count upon each iteration in the collision score according to the following calculation:

slow change count=slow change count+1 when (collision score<

=previous collision score) and (collision score>

X*previous collision score) where X is close to but less than one;

wherein else slow change count=zero.

10. The system of claim 6 wherein determining for the group of labels the oscillation count comprises incrementing the oscillation count upon each iteration in the collision score according to the following calculation:

oscillation count=oscillation count+1 when ((collision score>

previous collision score and previous collision score<

previous previous collision score) or (collision score<

previous collision score and previous collision score>

previous previous collision score));

wherein else oscillation count=zero.