System and method for abstracting and visualizing a route map
First Claim
1. A method of positioning a plurality of labels in a route map, the method comprising, for each label in said plurality of labels:
- associating a plurality of constraint definitions with said label;
each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style;
selecting an initial constraint definition from said plurality of constraint definitions;
positioning a center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; and
the method further comprising;
choosing a label in said plurality of labels;
determining a first score (S1) using a target function;
wherein the score is determined by a position of said chosen label in said route map;
applying a different constraint definition, from the plurality of constraint definitions associated with said selected label;
said applying step including the step of repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition;
calculating a second score (S2) using said target function;
wherein the score is determined by the repositioned label position;
accepting the new position for said label in accordance with a function that is determined by a comparison of S1 and S2;
repeating said choosing, determining, applying, calculating, and accepting steps until a first occurrence of an exit condition.
1 Assignment
0 Petitions
Accused Products
Abstract
A system and method for making computer-generated maps includes a different scale factor for each road in a route. The scale factors are used to optimize the route map against a target function that considers factors such as the number of false intersections in the route and the number of roads falling below a minimum length threshold. A refinement technique such as simulated annealing is used to find a solution to the target function. Each road in the scaled map is rendered to provide a finished product having the appearance of a hand-drawn map. The finished product includes context roads that intersect the main route but are not part of the main route. Furthermore, the hand-drawn map is optimized to the characteristics of the viewport used to visualize the map.
-
Citations
18 Claims
-
1. A method of positioning a plurality of labels in a route map, the method comprising, for each label in said plurality of labels:
-
associating a plurality of constraint definitions with said label;
each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style;
selecting an initial constraint definition from said plurality of constraint definitions;
positioning a center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; and
the method further comprising;
choosing a label in said plurality of labels;
determining a first score (S1) using a target function;
wherein the score is determined by a position of said chosen label in said route map;
applying a different constraint definition, from the plurality of constraint definitions associated with said selected label;
said applying step including the step of repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition;
calculating a second score (S2) using said target function;
wherein the score is determined by the repositioned label position;
accepting the new position for said label in accordance with a function that is determined by a comparison of S1 and S2;
repeating said choosing, determining, applying, calculating, and accepting steps until a first occurrence of an exit condition. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:
-
a label placement module for positioning a plurality of labels in a route map, the label placement module comprising, for each label in said plurality of labels;
instructions for associating a plurality of constraint definitions with said label;
each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style;
instructions for selecting an initial constraint definition from said plurality of constraint definitions;
instructions for positioning a center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; and
the module further including;
instructions for choosing a label in said plurality of labels;
instructions for determining a first score (S1) using a target function;
wherein the score is determined by a position of said chosen label in said route map;
instructions for applying a different constraint definition, from the plurality of constraint definitions associated with said selected label;
said instructions for applying including instructions for repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition;
instructions for calculating a second score (S2) using said target function;
wherein the score is determined by the repositioned label position;
instructions for accepting the new position for said label in accordance with a function that is determined by a comparison of S1 and S2;
instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A computer system for positioning a plurality of labels in a route map, the computer system comprising:
-
a central processing unit;
a memory, coupled to said central processing unit;
a viewport for displaying said route map;
a program module, executable by said central processing unit, said program module comprising;
a label refinement module for refining the plurality of labels in a route map, the label refinement module comprising, for each label in said plurality of labels;
instructions for associating a plurality of constraint definitions with said label;
each constraint definition in said plurality of constraint definitions uniquely defining a bounding box, label orientation, and layout style;
instructions for selecting an initial constraint definition from said plurality of constraint definitions;
instructions for positioning a center of said label at a location within the bounding box defined by said initial constraint definition in accordance with the label orientation and layout style defined by said initial constraint definition; and
the label refinement module further including;
instructions for choosing a label in said plurality of labels;
instructions for determining a first score (S1) using a target function;
wherein the score is determined by a position of said chosen label in said route map;
instructions for applying a different constraint definition, from the plurality of constraint definitions associated with said selected label;
said instructions for applying including instructions for repositioning a center of said label inside the bounding box defined by said different constraint definition in accordance with the label orientation and layout style defined by said different constraint definition;
instructions for calculating a second score (S2) using said target function;
wherein the score is determined by the repositioned label position;
instructions for accepting the new position for said label in accordance with a function that is determined by a comparison of S1 and S2;
instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification