Patent ID: 7414637
Filing Date: 2008-08-19
Classification: G01C

Abstract:
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.