System and method for labeling maps
OwnerTheodore J. Gelberinventor
Life of this patent
Estimating the term…
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.
Claims21
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,
- wherein the boundary of the map is a rectangle, and
- 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.
A computer system for generating a solution for pulling a label within a boundary of a map, 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:
- 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,
- wherein the boundary of the map is a rectangle, and
- 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 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.
Dependencies are inferred from the claim text.