System and method for labeling maps

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.

I claim: 
     
         1 . A method utilizing a computer system for generating a solution for determining a fraction of a label area, of a label, that is within a boundary of a map, if the label is not wholly within the boundary of the map, comprising the computer implemented steps of:
 circumscribing a rectangle around a 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;   dividing the number of centroids both inside the label and inside the boundary of the map by the number inside the label;   and then   outputting the solution to a caller.   
     
     
         2 . The method of  claim 1  wherein the boundary of the label is a convex polygon. 
     
     
         3 . The method of  claim 1  wherein the boundary of the map is a rectangle. 
     
     
         4 . A computer system for generating a solution for determining a fraction of a label area that is within a boundary of a map, if a label is not wholly within the boundary, said computer system comprising:
 input means for inputting map data and label data;   memory means for storing the solution;   processor means responsive to a control program for generating digital signals corresponding to the solution, the processor means being adapted to:   circumscribing a rectangle around a 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;   dividing the number of centroids both inside the label and inside the boundary of the map by the number inside the label;   and then outputting the solution to the memory means.   
     
     
         5 . The system of  claim 4  wherein the boundary of the label is a convex polygon. 
     
     
         6 . The system of  claim 4  wherein the boundary of the map is a rectangle. 
     
     
         7 . A non-transitory computer storage medium storing computer executable instructions for performing the method of  claim 1 . 
     
     
         8 . The medium of  claim 7  wherein the boundary of the label is a convex polygon. 
     
     
         9 . The medium of  claim 7  wherein the boundary of the map is a rectangle.