System and method for abstracting and visualizing a route map
First Claim
1. A method of placing an annotation or label in a route map, said method comprising:
- partitioning said route map into an initial grid that is composed of grid cells;
identifying candidate grid cells into which said annotation or label can be placed, wherein each said candidate grid cell is a grid cell that is free of objects associated with said route map;
searching, when said annotation or label will not fit in a single candidate grid cell, for grid cells having sufficient adjacent object free grid cells such that said candidate grid cell and one or more of said adjacent object free grid cells can accommodate said annotation or label;
when no candidate grid cells are found in said identifying or searching steps, performing a grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid to form a new grid, and repeating said identifying and searching steps using said new grid;
ranking, when multiple candidate grid cells are found, each candidate grid cell based on a density of objects in grid cells that border each said candidate grid cell, wherein the candidate grid cell that borders grid cells having the lowest density of objects is selected as the candidate grid cell and all other candidate grid cells are discarded; and
positioning said annotation or label in said candidate grid cell, thereby placing said annotation or label in said route map.
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.
70 Citations
18 Claims
-
1. A method of placing an annotation or label in a route map, said method comprising:
-
partitioning said route map into an initial grid that is composed of grid cells;
identifying candidate grid cells into which said annotation or label can be placed, wherein each said candidate grid cell is a grid cell that is free of objects associated with said route map;
searching, when said annotation or label will not fit in a single candidate grid cell, for grid cells having sufficient adjacent object free grid cells such that said candidate grid cell and one or more of said adjacent object free grid cells can accommodate said annotation or label;
when no candidate grid cells are found in said identifying or searching steps, performing a grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid to form a new grid, and repeating said identifying and searching steps using said new grid;
ranking, when multiple candidate grid cells are found, each candidate grid cell based on a density of objects in grid cells that border each said candidate grid cell, wherein the candidate grid cell that borders grid cells having the lowest density of objects is selected as the candidate grid cell and all other candidate grid cells are discarded; and
positioning said annotation or label in said candidate grid cell, thereby placing said annotation or label in said route map. - 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 map annotation module for placing an annotation or label in a route map, said map annotation module including;
instructions for partitioning said route map into an initial grid, said initial grid composed of grid cells;
instructions for identifying candidate grid cells into which said annotation or label can be placed, wherein each said candidate grid cell is a grid cell that is free of objects associated with said route map;
instructions for searching, when said annotation or label will not fit in a single candidate grid cell, for grid cells having sufficient adjacent object free grid cells such that said candidate grid cell and one or more of said adjacent object free grid cells can accommodate said annotation or label;
instructions for performing a grid subdivision scheme, when no candidate grid cells are found after execution of said instructions for identifying or said instructions for searching, said grid subdivision scheme subdividing a portion of said grid cells in said initial grid to form a new grid, and instructions for re-executing said instructions for identifying and said instructions for searching using said new grid;
instructions for ranking, when multiple candidate grid cells are found by said instructions for identifying or said instructions for searching, said ranking of each candidate grid cell dependent on a density of objects in grid cells that border each said candidate grid cell, wherein the candidate grid cell that borders grid cells having the lowest density of objects is chosen as the candidate grid cell and all other candidate grid cells are discarded; and
instructions for positioning said annotation or label in said candidate grid cell, thereby placing said annotation or label in said route map. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A computer system for optimizing a display of 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;
instructions for partitioning said route map into an initial grid, said initial grid composed of grid cells;
instructions for identifying candidate grid cells into which said annotation or label can be placed, wherein each said candidate grid cell is a grid cell that is free of objects associated with said route map;
instructions for searching, when said annotation or label will not fit in a single candidate grid cell, for grid cells having sufficient adjacent object free grid cells such that said candidate grid cell and one or more of said adjacent object free grid cells can accommodate said annotation or label;
instructions for performing a grid subdivision scheme, when no candidate grid cells are found after execution of said instructions for identifying or said instructions for searching, said grid subdivision scheme subdividing a portion of said grid cells in said initial grid to form a new grid, and instructions for re-executing said instructions for identifying and said instructions for searching using said new grid;
instructions for ranking, when multiple candidate grid cells are found by said instructions for identifying or said instructions for searching, said ranking of each candidate grid cell dependent on a density of objects in grid cells that border each said candidate grid cell, wherein the candidate grid cell that borders grid cells having the lowest density of objects is chosen as the candidate grid cell and all other candidate grid cells are discarded; and
instructions for positioning said annotation or label in said candidate grid cell, thereby placing said annotation or label in said route map. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification