SYSTEM AND METHOD FOR LABELING MAPS
First Claim
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,andplacing onto the map remaining labels in respective computed locations.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
28 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A computer system for automatically labeling a map in accordance with 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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28)
-
Specification