System and method for abstracting and visualizing a route map
First Claim
1. A computer implemented 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 placing an annotation or label in a route map in an appropriate grid cell are described. Initially, the route map is partitioned into an initial grid; composed of candidate grid cells, into which the annotation or label can be placed. If necessary, a search for grid cells having sufficient adjacent object free grid cells is conducted. When no candidate grid cells are found during the identifying or searching stages, a grid subdivision scheme subdivides a portion of the grid cells in the initial grid to form a new grid. Then, the identifying and searching steps are repeated using the new grid. The process also ranks multiple candidate cells based on a density of objects in bordering grid cells. The candidate grid cell having the lowest density of objects in bordering cells is selected as the appropriate candidate grid cell.
109 Citations
18 Claims
-
1. A computer implemented 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 executable on 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