System and method for labeling maps

• US 20080036788A1
• Filed: 08/13/2007
• Published: 02/14/2008
• Est. Priority Date: 06/16/2003
• Status: Active Grant

• Current Assignee: Theodore Gelber
• Original Assignee: Theodore Gelber
• Inventors: Gelber, Theodore
• Granted Patent: US 9,262,846 B2
• Time in Patent Office: Days
• US Class Current: 345/619
• 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 of pulling a label within boundaries of a map, wherein the label is a convex polygon with pre-assigned properties including location, vertices, type of movement allowed, and maximum movement permitted from an original position, and wherein the boundaries of the map comprise a rectangle, comprising the steps of:

determining if the label is wholly within the boundaries of the map,

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

moving the label within the boundaries of the map if;

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

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

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

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

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

4. The method of claim 1 further comprising discarding the label after attempting to move the label within boundaries of the map if the label is not wholly inside the boundaries of the map.

5. The method of claim 1 wherein determining if the label is wholly within the boundaries of the map comprises:

concluding, if all of the vertices of the label are inside the map, that the label is inside the boundaries of the map.

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

circumscribing a rectangle around 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 boundaries of the map,

and

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

7. A computer storage medium storing computer executable instructions for performing the method of claim 1.