Back to results
US 11,994,406 B2Granted
Group-based technique for dynamic label placement
AssigneeThe Government of the United States of America, as represented by the Secretary of the Navy
InventorsBrent Barre, Norman Schoenhardt
Life of this patent
Estimating the term…
Abstract
Systems and methods are provided for label placement that provide necessary information on a map when map features conflict without significantly impacting performance. Embodiments of the present disclosure can handle placement of map labels that vary in size, have prioritized label/feature groupings, apply to point, line, and area features, minimize overlap when there is no more open space, and render fast enough for interactive viewing.
Claims18
A system for label placement, the system comprising:
- a data storage device configured to store spatial feature information;
- and
- a labeling device, in communication with the data storage device, wherein the labeling device is configured to:
- receive the spatial feature information,
- receive data indicating a spatial area,
- determine a plurality of spatial feature entries in the spatial feature information that correspond to the spatial area,
- determine a symbol and a label for each spatial feature entry in the plurality of spatial feature entries,
- determine a plurality of symbol placements on a map for each symbol in the plurality of symbols,
- assign each symbol to a respective symbol deconfliction group in a plurality of symbol deconfliction groups after respective placements for each symbol have been determined, wherein each respective symbol is assigned to each respective symbol deconfliction group based on a respective spatial feature entry in the plurality of spatial feature entries that corresponds to each respective symbol,
- determine a plurality of groups to avoid for each label in the plurality of labels based on respective spatial feature entries in the plurality of spatial feature entries that correspond to each label,
- determine a minimum overlap score for a plurality of candidate label positions for each label in the plurality of labels based on a set of cell polygons into which respective label outline polygons for labels in the plurality of labels are divided, the plurality of groups to avoid, a plurality of weights assigned to the plurality of symbol deconfliction groups, and an intersection function corresponding to a potential intersection of the set of cell polygons and the plurality of groups to avoid,
- determine a plurality of label placements on the map for each label in the plurality of labels based on the plurality of groups to avoid, the minimum overlap score, and the plurality of weights assigned to the plurality of symbol deconfliction groups, wherein responsive to determining that there is no open space for a first one of the plurality of labels without overlap, the labeling device is configured to determine that the corresponding label placement for the first one of the plurality of labels be placed over a prior label on the map in a location having the candidate label position having the minimum overlap score corresponding to the first one of the plurality of labels, wherein determination of the prior label on the map is based on the plurality of weights assigned to the plurality of symbol deconfliction groups, and
- send the plurality of symbol placements and the plurality of label placements to an output device, wherein the sent plurality of label placements includes the label placement to be placed over the prior label on the map.
10 more elements
A method for label placement, the method comprising:
- receiving, using a processing device, data indicating a spatial area;
- determining, using the processing device spatial feature information for the spatial area, wherein the spatial feature information includes a plurality of spatial feature entries;
- determining, using the processing device, a symbol and a label for each spatial feature entry in the plurality of spatial feature entries;
- determining, using the processing device, a plurality of symbol placements on a map for each symbol in the plurality of symbols;
- assigning, using the processing device, each symbol to a respective symbol deconfliction group in a plurality of symbol deconfliction groups after respective placements for each symbol have been determined, wherein each respective symbol is assigned to each respective symbol deconfliction group based on a respective spatial feature entry in the plurality of spatial feature entries that corresponds to each respective symbol;
- determining, using the processing device, a plurality of groups to avoid for each label in the plurality of labels based on respective spatial feature entries in the plurality of spatial feature entries that correspond to each label;
- determining, using the processing device, a minimum overlap score for a plurality of candidate label positions for each label in the plurality of labels based on a set of cell polygons into which respective label outline polygons for labels in the plurality of labels are divided, the plurality of groups to avoid, a plurality of weights assigned to the plurality of symbol deconfliction groups, and an intersection function corresponding to a potential intersection of the set of cell polygons and the plurality of groups to avoid;
- determining, using the processing device, a plurality of label placements on the map for each label in the plurality of labels based on the plurality of groups to avoid, the minimum overlap score, and the plurality of weights assigned to the plurality of symbol deconfliction groups, wherein responsive to determining that there is no open space for a first one of the plurality of labels without overlap, determining that the corresponding label placement for the first one of the plurality of labels be placed over a prior label on the map in a location having the candidate label position having the minimum overlap score corresponding to the first one of the plurality of labels, wherein determination of the prior label on the map is based on the plurality of weights assigned to the plurality of symbol deconfliction groups;
- and
- sending, using the processing device, the plurality of symbol placements and the plurality of label placements to an output device, wherein the sent plurality of label placements includes the label placement to be placed over the prior label on the map.
7 more elements
A system for label placement, the system comprising:
- a data storage device configured to store spatial feature information;
- and
- a labeling device, in communication with the data storage device, wherein the labeling device is configured to:
- receive the spatial feature information,
- receive data indicating a spatial area,
- determine a plurality of spatial feature entries in the spatial feature information that correspond to the spatial area,
- determine a symbol and a label for each spatial feature entry in the plurality of spatial feature entries,
- determine a plurality of symbol placements on a map for each symbol in the plurality of symbols,
- assign each symbol to a respective symbol deconfliction group in a plurality of symbol deconfliction groups after respective placements for each symbol have been determined, wherein each respective symbol is assigned to each respective symbol deconfliction group based on a respective spatial feature entry in the plurality of spatial feature entries that corresponds to each respective symbol,
- determine a minimum overlap score for a plurality of candidate label positions for each label in the plurality of labels based on a set of cell polygons into which respective label outline polygons for labels in the plurality of labels are divided, a plurality of groups to avoid, a plurality of weights assigned to the plurality of symbol deconfliction groups, and an intersection function corresponding to a potential intersection of the set of cell polygons and the plurality of groups to avoid, and
- determine a plurality of label placements on the map for each label in the plurality of labels based on the minimum overlap score, the plurality of weights assigned to the plurality of symbol deconfliction groups, and a plurality of weights assigned to the plurality of label deconfliction groups, wherein responsive to determining that there is no open space for a first one of the plurality of labels without overlap, the labeling device is configured to determine that the corresponding label placement for the first one of the plurality of labels be placed over a prior label on the map in a location having the candidate label position having the minimum overlap score corresponding to the first one of the plurality of labels, wherein determination of the prior label on the map is based on the plurality of weights assigned to the plurality of symbol deconfliction groups.
8 more elements
Dependencies are inferred from the claim text.