System and method for labeling maps

• US 9,262,846 B2
• Filed: 08/13/2007
• Issued: 02/16/2016
• Est. Priority Date: 06/16/2003
• Status: Active Grant

• Current Assignee: Theodore Joseph Gelber
• Original Assignee: Theodore Joseph Gelber
• Inventors: Gelber, Theodore Joseph
• Primary Examiner(s): Brier, Jeffery A
• Application Number:
  US11/891,606
• Publication Number:
  US 20080036788A1
• Time in Patent Office: 3,109 Days
• Field of Search: 345/629, 345/672, 345/636
• 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 generating a solution for pulling a label within a boundary of a map utilizing a computer system comprising the computer implemented steps of:

determining, if the label is not wholly within the boundary of the map, a fraction of a label area that is inside the boundary of the map,

moving the label within the boundary of the map if;

a. the fraction of the label area inside the boundary of the map is greater than a predetermined value,

b. a distance of a movement of the label is less than a maximum movement permitted from an original position, and

c. the movement would result in all vertices located within the boundary of the map,

and then

outputting the solution to a caller,

wherein a boundary of the label is a convex polygon with pre-assigned properties including the original position, the vertices, a type of movement allowed, and the maximum movement permitted from the original position, and

wherein the boundary of the map is a rectangle.

2. The method of claim 1 wherein the type of movement allowed is a vector type movement.

3. The method of claim 1 wherein the type of movement allowed is a 2D type movement.

4. The method of claim 1 further comprising a computer implemented step of discarding the label after attempting to move the label within the boundary of the map if the label is not wholly inside the boundary of the map.

5. The method of claim 1 further comprising the computer implemented step of concluding that the label is wholly within the boundary of the map if all of the vertices are inside the map.

6. The method of claim 1 wherein the determining, if the label is not wholly within the boundary of the map, the fraction of the label area that is inside the boundary of the map, comprises:

circumscribing a rectangle around the boundary of the label,

dividing the rectangle into a n by m grid of sub-rectangles,

testing a centroid of each sub-rectangle to determine if the sub-rectangle centroid is inside the label,

testing, if the centroid is inside the label, if the centroid is inside the boundary of the map,

and

dividing a number of centroids both inside the label and inside the boundary of the map by a number of centroids inside the label.

7. The method of claim 1 further comprising discarding the label if the fraction of the label area inside the boundary of the map is less than a predetermined value;

wherein the boundary of the map is fixed relative to features within the boundary of the map;

wherein the boundary of the map is additionally fixed relative to the original position of the label;

and

wherein the features are not eliminated before the discarding.

8. The method of claim 1 further comprising discarding the label unless the label is always at least partially within the boundary of the map.

9. A method for generating a solution for pulling a label within a boundary of a map utilizing a computer system comprising the computer implemented steps of:

determining, if the label is not wholly within the boundary of the map, a fraction of a label area that is inside the boundary of the map,

moving the label within the boundary of the map if;

a. the fraction of the label area inside the boundary of the map is greater than a predetermined value,

b. a distance of a movement of the label is less than a maximum movement permitted from an original position, and

c. the movement would result in all vertices located within the boundary of the map,

and then

outputting the solution to a caller,

wherein a boundary of the label is defined by a convex polygon so that the polygon circumscribes the label, the label having pre-assigned properties including the original position, the vertices, a type of movement allowed, and the maximum movement permitted from the original position, and

wherein the boundary of the map is a rectangle.

10. The method of claim 9 wherein the type of movement allowed is a vector type movement.

11. The method of claim 9 wherein the type of movement allowed is a 2D type movement.

12. The method of claim 9 further comprising a computer implemented step of discarding the label after attempting to move the label within the boundary of the map if the label is not wholly inside the boundary of the map.

13. The method of claim 9 further comprising the computer implemented step of concluding that the label is wholly within the boundary of the map if all of the vertices are inside the map.

14. The method of claim 9 wherein the determining, if the label is not wholly within the boundary of the map, the fraction of the label area that is inside the boundary of the map, comprises:

circumscribing a rectangle around the boundary of the label,

dividing the rectangle into a n by m grid of sub-rectangles,

testing a centroid of each sub-rectangle to determine if the sub-rectangle centroid is inside the label,

testing, if the centroid is inside the label, if the centroid is inside the boundary of the map,

and

dividing a number of centroids both inside the label and inside the boundary of the map by a number of centroids inside the label.

15. The method of claim 9 further comprising discarding the label if the fraction of the label area inside the boundary of the map is less than a predetermined value;

wherein the boundary of the map is fixed relative to features within the boundary of the map;

wherein the boundary of the map is additionally fixed relative to the original position of the label;

and

wherein the features are not eliminated before the discarding.

16. The method of claim 9 further comprising discarding the label unless the label is always at least partially within the boundary of the map.

17. A method for generating a solution for pulling a label within a boundary of a map utilizing a computer system comprising the computer implemented steps of:

determining, if the label is not wholly within the boundary of the map, a fraction of a label area that is inside the boundary of the map,

moving the label within the boundary of the map if;

a. the fraction of the label area inside the boundary of the map is greater than a predetermined value,

b. a distance of a movement of the label is less than a maximum movement permitted from an original position, and

c. the movement would result in all vertices located within the boundary of the map,

and then

outputting the solution to a caller,

wherein a boundary of the label is defined by a convex polygon so that the polygon circumscribes the label, the label having pre-assigned properties including the original position, the vertices, a type of movement allowed, and the maximum movement permitted from the original position,

wherein the label is discarded unless the label in its original position is at least partially within the boundaries of the map, and

wherein the boundary of the map is a rectangle.

18. The method of claim 17 wherein the type of movement allowed is a vector type movement.

19. The method of claim 17 wherein the type of movement allowed is a 2D type movement.

20. The method of claim 17 further comprising a computer implemented step of discarding the label after attempting to move the label within the boundary of the map if the label is not wholly inside the boundary of the map.

21. The method of claim 17 further comprising the computer implemented step of concluding that the label is wholly within the boundary of the map if all of the vertices are inside the map.

22. The method of claim 17 wherein the determining, if the label is not wholly within the boundary of the map, the fraction of the label area that is inside the boundary of the map, comprises:

circumscribing a rectangle around the boundary of the label,

dividing the rectangle into a n by m grid of sub-rectangles,

testing a centroid of each sub-rectangle to determine if the sub-rectangle centroid is inside the label,

testing, if the centroid is inside the label, if the centroid is inside the boundary boundaries of the map,

and

dividing a number of centroids both inside the label and inside the boundary of the map by a number of centroids inside the label.

23. The method of claim 17 further comprising discarding the label if the fraction of the label area inside the boundary of the map is less than a predetermined value;

wherein the boundary of the map is fixed relative to features within the boundary of the map;

wherein the boundary of the map is additionally fixed relative to the original position of the label;

and

wherein the features are not eliminated before the discarding.