US2014218396A1PendingUtilityA1
System and method for labeling maps
Individually held — no corporate assignee on recordPriority: Jun 16, 2003Filed: Apr 5, 2014Published: Aug 7, 2014
Est. expiryJun 16, 2023(expired)· nominal 20-yr term from priority
Inventors:Theodore J. Gelber
G09B 29/10G06T 11/60G06T 11/20G06T 11/00G01C 21/3673
66
PatentIndex Score
0
Cited by
0
References
0
Claims
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
exact text as granted — not AI-modifiedI claim:
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:
collision
score
=
∑
ij
(
(
adjusted
priority
for
i
)
2
+
(
adjusted
priority
for
j
)
2
)
.
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.
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:
collision
score
=
∑
ij
(
(
adjusted
priority
for
i
)
2
+
(
adjusted
priority
for
j
)
2
)
.
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.
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:
collision
score
=
∑
ij
(
(
adjusted
priority
for
i
)
2
+
(
adjusted
priority
for
j
)
2
)
.
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.Join the waitlist — get patent alerts
Track US2014218396A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.