×

Placement of map labels

  • US 7,414,637 B2
  • Filed: 09/10/2004
  • Issued: 08/19/2008
  • Est. Priority Date: 09/10/2004
  • Status: Expired due to Fees
First Claim
Patent Images

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 all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×