System and method for abstracting and visualizing a rout map

• US 20010034588A1
• Filed: 11/30/2000
• Published: 10/25/2001
• Est. Priority Date: 03/17/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Agrawals, Maneesh, Stolte, Chris
• Granted Patent: US 6,952,661 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

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 mean position 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 mean 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 mean position and said first farthest position;

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

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

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; and

presenting a portion of said rotated route map, thereby optimizing said display of said 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 mechanism embedded therein, the computer program mechanism comprising:

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 mean position 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 mean 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 mean 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 mean position, said first farthest position and said second farthest position;

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

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; and

instructions for presenting a portion of said rotated route map, thereby optimizing said display of said 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 viewport for displaying said route map;

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 mean position 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 mean 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 mean 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 mean position, said first farthest position and said second farthest position;

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

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; and

instructions for presenting a portion of said rotated route map on said viewport, thereby optimizing said display of said 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 said 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

, wherein:

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

said portion of said rotated route map displayed on said viewport representing 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

, wherein:

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

said portion of said rotated route map displayed on said viewport representing 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.

16. 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.

17. The method of

claim 16

wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a uniform spacial separation scheme.

18. The method of

claim 16

wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a nonuniform spacial subdivision scheme.

19. The method of

claim 16

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.

20. The method of

claim 19

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.

21. The method of

claim 19

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.

22. 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.

23. The computer program product of

claim 22

wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a uniform spacial separation scheme.

24. The computer program product of

claim 22

wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a nonuniform spacial subdivision scheme.

25. The computer program product of

claim 22

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.

26. The computer program product of

claim 25

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.

27. The computer program product of

claim 25

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.

28. 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.

29. The computer system of

claim 28

wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a uniform spacial separation scheme.

30. The computer system of

claim 28

wherein said grid subdivision scheme, which subdivides a portion of said grid cells in said initial grid, is a nonuniform spacial subdivision scheme.

31. The computer system of

claim 28

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.

32. The computer system of

claim 31

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.

33. The computer system of

claim 31

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.

34. 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 (S₁) 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 (S₂) 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 S₁ and S₂;

repeating said choosing, determining, applying, calculating, and accepting steps until a first occurrence of an exit condition.

35. The method of

claim 34

wherein said function comprises accepting the repositioned label position:

(1) when S₂ is less than S₁; and

(2) with the probability P(Δ

S), when S₂ is greater than S₁, where P(Δ

S) is a probability function that is dependent upon an effective temperature t that is reduced by an amount after each execution of said repeating step.

36. The method of

claim 34

where:

P(Δ

S)=exp<sup>−

[(Δ

S)/(k*t)]</sup>Δ

S=(S₁)−

(S₂), and k is a constant.

37. The method of

claim 34

, wherein said positioning step further comprises fixing a label in said plurality of labels in said route map when said label does not intersect with any other label in said route map;

and said choosing step does not choose a label that has been fixed.

38. The method of

claim 34

, wherein each constraint definition in said plurality of constraint definitions includes a scoring strategy that is used by said target function in said determining and calculating steps.

39. The method of

claim 34

, wherein each said layout style is selected from the group consisting of a simple layout style, a combination of an arrow image with the primary name for a street or highway, a combination of a primary name for a street or highway with a mileage along the road, a highway number as text stacked on top of a shield image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.

40. 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 (S₁) 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 (S₂) 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 S₁ and S₂;

instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition.

41. The computer program product of

claim 40

wherein said function comprises instructions for accepting the repositioned label position:

(1) when S₂ is less than S₁; and

(2) with the probability P(Δ

S), when S₂ is greater than S₁, where P(Δ

S) is a probability function that is dependent upon an effective temperature t that is reduced by an amount after each execution of said repeating step.

42. The computer program product of

claim 40

where:

P(Δ

S)=exp<sup>−

[(Δ

S)/(k*t)]</sup>Δ

S=(S₁)−

(S₂), and k is a constant.

43. The computer program product of

claim 40

, wherein said instructions for positioning further comprises instructions fixing a label in said plurality of labels in said route map when said label does not intersect with any other label in said route map;

and said instructions for choosing includes instructions for not choosing a label that has been fixed.

44. The computer program product of

claim 40

, wherein each constraint definition in said plurality of constraint definitions includes a scoring strategy that is used by said target function coded by said instructions for determining and calculating.

45. The computer program product of

claim 40

, wherein each said layout style is selected from the group consisting of a simple layout style, a combination of an arrow image with the primary name for a street or highway, a combination of a primary name for a street or highway with a mileage along the road, a highway number as text stacked on top of shield image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.

46. 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 (S₁) 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 (S₂) 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 S₁ and S₂;

instructions for repeating said instructions for choosing, determining, applying, calculating, and accepting until a first occurrence of an exit condition.

47. The computer system of

claim 46

wherein said function comprises instructions for accepting the repositioned label position:

(1) when S₂ is less than S₁; and

(2) with the probability P(Δ

S), when S₂ is greater than S₁, where P(Δ

S) is a probability function that is dependent upon an effective temperature t that is reduced by an amount after each execution of said repeating step.

48. The computer system of

claim 46

where:

P(Δ

S)=exp<sup>−

[(Δ

S)/(k*t)]</sup>Δ

S=(S₁)−

(S₂), and k is a constant.

49. The computer system of

claim 46

, wherein said instructions for positioning further comprises instructions fixing a label in said plurality of labels in said route map when said label does not intersect with any other label in said route map;

and said instructions for choosing includes instructions for not choosing a label that has been fixed.

50. The computer system of

claim 46

, wherein each constraint definition in said plurality of constraint definitions includes a scoring strategy that is used by said target function coded by said instructions for determining and calculating.

51. The computer system of

claim 46

, wherein each said layout style is selected from the group consisting of a simple layout style, a combination of an arrow image with the primary name for a street or highway, a combination of a primary name for a street or highway with a mileage along the road, a highway number as text stacked on top of a shield image, a word-wrapped name, and a highway number stacked on top of a shield image with a mileage along a corresponding road.

52. A method of preparing a route map that describes a path between a start and an end, said method comprising:

obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

estimating a total height and a total width of a rendering of each element in said scaled set of elements;

selecting, based on a function of said total height and said total width, an image component; and

outputting a rendering of each element in said scaled set of elements to said image component.

53. The method of

claim 52

, wherein, in said selecting step:

when a ratio of said total width to said total height is less than about 0.60, a first image component is selected;

when a ratio of said total width to said total height is greater than about 2.0, a second image component is selected; and

when said first image and said second image component is not selected, a third image component is selected.

54. The method of

claim 52

, wherein said image component is selected based on said function as well as a number of elements in said scaled set of elements.

55. 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 module for preparing a route map that describes a path between a start and an end, the map module comprising;

instructions for obtaining said path from said start to said end, the path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

instructions for independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

instructions for estimating a total height and a total width of a rendering of each element in said scaled set of elements;

instructions for selecting, based on a function of said total height and said total width, an image component; and

instructions for outputting a rendering of each element in said scaled set of elements to said image component.

56. The computer program product of

claim 55

, wherein, said instructions for selecting further include:

instructions for selecting a first image component when a ratio of said total width to said total height is less than about 0.60;

instructions for selecting a second image component when a ratio of said total width to said total height is greater than about 2.0; and

instructions for selecting a third image component when said first image and said second image component is not selected.

57. The computer program product of

claim 55

, wherein said image component is selected based on said function as well as a number of elements in said scaled set of elements.

58. A computer system for preparing 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 map module for preparing said route map, the route map describing a path between a start and an end, the map module comprising;

instructions for obtaining said path from said start to said end, the path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

instructions for independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

instructions for estimating a total height and a total width of a rendering of each element in said scaled set of elements;

instructions for selecting, based on a function of said total height and said total width, an image component; and

instructions for outputting a rendering of each element in said scaled set of elements to said image component.

59. The computer system of

claim 58

, wherein, said instructions for selecting further include:

instructions for selecting a first image component when a ratio of said total width to said total height is less than about 0.60;

instructions for selecting a second image component when a ratio of said total width to said total height is greater than about 2.0; and

instructions for selecting a third image component when said first image and said second image component is not selected.

60. The computer system of

claim 58

, wherein said image component is selected based on said function as well as a number of elements in said scaled set of elements.

61. A method of adding a cross street and a cross street label that is associated with said cross street to a route map having a main path, the method comprising:

determining an intersection point at which said cross street intersects said main path;

placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point;

positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point;

adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path;

perturbing said first or said second test position by an amount;

obtaining a score of a function that is determined by a location of said cross street and said cross street label in said route map;

repeating said perturbing and obtaining steps until said score reaches a threshold value or said perturbing and obtaining steps have been executed a predetermined number of times;

wherein;

said cross street and said cross street label is added to said route map when said score reaches said threshold value; and

said cross street and said cross street label is not added to said route map when said perturbing, obtaining and determining steps have been executed said predetermined number of times and said score does not reach said threshold value.

62. The method of

claim 61

, wherein said function that is determined by a location of said cross street and said cross street label in said route map comprises:

a first component that is determined by a distance between said first test position and said intersection point;

a second component that is determined by a number of objects in said map that overlap said cross street or said cross street label;

wherein an amount that an intersecting object contributes to said second component is weighted by a degree of overlap between said overlapping object and said cross street or said cross street label; and

a third component that is determined by an amount of visual clutter.

63. The method of

claim 62

wherein said amount of visual clutter is determined by:

rendering a pixel based image of said route map;

choosing a focus region in said pixel based image that includes said cross street; and

convolving said focus region with a Guassian kernel using a luminance value of each pixel in said focus region.

64. The method of

claim 62

wherein said amount of visual clutter is determined by:

rendering a pixel based image of said route map;

choosing a focus region in said pixel based image that includes said cross street;

computing an area for each object in said focus region; and

weighting each computed area by (i), multiplying said area by an average luminance of the object that corresponds to the area and (ii), dividing said area by a distance between the object that corresponds to said area and a center of said focus region;

wherein said amount of visual clutter is a sum of each weighted area in said focus region.

65. The method of

claim 62

, said perturbing step further including an option to toggle said cross street between a hidden state and a visible state;

wherein one of said option to toggle, perturbation of said first test position, and perturbation of said second position is randomly selected during said perturbing step; and

said function that is determined by a location of said cross street and said cross street label includes a fourth component that serves as a penalty when said cross street is in said hidden state.

66. A method of adding a set of cross streets and corresponding cross street labels to a route map having a main path, the method comprising:

for each cross street in said set of cross streets and corresponding cross street labels;

determining an intersection point at which said cross street intersects said main path;

placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point;

positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point; and

adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path;

the method further comprising;

perturbing a cross street randomly selected from said set of cross streets by adjusting said first or said second test position corresponding to said cross street by a random amount;

obtaining a score of a function that is determined by a location of each cross street and corresponding cross street label in said set of cross streets and corresponding cross street labels;

determining whether to accept a change made during said perturbing step based on said score of said function in accordance with a search algorithm; and

repeating said perturbing, obtaining and determining steps until said score reaches a threshold value or said perturbing, obtaining and determining steps have been executed a predetermined number of times.

67. The method of

claim 66

, wherein said function that is determined by a location of each cross street and corresponding cross street label in said set of cross streets and corresponding cross street labels comprises:

a first component that is determined by a combination of a set of distances;

each distance in said set of distances determined by a difference in a first test position, which is associated with a different cross street in said set of cross streets, and an intersection point that corresponds to said different cross street;

a second component that is determined by a number of objects in said route map that overlap a cross street or cross street label in said set of cross streets and corresponding cross street labels;

wherein an amount that an intersecting object contributes to said second component is weighted by a degree of overlap between said overlapping object and said cross street or said cross street label; and

a third component that is determined by an amount of visual clutter in said route map.

68. The method of

claim 67

wherein said amount of visual clutter is determined by:

rendering a pixel based image of said route map; and

convolving said pixel based image with a Guassian kernel using a luminance value of each pixel in said pixel based image.

69. The method of

claim 67

wherein said amount of visual clutter is determined by:

rendering a pixel based image of said route map;

computing an area for each object in said pixel based image; and

weighting each computed area by (i), multiplying said area by an average luminance of the object that corresponds to the area and (ii), dividing said area by a distance between the object that corresponds to said area and a center of said focus region;

wherein said amount of visual clutter is a sum of each weighted area in said pixel based image.

70. The method of

claim 66

, said perturbing step further including an option to toggle said cross street between a hidden state and a visible state;

wherein one of (i) said option to toggle, (ii) perturbation of said first test position, and (iii) perturbation of said second position is randomly selected during said perturbing step; and

said function that is determined by a location of each cross street and corresponding cross street label in said set of cross streets and corresponding cross street labels includes a fourth component that serves as a penalty for each cross street in a hidden state.

71. The method of

claim 66

, wherein said search algorithm is selected from the group consisting of simulated annealing, adaptive simulated annealing, a Tabu search, A*, IDA*, a genetic algorithm, a greedy search, gradient descent, and a random walk.

72. A method of preparing a route map that describes a path between a start and an end, comprising:

obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

creating a rendering of each element in said scaled set of elements to form an intermediate map;

identifying a set of N breakpoints in said intermediate map, each breakpoint in said set of N breakpoints occurring in an element in said scaled set of elements, and a minimum value for N is determined by the expression;

N>

=S/M

where,

S is a number of elements in said scaled set of elements; and

M is a predetermined maximum number of elements; and

splitting said intermediate map into a set of N segment maps, each segment map including a different breakpoint, the set of N segment maps thereby comprising said route map.

73. The method of

claim 72

wherein said rendering of each element in said scaled set of elements is not altered when said intermediate map is split into said set of N segment maps.

74. The method of

claim 72

wherein each breakpoint in said set of N breakpoints is characterized by a different connection point icon.

75. A method of preparing an inset for a route map that describes a portion of a path between a start and an end, comprising:

obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

creating a first rendering of each element in said scaled set of elements to form said route map;

identifying a set of contiguous elements that is a subset of said scaled set of elements;

wherein said set of contiguous elements (i) include a false intersection, (ii) are relatively short compared to other elements in said scaled set of elements or, (iii) are substantially longer than corresponding elements in said initial set of elements;

producing a second rendering of each element in said set of contiguous elements to form said inset, wherein a scale of said second rendering is larger than a scale of a portion of said first rendering that corresponds to said second rendering.

76. 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, comprising:

a map preparation module for preparing a route map that describes a path between a start and an end optimizing a display of a route map, including;

instructions for obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

instructions for independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

instructions for creating a rendering of each element in said scaled set of elements to form an intermediate map;

instructions for identifying a set of N breakpoints in said intermediate map, each breakpoint in said set of N breakpoints occurring in an element in said scaled set of elements, and a minimum value for N is determined by the expression;

N>

=S/M

where,

S is a number of elements in said scaled set of elements; and

M is a predetermined maximum number of elements; and

instructions for splitting said intermediate map into a set of N segment maps, each segment map including a different breakpoint, the set of N segment maps thereby comprising said route map.

77. The computer program product of

claim 76

wherein said rendering of each element in said scaled set of elements is not altered when said intermediate map is split into said set of N segment maps.

78. The computer program product of

claim 76

wherein each breakpoint in said set of N breakpoints is characterized by a different connection point icon.

79. 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, comprising:

a map preparation module for preparing a route map that describes a path between a start and an end optimizing a display of a route map, including;

instructions for obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

instructions for independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

instructions for creating a first rendering of each element in said scaled set of elements to form said route map;

instructions for identifying a set of contiguous elements that is a subset of said scaled set of elements;

wherein said set of contiguous elements (i) include a false intersection, (ii) are relatively short compared to other elements in said scaled set of elements or, (iii) are substantially longer than corresponding elements in said initial set of elements; and

instructions for producing a second rendering of each element in said set of contiguous elements to form said inset, wherein a scale of said second rendering is larger than a scale of a portion of said first rendering that corresponds to said second rendering.

80. 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 obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

instructions for independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

instructions for creating a rendering of each element in said scaled set of elements to form an intermediate map;

instructions for identifying a set of N breakpoints in said intermediate map, each breakpoint in said set of N breakpoints occurring in an element in said scaled set of elements, and a minimum value for N is determined by the expression;

N>

=S/M

where,

S is a number of elements in said scaled set of elements; and

M is a predetermined maximum number of elements; and

instructions for splitting said intermediate map into a set of N segment maps, each segment map including a different breakpoint, the set of N segment maps thereby comprising said route map.

81. The computer system of

claim 80

wherein said rendering of each element in said scaled set of elements is not altered when said intermediate map is split into said set of N segment maps.

82. The computer system of

claim 80

wherein each breakpoint in said set of N breakpoints is characterized by a different connection point icon.

83. 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 obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

instructions for independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

instructions for creating a first rendering of each element in said scaled set of elements to form said route map;

instructions for identifying a set of contiguous elements that is a subset of said scaled set of elements;

wherein said set of contiguous elements (i) include a false intersection, (ii) are relatively short compared to other elements in said scaled set of elements or, (iii) are substantially longer than corresponding elements in said initial set of elements; and

instructions for producing a second rendering of each element in said set of contiguous elements to form said inset, wherein a scale of said second rendering is larger than a scale of a portion of said first rendering that corresponds to said second rendering.

84. A method of simplifying a road in a route map, comprising:

approximating said road as a piecewise linear curve that includes a plurality of shape points, each shape point in said plurality of shape points connected by a linear segment to a different shape point in said plurality of shape points;

adding at least one point at which said road intersects another road in said route map to said plurality of shape points as an intersection point;

marking each shape point in said plurality of shape points that is (i) not a first shape point, (ii) a last shape point, or (iii) an intersection point;

checking for false intersections between said road and another road in said route map and, when a false intersection is found, a first marked shape point and a last marked shape point in said plurality of shape points is unmarked; and

repeating said checking step until no false intersection is found or there is no marked shape point in said plurality of shape points;

wherein;

when a shape point is marked, said piecewise linear curve is modified by replacing said marked shape point and each said linear segment connected to said marked shape point with a new linear segment that originates at a shape point or intersection point immediately proceeding said marked shape point and ends with a shape point or intersection point immediately succeeding said marked shape point; and

when a shape point is unmarked, said piecewise linear curve is modified by replacing the new linear segment associated with said shape point with (i) a first linear segment that is bounded by said shape point or intersection point immediately proceeding said marked shape point and said shape point and (ii) a second linear segment that is bounded by said shape point or intersection point succeeding said marked shape point and said shape point;

said piecewise linear curve thereby representing a smoothed road that corresponds to said road in said route map.

85. The method of

claim 84

, further comprising:

forming a first vector from a shape point immediately proceeding a marked shape point in said plurality of shape points to said marked shape point;

generating a second vector between said shape point immediately proceeding said marked shape point and a last shape point in said plurality of shape points; and

comparing said first vector and said second vector, wherein, when said first and said second vector are not within a predetermined number of degrees of each other, said shape point is unmarked.

86. The method of

claim 85

, wherein said predetermined number of degrees is 180.

87. The method of

claim 85

, wherein said forming, generating, and comparing steps are repeated for each marked shape point in said plurality of shape points.

88. The method of

claim 84

, further comprising:

forming a first vector from a first shape point to a marked shape point in said plurality of shape points;

generating a second vector between said marked shape point and a last shape point in said plurality of shape points; and

comparing said first vector and said second vector, wherein, when said first and said second vectors are not within a predetermined number of degrees of each other, said shape point is unmarked.

89. The method of

claim 88

, wherein said forming, generating, and comparing steps are repeated for each marked shape point in said plurality of shape points.

90. A method of simplifying a ramp in a route map, comprising:

approximating said ramp as a piecewise linear curve that includes a plurality of shape points, each shape point in said plurality of shape points connected by a linear segment to a different shape point in said plurality of shape points;

computing a relevance for a shape point in said plurality of shape points;

wherein, when said relevance for said shape point falls below a tolerance, said shape point is marked and said piecewise linear curve is modified by replacing said marked shape point and each said linear segment connected to said marked shape point with a new linear segment that originates at a shape point immediately proceeding said marked shape point and ends with a shape point immediately succeeding said marked shape point, said new linear segment thereby representing said marked shape point; and

said piecewise linear curve thereby representing a smoothed ramp that corresponds to said ramp in said route map.

91. The method of

claim 90

wherein said relevance is determined by the expression:

99. The computer program product of

claim 90

wherein said relevance is determined by the expression:

92. 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 road simplification module for simplifying a road in a route map, the road simplifying module including;

instructions for approximating said road as a piecewise linear curve that includes a plurality of shape points, each shape point in said plurality of shape points connected by a linear segment to a different shape point in said plurality of shape points;

instructions for adding at least one point at which said road intersects another road in said route map to said plurality of shape points as an intersection point;

instructions for marking each shape point in said plurality of shape points that is (i) not a first shape point, (ii) a last shape point, or (iii) an intersection point;

instructions for checking for false intersections between said road and another road in said route map and, when a false intersection is found, a first marked shape point and a last marked shape point in said plurality of shape points is unmarked; and

instructions for repeating said instructions for checking until no false intersection is found or there is no marked shape point in said plurality of shape points;

wherein;

when a shape point is marked, said road simplifying module further includes instructions for modifying said piecewise linear curve by replacing said marked shape point and each said linear segment connected to said marked shape point with a new linear segment that originates at a shape point or intersection point immediately proceeding said marked shape point and ends with a shape point or intersection point immediately succeeding said marked shape point; and

when a shape point is unmarked, said road simplifying module further includes instructions for modifying said piecewise linear curve by replacing the new linear segment associated with said shape point with (i) a first linear segment that is bounded by said shape point or intersection point immediately proceeding said marked shape point and said shape point and (ii) a second linear segment that is bounded by said shape point or intersection point succeeding said marked shape point and said shape point.

93. The computer program product of

claim 92

, said road simplifying module further comprising:

instructions for forming a first vector from a shape point immediately proceeding a marked shape point in said plurality of shape points to said marked shape point;

instructions for generating a second vector between said shape point immediately proceeding said marked shape point and a last shape point in said plurality of shape points; and

instructions for comparing said first vector and said second vector, wherein, when said first and said second vector are not within a predetermined number of degrees of each other, said shape point is unmarked.

94. The computer program product of

claim 93

, wherein said predetermined number of degrees is 180.

95. The computer program product of

claim 93

, wherein said instructions for forming, instructions for generating, and instructions for comparing steps are repeated for each marked shape point in said plurality of shape points.

96. The computer program product of

claim 92

, said road simplifying module further comprising:

instructions for forming a first vector from a first shape point to a marked shape point in said plurality of shape points;

instructions for generating a second vector between said marked shape point and a last shape point in said plurality of shape points; and

instructions for comparing said first vector and said second vector, wherein, when said first and said second vectors are not within a predetermined number of degrees of each other, said shape point is unmarked.

97. The computer program product of

claim 92

, wherein said instructions for forming, generating, and comparing are repeated for each marked shape point in said plurality of shape points.

98. 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 ramp simplification module for simplifying a ramp in a route map, the ramp simplification module including;

instructions for approximating said ramp as a piecewise linear curve that includes a plurality of shape points, each shape point in said plurality of shape points connected by a linear segment to a different shape point in said plurality of shape points;

instructions for computing a relevance for a shape point in said plurality of shape points;

wherein, when said relevance for said shape point falls below a tolerance, said shape point is marked and said piecewise linear curve is modified by replacing said marked shape point and each said linear segment connected to said marked shape point with a new linear segment that originates at a shape point immediately proceeding said marked shape point and ends with a shape point immediately succeeding said marked shape point, said new linear segment thereby representing said marked shape point.

100. 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 including;

instructions for approximating said road as a piecewise linear curve that includes a plurality of shape points, each shape point in said plurality of shape points connected by a linear segment to a different shape point in said plurality of shape points;

instructions for adding at least one point at which said road intersects another road in said route map to said plurality of shape points as an intersection point;

instructions for marking each shape point in said plurality of shape points that is (i) not a first shape point, (ii) a last shape point, or (iii) an intersection point;

instructions for checking for false intersections between said road and another road in said route map and, when a false intersection is found, a first marked shape point and a last marked shape point in said plurality of shape points is unmarked; and

instructions for repeating said instructions for checking until no false intersection is found or there is no marked shape point in said plurality of shape points;

wherein;

when a shape point is marked, said road simplification module further includes instructions for modifying said piecewise linear curve by replacing said marked shape point and each said linear segment connected to said marked shape point with a new linear segment that originates at a shape point or intersection point immediately proceeding said marked shape point and ends with a shape point or intersection point immediately succeeding said marked shape point; and

when a shape point is unmarked, said road simplification module further includes instructions for modifying said piecewise linear curve by replacing the new linear segment associated with said shape point with (i) a first linear segment that is bounded by said shape point or intersection point immediately proceeding said marked shape point and said shape point and (ii) a second linear segment that is bounded by said shape point or intersection point succeeding said marked shape point and said shape point.

101. The computer system of

claim 100

, said road simplification module further comprising:

instructions for forming a first vector from a shape point immediately proceeding a marked shape point in said plurality of shape points to said marked shape point;

instructions for generating a second vector between said shape point immediately proceeding said marked shape point and a last shape point in said plurality of shape points; and

instructions for comparing said first vector and said second vector, wherein, when said first and said second vector are not within a predetermined number of degrees of each other, said shape point is unmarked.

102. The computer system of

claim 101

, wherein said predetermined number of degrees is 180.

103. The computer system of

claim 101

, wherein said instructions for forming, generating, and comparing are repeated for each marked shape point in said plurality of shape points.

104. The computer system of

claim 100

, said road simplification module further comprising:

instructions for forming a first vector from a first shape point to a marked shape point in said plurality of shape points;

instructions for generating a second vector between said marked shape point and a last shape point in said plurality of shape points; and

instructions for comparing said first vector and said second vector, wherein , when said first and said second vectors are not within a predetermined number of degrees of each other, said shape point is unmarked.

105. The computer system of

claim 100

, wherein said instructions for forming, generating, and comparing are repeated for each marked shape point in said plurality of shape points.

106. 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 for simplifying a ramp in a route map, said program module executable by said central processing unit and including;

instructions for approximating said ramp as a piecewise linear curve that includes a plurality of shape points, each shape point in said plurality of shape points connected by a linear segment to a different shape point in said plurality of shape points;

instructions for computing a relevance for a shape point in said plurality of shape points;

wherein, when said relevance for said shape point falls below a tolerance, said shape point is marked and said piecewise linear curve is modified by replacing said marked shape point and each said linear segment connected to said marked shape point with a new linear segment that originates at a shape point immediately proceeding said marked shape point and ends with a shape point immediately succeeding said marked shape point, said new linear segment thereby representing said marked shape point.

107. The computer system of

claim 106

wherein said relevance is determined by the expression:

108. A method of preparing a route map that describes a path between a start and an end, said method comprising:

obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

refining at least one said different scale factor against a target function, a score resulting from application of said target function during said refining determined by at least one factor selected from the from the group consisting of (i) presence of a false intersection in said scaled set of elements and (ii) occurrence of a condition in which there is an intersection in said initial set of elements that has no corresponding intersection in said scaled set of elements; and

outputting a rendering of each element in said scaled set of elements.

109. A method of preparing a route map that describes a path between a start and an end, said method comprising:

obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

refining at least one said different scale factor using a search-based refinement algorithm selected from the group consisting of simulated annealing, adaptive simulated annealing, a Tabu search, A*, IDA*, a genetic algorithm, a greedy search, gradient descent, and a random walk; and

outputting a rendering of each element in said scaled set of elements to form said route map.

110. A method of preparing a route map that describes a path between a start and an end, said method comprising:

obtaining said path from said start to said end, said path comprising an initial set of elements, each said element including sufficient information to determine a direction and each said element intersecting at least one other element in said initial set of elements;

a first element in said initial set of elements including said start and a second element in said initial set of elements including said end;

independently applying a different scale factor to each of at least two elements in said initial set of elements;

wherein application of said different scale factor to each of said at least two elements produces a scaled set of elements;

assigning a plurality of labels to respective label positions so that each label in said plurality of labels is proximal to a corresponding element in said scaled set of elements; and

refining each said respective label position against a target function to form a plurality of refined label positions; and

outputting a rendering of each element in said scaled set of elements as well as said plurality of labels at said refined label positions to form said route map.

111. The method of

claim 110

wherein said refining step is conducted using a search-based algorithm selected from the group consisting of simulated annealing, adaptive simulated annealing, a Tabu search, A*, IDA*, a genetic algorithm, a greedy search, gradient descent, and a random walk.