System and method for abstracting and visualizing a route map

• US 7,076,409 B2
• Filed: 12/06/2004
• Issued: 07/11/2006
• Est. Priority Date: 03/17/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Stolte, Chris, Agrawala, Maneesh
• Primary Examiner(s): Broda, Samuel
• Application Number:
  US11/005,834
• Publication Number:
  US 20050137791A1
• Time in Patent Office: 582 Days
• Field of Search: 703 1- 2, 703 6- 8, 701201-212, 715517-521
• US Class Current: 703/2
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G01C 21/3673 Labelling using text of road map data items, e.g. road names, POI names
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 17/05 Geographic models

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.

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.

2. The method of claim 1 wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a uniform spacial separation scheme.

3. The method of claim 1 wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a nonuniform spacial subdivision scheme.

4. The method of claim 1 wherein said annotation or label is constrained to a subregion of said route map and said identifying and searching steps are limited to said subregion.

5. The method of claim 4 wherein said portion of said grid cells in said initial grid includes said subregion, and said grid subdivision scheme comprises uniformly dividing each initial grid cell into four uniformly sized grid cells.

6. The method of claim 4 wherein said subregion of said route map is enlarged when no candidate grid cells are found in an instance of said identifying and searching steps.

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.

8. The computer program product of claim 7 wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a uniform spacial separation scheme.

9. The computer program product of claim 7 wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a nonuniform spacial subdivision scheme.

10. The computer program product of claim 7 wherein said annotation or label is constrained to a subregion of said route map and said instructions for identifying and said instructions for searching are limited to said subregion.

11. The computer program product of claim 10 wherein said portion of said grid cells in said initial grid includes said subregion, and said grid subdivision scheme comprises uniformly dividing each initial grid cell into four uniformly sized grid cells.

12. The computer program product of claim 10 wherein said subregion of said route map is enlarged when no candidate grid cells are found after execution of said instructions for identifying and instructions for searching.

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.

14. The computer system of claim 13 wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a uniform spacial separation scheme.

15. The computer system of claim 13 wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a nonuniform spacial subdivision scheme.

16. The computer system of claim 13 wherein said annotation or label is constrained to a subregion of said route map and said instructions for identifying and said instructions for searching are limited to said subregion.

17. The computer system of claim 16 wherein said portion of said grid cells in said initial grid includes said subregion, and said grid subdivision scheme comprises uniformly dividing each initial grid cell into four uniformly sized grid cells.

18. The computer system of claim 16 wherein said subregion of said route map is enlarged when no candidate grid cells are found after execution of said instructions for identifying and instructions for searching.