System and method for labeling maps

• US 9,472,006 B2
• Filed: 04/01/2014
• Issued: 10/18/2016
• Est. Priority Date: 06/16/2003
• Status: Active Grant

• Current Assignee: Theodore J. Gelber
• Original Assignee: Theodore J. Gelber
• Inventors: Gelber, Theodore J.
• Primary Examiner(s): Brier, Jeffery A
• Application Number:
  US14/231,757
• Publication Number:
  US 20140300631A1
• Time in Patent Office: 931 Days
• Field of Search: 345/636, 345/672, 345/681
• US Class Current: 1/1
• 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 placing labels on a map utilizing a computer system, the computer system programmed to perform steps of the method, comprising:

retrieving an association of each of the labels with a respective target feature on the map without regard to other of the labels or features of the map,

retrieving properties of the features of the map,

retrieving properties of the labels,

pulling the labels within boundaries of the map,

ordering the labels in rank of descending priority,

selecting halting criteria parameters including iteration count, slow change count, and

oscillation count,

iterating the following steps, (a) to (f);

(a) determining if all label pairs have been tested, and if all the label pairs have been tested proceeding to step (d),

(b) cycling through the label pairs, testing whether pair members overlap each other, and, if the members do not overlap, then proceeding to step (a),

(c) moving a second member of an overlapping label pair to a location where there is no overlap with any label, or to a location where there is overlap with one or more labels of lesser priority than a first label of the label pair,

(d) performing an evaluation function to calculate a collision score,

(e) executing a halting procedure using an iteration number, a respective previous collision score, and the collision score,

(f) comparing a result of the executing to the halting criteria parameters to determine if the moving the labels is to be halted, and, if the moving is not to be halted, proceeding to step (a), else proceeding to the following step,

eliminating the labels which cannot be placed on the map without overlapping other of the labels with higher priority,

adjusting the properties of the labels,

and

placing onto the map remaining labels in respective computed locations.

2. The method of claim 1 wherein the pulling labels within map boundaries comprises:

determining whether each of the labels is wholly within the boundaries of the map,

determining, for labels not wholly within the boundaries of the map, what fraction of an area of each of the labels is within the boundaries of the map, and

moving each of the labels within the boundaries of the map, if the fraction of the area of each of the labels outside the boundaries of the map is less than a predetermined value,

wherein placing onto the map the remaining labels comprises placing onto the map labels that have been moved within the boundaries of the map.

3. The method of claim 1 wherein the testing whether pair members overlap each other comprises:

choosing a first label and a second label to compare,

associating the first label with a region of a first convex planar polygon,

associating the second label with a region of a second convex planar polygon,

finding maximum extents of the first convex planar polygon and the second convex planar polygon respectively associated with the first label and the second label,

comparing the maximum extent of the first polygon with the maximum extent of the second polygon and, if the extents do not overlap, concluding that the pair members do not overlap each other,

testing vertices of the first polygon with edges forming a perimeter of the second polygon and, if any vertex is within the second polygon, then concluding that the pair members overlap each other, and

testing each edge of the first polygon with each edge of the second polygon, and, if any edges being tested intersect, then concluding that the pair members overlap each other.

4. The method of claim 3 wherein the testing the vertices of the first polygon with the edges forming the perimeter of the second polygon comprises:

traversing the perimeter of the second polygon,

obtaining equations of lines containing the edges forming the perimeter of the second polygon,

testing the vertices of the first polygon with the equations of the lines containing the edges forming the perimeter of the second polygon until all the vertices of the first polygon are tested, and

concluding that the label pair overlap if any vertex of the first polygon is within a boundary of the second polygon as determined by the equations.

5. The method of claim 3 wherein the testing each edge of the first polygon with each edge of the second polygon comprises:

obtaining equations of lines containing edges of the first polygon,

obtaining equations of lines containing edges of the second polygon,

calculating intersection points of the edges of the first polygon and the edges of the second polygon,

determining if the points lie on any of the edges of the first polygon or any of the edges of the second polygon, and

concluding that if at least one of the points lies on any of the edges of the first polygon or any of the edges of the second polygon then the label pair overlap.

6. The method of claim 1 wherein the performing the evaluation function comprises:

cycling through label pairs,

testing whether members of a current label pair overlap,

checking whether either label of the pair is too far outside the boundaries of the map or completely outside of the boundaries of the map, and

performing the calculation of the collision score of a label overlap.

7. The method of claim 6 wherein the to determine if the moving the labels is to be halted comprises:

testing if;

(a) the collision score of the label overlap is zero, or

(b) a consecutive number of iterations of slow changes exceeds the slow change count, or

(c) a number of oscillations exceeds the oscillation count, or

(d) a number of iterations exceeds the iteration count.

8. The method of claim 1 wherein the adjusting the properties of the labels comprises cycling through each label pair, testing whether each member of the pair overlap, eliminating a second member of the each label pair if the second member overlaps a first member of the each label pair, and eliminating the labels not pulled into the boundaries of the map.

9. The method of claim 1 wherein the step of moving the second member of an overlapping label pair and the step of eliminating the labels comprise:

moving a second member of an overlapping label pair, which overlap other of the labels of higher priority or equal priority, whenever possible to locations where there is no overlap;

or, if not possible, to where there is overlap with one or more of the labels of lesser priority or equal priority;

eliminating the labels of lesser priority where there is overlap with the labels of higher priority; and

eliminating labels which overlap labels of equal priority so that one label remains.

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

11. The medium of claim 10 wherein the pulling labels within map boundaries comprises:

determining whether each of the labels is wholly within the boundaries of the map,

determining, for labels not wholly within the boundaries of the map, what fraction of an area of each of the labels is within the boundaries of the map, and

moving each of the labels within the boundaries of the map, if the fraction of the area of each of the labels outside the boundaries of the map is less than a predetermined value,

wherein placing onto the map the remaining labels comprises placing onto the map labels that have been moved within the boundaries of the map.

12. The medium of claim 10 wherein the testing whether pair members overlap each other comprises:

choosing a first label and a second label to compare,

associating the first label with a region of a first convex planar polygon,

associating the second label with a region of a second convex planar polygon,

finding maximum extents of the first convex planar polygon and the second convex planar polygon respectively associated with the first label and the second label,

comparing the maximum extent of the first polygon with the maximum extent of the second polygon and, if the extents do not overlap, concluding that the pair members do not overlap each other,

testing vertices of the first polygon with edges forming a perimeter of the second polygon and, if any vertex is within the second polygon, then concluding that the pair members overlap each other, and

testing each edge of the first polygon with each edge of the second polygon, and, if any edges being tested intersect, then concluding that the pair members overlap each other.

13. The medium of claim 12 wherein the testing the vertices of the first polygon with the edges forming the perimeter of the second polygon comprises:

traversing the perimeter of the second polygon,

obtaining equations of lines containing the edges forming the perimeter of the second polygon,

testing the vertices of the first polygon with the equations of the lines containing the edges forming the perimeter of the second polygon until all the vertices of the first polygon are tested, and

concluding that the label pair overlap if any vertex of the first polygon is within a boundary of the second polygon as determined by the equations.

14. The medium of claim 12 wherein the testing each edge of the first polygon with each edge of the second polygon comprises:

obtaining equations of lines containing edges of the first polygon,

obtaining equations of lines containing edges of the second polygon,

calculating intersection points of the edges of the first polygon and the edges of the second polygon,

determining if the points lie on any of the edges of the first polygon or any of the edges of the second polygon, and

concluding that if at least one of the points lies on any of the edges of the first polygon or any of the edges of the second polygon then the label pair overlap.

15. The medium of claim 10 wherein the performing the evaluation function comprises:

cycling through label pairs,

testing whether members of a current label pair overlap,

checking whether either label of the pair is too far outside the boundaries of the map or completely outside of the boundaries of the map, and

performing the calculation of the collision score of a label overlap.

16. The method of claim 15 wherein the to determine if the moving the labels is to be halted comprises:

testing if;

(a) the collision score of the label overlap is zero, or

(b) a consecutive number of iterations of slow changes exceeds the slow change count, or

(c) a number of oscillations exceeds the oscillation count, or

(d) a number of iterations exceeds the iteration count.

17. The medium of claim 10 wherein the adjusting the properties of the labels comprises cycling through each label pair, testing whether each member of the pair overlap, eliminating a second member of the each label pair if the second member overlaps a first member of the each label pair, and eliminating the labels not pulled into the boundaries of the map.

18. The medium of claim 10 wherein the step of moving the second member of an overlapping label pair and the step of eliminating the labels comprise:

moving a second member of an overlapping label pair, which overlap other of the labels of higher priority or equal priority, whenever possible to locations where there is no overlap;

or, if not possible, to where there is overlap with one or more of the labels of lesser priority or equal priority;

eliminating the labels of lesser priority where there is overlap with the labels of higher priority; and

eliminating labels which overlap labels of equal priority so that one label remains.

19. A computer system for automatically labeling a map in accordance predefined label positioning and placement criteria, the map including a plurality of regions encompassing points with said region and bounded by region boundary points to be labeled with a corresponding label in accordance with said label positioning and placement criteria, said system comprising:

input cans for inputting map data including region data for said plurality of regions to be labeled and label data including said corresponding label for each of said plurality of regions,

first memory means for storing said map data and said region data,

processor means responsive to a control program for generating digital signals corresponding to approximate label positions for each of said regions satisfying said label positioning criteria and digital signals denoting final label positions for each of said locations satisfying said label placement criteria, said processor means being adapted to;

retrieving an association of each of the labels with a respective target feature on the map without regard to other of the labels or features of the map,

retrieving properties of the features of the map,

retrieving properties of the labels,

pulling the labels within boundaries of the map,

ordering the labels in rank of descending priority,

selecting halting criteria parameters including iteration count, slow change count, and oscillation count,

iterating the following steps, (a) to (f);

(a) determining if all label pairs have been tested, and if all the label pairs have been tested proceeding to step (d),

(b) cycling through the label pairs, testing whether pair members overlap each other, and, if the members do not overlap, then proceeding to step (a),

(c) moving a second member of an overlapping label pair to a location where there is no overlap with any label, or to a location where there is overlap with one or more labels of lesser priority than a first label of the label pair,

(d) performing an evaluation function to calculate a collision score,

(e) executing a halting procedure using an iteration number, a respective previous collision score, and the collision score,

(f) comparing a result of the executing to the halting criteria parameters to determine if the moving the labels is to be halted, and, if the moving is not to be halted, proceeding to step (a), else proceeding to the following step,

eliminating the labels which cannot be placed on the map without overlapping other of the labels with higher priority,

adjusting the properties of the labels,

and

placing onto the map remaining labels in respective computed locations.

20. The computer system as claimed in claim 19, further comprising display means for displaying a graphic image of said map data together with a graphic image generated from said digital signals corresponding to the final label positions of each label.

21. The computer system of claim 19 wherein the pulling labels within map boundaries comprises:

determining whether each of the labels is wholly within the boundaries of the map,

determining, for labels not wholly within the boundaries of the map, what fraction of an area of each of the labels is within the boundaries of the map, and

moving each of the labels within the boundaries of the map, if the fraction of the area of each of the labels outside the boundaries of the map is less than a predetermined value,

wherein placing onto the map the remaining labels comprises placing onto the map labels that have been moved within the boundaries of the map.

22. The computer system of claim 19 wherein the testing whether pair members overlap each other comprises:

choosing a first label and a second label to compare,

associating the first label with a region of a first convex planar polygon,

associating the second label with a region of a second convex planar polygon,

finding maximum extents of the first convex planar polygon and the second convex planar polygon respectively associated with the first label and the second label,

comparing the maximum extent of the first polygon with the maximum extent of the second polygon and, if the extents do not overlap, concluding that the pair members do not overlap each other,

testing vertices of the first polygon with edges forming a perimeter of the second polygon and, if any vertex is within the second polygon, then concluding that the pair members overlap each other, and

testing each edge of the first polygon with each edge of the second polygon, and, if any edges being tested intersect, then concluding that the pair members overlap each other.

23. The computer system of claim 22 wherein the testing the vertices of the first polygon with the edges forming the perimeter of the second polygon comprises:

traversing the perimeter of the second polygon,

obtaining equations of lines containing the edges forming the perimeter of the second polygon, testing the vertices of the first polygon with the equations of the lines containing the edges forming the perimeter of the second polygon until all the vertices of the first polygon are tested, and

concluding that the label pair overlap if any vertex of the first polygon is within a boundary of the second polygon as determined by the equations.

24. The computer system of claim 22 wherein the testing each edge of the first polygon with each edge of the second polygon comprises:

obtaining equations of lines containing edges of the first polygon,

obtaining equations of lines containing edges of the second polygon,

calculating intersection points of the edges of the first polygon and the edges of the second polygon,

determining if the points lie on any of the edges of the first polygon or any of the edges of the second polygon, and

concluding that if at least one of the points lies on any of the edges of the first polygon or any of the edges of the second polygon then the label pair overlap.

25. The computer system of claim 19 wherein the performing the evaluation function comprises:

cycling through label pairs,

testing whether members of a current label pair overlap,

checking whether either label of the pair is too far outside the boundaries of the map or completely outside of the boundaries of the map, and

performing the calculation of the collision score of a label overlap.

26. The computer system of claim 25 wherein the to determine if the moving the labels is to be halted comprises:

testing if;

(a) the collision score of the label overlap is zero, or

(b) a consecutive number of iterations of slow changes exceeds the slow change count, or

(c) a number of oscillations exceeds the oscillation count, or

(d) a number of iterations exceeds the iteration count.

27. The computer system of claim 19 wherein the adjusting the properties of the labels comprises cycling through each label pair, testing whether each member of the pair overlap, eliminating a second member of the each label pair if the second member overlaps a first member of the each label pair, and eliminating the labels not pulled into the boundaries of the map.

28. The computer system of claim 19 wherein the step of moving the second member of an overlapping label pair and the step of eliminating the labels comprise:

moving a second member of an overlapping label pair, which overlap other of the labels of higher priority or equal priority, whenever possible to locations where there is no overlap;

or, if not possible, to where there is overlap with one or more of the labels of lesser priority or equal priority;

eliminating the labels of lesser priority where there is overlap with the labels of higher priority; and

eliminating labels which overlap labels of equal priority so that one label remains.