System and method for abstracting and visualizing a route map

• US 7,437,279 B2
• Filed: 03/04/2005
• Issued: 10/14/2008
• 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): JONES, HUGH M
• Application Number:
  US11/073,399
• Publication Number:
  US 20050149303A1
• Time in Patent Office: 1,320 Days
• Field of Search: 703/2, 703/6, 715/866
• US Class Current: 703/6
• 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 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.

Claims

1. A method for optimizing a display of a route map, the method comprising:

fitting a collection of reference points in said route map with a probability distribution function, each said reference point corresponding to a position of an intersection in said route map;

deriving (i) a position representative of said collection of reference points, (ii) a first farthest position in which a member of said collection of reference points extends in a first direction away from said representative position, (iii) and a second farthest position to which a member of said collection of reference points extends in a direction that is orthogonal to a vector between said representative position and said first farthest position;

computing a bounding box, wherein a size and orientation of said bounding box is determined by said representative position, said first farthest position and said second farthest position;

determining a direction of the long axis of said bounding box; and

rotating said route map, by an amount that is sufficient to reorient said long axis so that said long axis lies in a predetermined orientation, to form a rotated route map.

2. The method of claim 1, wherein said probability function is selected from the group consisting of a binomial distribution, a Poisson distribution, and a Gaussian distribution.

3. The method of claim 1, wherein said predetermined orientation is chosen so that a starting point in said rotated route map is in a designated location.

4. 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 embedded therein;

a map optimization module for optimizing a display of a route map, said map optimization module comprising;

instructions for fitting a collection of reference points in said route map with a probability distribution function, each said reference point corresponding to a position of an intersection in said route map;

instructions for deriving (i) a position representative of said collection of reference points, (ii) a first farthest position in which a member of said collection of reference points extends in a first direction away from the representative position, (iii) and a second farthest position to which a member of said collection of reference points extends in a direction that is orthogonal to a vector between said representative position and said first farthest position;

instructions for computing a bounding box, wherein a size and orientation of said bounding box is determined by said representative position, said first farthest position and said second farthest position;

instructions for determining a direction of the long axis of said bounding box; and

instructions for rotating said route map, by an amount that is sufficient to reorient said long axis so that said long axis lies in a predetermined orientation, to form a rotated route map.

5. The computer program product of claim 4, wherein said probability function is selected from the group consisting of a binomial distribution, a Poisson distribution, and a Gaussian distribution.

6. The computer program product of claim 4, wherein said predetermined orientation is chosen so that a starting point in said rotated route map is in a designated location.

7. 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 program module, executable by said central processing unit, said program module comprising;

instructions for fitting a collection of reference points in said route map with a probability distribution function, each said reference point corresponding to a position of an intersection in said route map;

instructions for deriving (i) a position representative of said collection of reference points, (ii) a first farthest position in which a member of the collection of reference points extends in a first direction away from the representative position, (iii) and a second farthest position to which a member of said collection of reference points extends in a direction that is orthogonal to a vector between said representative position and said first farthest position;

instructions for computing a bounding box, wherein a size and orientation of said bounding box is determined by said representative position, said first farthest position and said second farthest position;

instructions for determining a direction of the long axis of said bounding box; and

instructions for rotating said route map, by an amount that is sufficient to reorient said long axis so that said long axis lies in a predetermined orientation, to form a rotated route map.

8. The computer system of claim 7, wherein said probability function is selected from the group consisting of a binomial distribution, a Poisson distribution, and a Gaussian distribution.

9. The computer system of claim 7, wherein said predetermined orientation is chosen so that a starting point in said rotated route map is displayed in a designated location in a viewport.

10. The computer system of claim 9, wherein said designated location is the top or bottom of said viewport.

11. The computer system of claim 7, further comprising a viewport for displaying said route map, and wherein:

said viewport has a horizontal dimension x and a vertical dimension y;

a portion of said rotated route map displayed on said viewport represents a full vertical component of said rotated route map and a subset of a horizontal component of said rotated route map;

said program module further comprising;

instructions for associating a scroll bar with said horizontal dimension of said viewport, whereby, in response to directed input, the full horizontal component of said rotated route map is accessible.

12. The computer system of claim 7 further comprising a viewport for displaying said route map, wherein:

said viewport has a horizontal dimension x and a vertical dimension y;

a portion of said rotated route map displayed on said viewport represents a full horizontal component of said rotated route map and a subset of a vertical component of said rotated route map;

said program module further comprising;

instructions for associating a scroll bar with said vertical dimension of said viewport, whereby, in response to directed input, the full vertical component of said rotated route map is accessible.

13. The computer system of claim 12, wherein said predetermined orientation is vertical.

14. The computer system of claim 7, wherein said route map has a constant dimension and a variable dimension orthogonal to said constant dimension, the length of the variable dimension determined by a number of steps or a distance of a route within said route map.

15. The computer system of claim 7, wherein said computer system is a personal digital assistant.