System and method for optimally placing labels on a map
First Claim
1. A method for drawing map features and associated labels to be displayed on a map, comprising the steps of:
- compiling a list of map features to be potentially displayed on a map, the map features comprising point features and non-point features, each feature comprising an associated label positionable in a plurality of potential label positions;
assigning a label selection priority to each feature in the list;
ordering the features in the list in priority order;
drawing the non-point features in the list to a representation of the map; and
selecting point features, labels associated with the point features, and labels associated with the non-point features for drawing to the representation of the map by;
a. retrieving a selected feature from the list in priority order;
b. if the label associated with the selected feature can be placed in one or more of the potential label locations for the selected feature without causing a collision with any of the features or associated labels having a higher priority, drawing the label for the selected feature to the representation of the map in one of those locations and, if the feature is a point feature, also drawing the feature to the representation of the map;
c. if the label associated with the selected feature cannot be placed in one of the potential label locations for the feature without causing a collision with any of the features or associated labels having a higher priority, deleting the selected feature from the first list;
d. if the label has been drawn for the selected feature, determining whether there is a collision between the label and one or more point features having a lower priority and, if so, removing the features involved in the collision having the lower priorities from the list; and
e. repeating steps a-d until labels for all of the features remaining in the list have been drawn.
2 Assignments
0 Petitions
Accused Products
Abstract
Labeling objects on a computerized map in an efficient manner while avoiding collisions with both more and less important objects. A first list contains objects to be labeled on the computerized map, the objects being both points and non-points. Each of the objects in the first list has a label selection priority. A second list contains the a collection of objects from the first list having the lowest label selection priority. The system can draw each object in the first list to the computerized map in ascending order of label selection priority. As each object is drawn, the system labels the object with a label while avoiding collisions between the label and objects in the second list having a higher label selection priority than the object.
-
Citations
20 Claims
-
1. A method for drawing map features and associated labels to be displayed on a map, comprising the steps of:
-
compiling a list of map features to be potentially displayed on a map, the map features comprising point features and non-point features, each feature comprising an associated label positionable in a plurality of potential label positions; assigning a label selection priority to each feature in the list; ordering the features in the list in priority order; drawing the non-point features in the list to a representation of the map; and selecting point features, labels associated with the point features, and labels associated with the non-point features for drawing to the representation of the map by; a. retrieving a selected feature from the list in priority order; b. if the label associated with the selected feature can be placed in one or more of the potential label locations for the selected feature without causing a collision with any of the features or associated labels having a higher priority, drawing the label for the selected feature to the representation of the map in one of those locations and, if the feature is a point feature, also drawing the feature to the representation of the map; c. if the label associated with the selected feature cannot be placed in one of the potential label locations for the feature without causing a collision with any of the features or associated labels having a higher priority, deleting the selected feature from the first list; d. if the label has been drawn for the selected feature, determining whether there is a collision between the label and one or more point features having a lower priority and, if so, removing the features involved in the collision having the lower priorities from the list; and e. repeating steps a-d until labels for all of the features remaining in the list have been drawn. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 17, 19)
-
-
11. A method for drawing map features and associated labels to be displayed on a map, comprising the steps of:
-
compiling a first list of map features to be potentially displayed on a map, the map features comprising point features and non-point features, each feature comprising an associated label positionable in a plurality of potential label positions; assigning a label selection priority to each feature in the first list; ordering the features in the first list in priority order; compiling a second list comprising selected point features from the first list; creating a weighted collision array for the features of the second list including a penalty for each feature in the second list, and if there are multiple potential label positions for the selected feature, determining whether there are collisions, and for each of the available potential label positions, determining a penalty for the label position by identifying one or more features in collision with the label position, obtaining the penalties for the features in collision from the weighted collision array, and those penalties to the label position, and drawing the non-point features in the list to a representation of the map; and selecting point features, labels associated with the point features, and labels associated with the non-point features for drawing to the representation of the map by; a. retrieving a selected feature from the first list in priority order; b. if there are multiple potential label positions for the selected feature that do not collide with features or labels having a higher priority, determining whether there are collisions between multiple available potential label positions and features having lower priorities, and if so, c. if the label associated with the selected feature cannot be placed in one of the potential label locations for the feature without causing a collision with any of the features or associated labels having a higher priority, deleting the selected feature from the first and second lists; d. if the label has been drawn for the selected feature, determining whether there is a collision between the label and one or more point features having a lower priority and, if so, removing the features involved in the collision having the lower priorities from the first and second lists; and e. repeating steps a-d until labels for all of the features remaining in the list have been drawn. - View Dependent Claims (13, 15, 18, 20)
-
Specification