Placement of map labels
First Claim
Patent Images
1. A method of automatically annotating features on a map, comprising the steps of:
- in a first subtask, identifying a set of candidate positions for labels of said features;
in a second subtask, for each of said features selecting initial ones of said candidate positions;
in a third subtask, evaluating different ones of said candidate positions 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, wherein said first subtask, said second subtask, and said third subtask each comprise a static phase, and a real-time phase that is executed subsequent to said static phase responsively to data produced in said static phase.
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.
96 Citations
31 Claims
-
1. A method of automatically annotating features on a map, comprising the steps of:
-
in a first subtask, identifying a set of candidate positions for labels of said features;
in a second subtask, for each of said features selecting initial ones of said candidate positions;
in a third subtask, evaluating different ones of said candidate positions 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, wherein said first subtask, said second subtask, and said third subtask each comprise a static phase, and a real-time phase that is executed subsequent to said static phase responsively to data produced in said static phase. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. 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 perform a method of automatically annotating features on a map, comprising the steps of:
-
in a first subtask, identifying a set of candidate positions for each label of said features;
in a second subtask, for each of said features selecting initial ones of said candidate positions;
in a third subtask, evaluating different ones of said candidate positions 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, wherein said first subtask, said second subtask, and said third subtask each comprise a static phase,and a real-time phase that is executed subsequent to said static phase responsively to data produced in said static phase. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24)
-
-
25. A system for automatically situating labels on a map, said map having features to be labeled, comprising:
-
a server operative to perform the steps of;
in a first subtask, identifying a set of candidate positions for each label of said features;
in a second subtask, for each of said features selecting initial ones of said candidate positions;
in a third subtask, evaluating different ones of said candidate positions 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, wherein responsively to a request by said client, said server is operative to transmit data descriptive of said map for display by said client, wherein said first subtask, said second subtask, and said third subtask each comprise a static phase that is executable when said server is offline with said client and a real-time phase that is executed when said server is online with said client and subsequent to said static phase responsively to data produced in said static phase. - View Dependent Claims (26, 27, 28, 29, 30, 31)
-
Specification