Placement of map labels
First Claim
1. A method of automatically annotating features on a map, having a first subtask, a second subtask and a third subtask, each having a static phase and a real-time phase, the method comprising the steps of:
- in said first subtask, identifying a set of candidate positions for labels of said features, said static phase of said first subtask being performed prior to receiving a request for a map to be displayed, said static phase of said first subtask further comprising;
selecting rules for assignment of label attributes from a rule database;
responsively to said step of selecting rules, assigning said label attributes to said candidate positions, said label attributes comprising a font size, and a rotational orientation; and
designating a virtual candidate position having a zero size bounding rectangle and having metric parameters such that a cost of a selection of said virtual candidate position in said third subtask is less than a cost of an overlap conflict between said virtual candidate position and others of said candidate positions;
in said second subtask, for each of said features selecting initial ones of said candidate positions;
in said third subtask, evaluating different ones of said candidate positions and said virtual candidate position in comparison with said initial ones of said candidate positions to define a labeling;
responsively to said step of evaluating, replacing at least a portion of said initial ones of said candidate positions with corresponding said different ones of said candidate positions so as to optimize a quality function of said labeling,wherein said real-time phase of said first, second, and third subtasks being executed subsequent to said static phase of said first, second, and third subtasks, respectively, and responsively to data produced in said static phases, wherein said real-time phase of said third subtask is performed responsively to said request by simulated annealing; and
transmitting display data comprising said labeling from a map server to a client.
4 Assignments
0 Petitions
Accused Products
Abstract
Methods and systems are presented for the automatic optimal placement text or symbol labels corresponding to graphical objects on maps. Using a map server and a thin, typically mobile client, maps are dynamically drawn and displayed at the client. Optimized labeling of map objects is achieved by dividing the task into pipelined subtasks, some being performed off-line, and others being performed in real time, responsively to changing client requests, and changes in the map viewport. Optimization of candidate label positions is accomplished using simulated annealing.
-
Citations
28 Claims
-
1. A method of automatically annotating features on a map, having a first subtask, a second subtask and a third subtask, each having a static phase and a real-time phase, the method comprising the steps of:
-
in said first subtask, identifying a set of candidate positions for labels of said features, said static phase of said first subtask being performed prior to receiving a request for a map to be displayed, said static phase of said first subtask further comprising; selecting rules for assignment of label attributes from a rule database; responsively to said step of selecting rules, assigning said label attributes to said candidate positions, said label attributes comprising a font size, and a rotational orientation; and designating a virtual candidate position having a zero size bounding rectangle and having metric parameters such that a cost of a selection of said virtual candidate position in said third subtask is less than a cost of an overlap conflict between said virtual candidate position and others of said candidate positions; in said second subtask, for each of said features selecting initial ones of said candidate positions; in said third subtask, evaluating different ones of said candidate positions and said virtual candidate position in comparison with said initial ones of said candidate positions to define a labeling; responsively to said step of evaluating, replacing at least a portion of said initial ones of said candidate positions with corresponding said different ones of said candidate positions so as to optimize a quality function of said labeling, wherein said real-time phase of said first, second, and third subtasks being executed subsequent to said static phase of said first, second, and third subtasks, respectively, and responsively to data produced in said static phases, wherein said real-time phase of said third subtask is performed responsively to said request by simulated annealing; and transmitting display data comprising said labeling from a map server to a client. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A computer software product, including a computer-readable medium in which computer program instructions are stored, which instructions, when read by inter-connected computers, cause the computers to execute a first subtask, a second subtask and a third subtask to thereby automatically annotate features on a map responsively to a request for said map to be displayed, said first subtask, said second subtask and said third subtask each having a static phase and a real-time phase;
-
said first subtask comprising identifying a set of candidate positions for each label of said features, said static phase of said first subtask being performed prior to accepting said request, said static phase of said first subtask further comprising making a choice of rules for assignment of label attributes from a rule database assigning said label attributes to said candidate positions in accordance with said choice of rules, said label attributes comprising a font size, and a rotational orientation designating a virtual candidate position having a zero size bounding rectangle and having metric parameters such that a cost of a selection of said virtual candidate position in said third subtask is less than a cost of an overlap conflict between said virtual candidate position and others of said candidate positions; said second subtask comprising for each of said features selecting initial ones of said candidate positions; said third subtask comprising making an evaluation of different ones of said candidate positions and said virtual candidate position in comparison with said initial ones of said candidate positions to define a labeling, and responsively to said evaluation, replacing at least a portion of said initial ones of said candidate positions with corresponding said different ones of said candidate positions so as to optimize a quality function of said labeling, wherein said real-time phase of said first, second, and third subtasks are executed subsequent to said static phase of said first, second, and third subtasks, respectively, and responsively to data produced in said static phases, and wherein said real-time phase of said third subtask is performed responsively to said request by simulated annealing. - View Dependent Claims (16, 17, 18, 19, 20)
-
-
21. A system for automatically situating labels on a map, said map having features to be labeled, comprising:
-
a server operative to perform a first subtask, a second subtask and a third subtask, each having a static phase and a real-time phase the steps of; in said first subtask, identifying a set of candidate positions for each label of said features, said static phase of said first subtask being performed prior to receiving a request for a map to be displayed, said static phase of said first subtask further comprising; selecting rules for assignment of label attributes from a rule database; responsively to said step of selecting rules, assigning said label attributes to said candidate positions, said label attributes comprising a font size, and a rotational orientation; and designating a virtual candidate position having a zero size bounding rectangle and having metric parameters such that a cost of a selection of said virtual candidate position in said third subtask is less than a cost of an overlap conflict between said virtual candidate position and others of said candidate positions; in said second subtask, for each of said features selecting initial ones of said candidate positions; in said third subtask, evaluating different ones of said candidate positions and said virtual candidate position in comparison with said initial ones of said candidate positions to define a labeling; and responsively to said step of evaluating, replacing at least a portion of said initial ones of said candidate positions with corresponding said different ones of said candidate positions so as to optimize a quality function of said labeling; and a client linked to said server and issuing said request, wherein responsively to said request, said server is operative to transmit data descriptive of said map for display by said client, said real-time phase of said first, second, and third subtasks being executed subsequent to said static phase of said first, second, and third subtasks, respectively, and responsively to data produced in said static phases, wherein said real-time phase of said third subtask is performed responsively to said request by simulated annealing. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28)
-
Specification