System and method for non-uniform scaled mapping

ES 2 373 095 T3

DESCRIPTION

System and procedure for the abstraction and visualization of a road map

The present disclosure generally refers to a system and procedure for generating a road map. More particularly the invention relates to a system and a method for applying a unique scale factor to each of the roads on a route map and for optimizing the positions of the labels on the route map. In addition, a procedure to represent the appearance of roads on the road map is disclosed.

Background

Route maps, when well designed, are an effective device for displaying and communicating directions. Such maps have existed in various forms for centuries, and the recent availability of detailed geographic databases via the Internet has led to the wide use of computer-generated route maps. Online mapping services typically provide directions as a set of maps supplemented with text descriptions. However, such online computer generated maps are not satisfactory, because the algorithms used to generate the maps ignore many of the techniques and principles used by cartographers.

Effective use of a route map generally requires two distinct activities: (i) following a road until a critical point is reached, and (ii) changing orientation at that point to follow another road. Thus, one of the most important types of information that route maps can communicate are reorientation points, that is, points along the route where someone must consciously turn from one road to another. However, existing computer generated route maps fail to communicate effectively the reorientation points because they scale all the roads on the map by a constant scale factor. Scaling of roads on a route map with a constant scaling factor is referred to herein as uniform scaling. As a result of uniform scaling, for routes of any reasonable length, uniform scaling often requires some roads to be very short. But often it is precisely these very short roads that connect critical turning points. Thus uniform scaling can result in a loss of some of the most critical information found on a roadmap.

Another shortcoming in prior art computer generated route maps is that they unnecessarily represent the precise length, angle and curvature of each of the roads on the route. Such accurate representations are made at the expense of the readability of the map. Psychological research indicates that most people distort distances, angles, and curvatures when drawing road maps. See, for example, How Space Structures Language by Tversky and Lee, Spatial Cognition: An Interdisciplinary Approach to the Representation and Processing of Spatial Knowledge (eds.) Freska, Habel, and Wender, 1998, 157-175; Pictorial and Verbal Tools for Driving Routes, by Tversky and Lee, COSIT 99, Procedural Conference, Stade, Germany 1999, 51-64. Other psychological studies indicate that people maintain such distortions in their own mental representations of a route. See for example Tversky's Distortions in Cognitive Maps, Geoforum 23, 1992, 131-138. Thus, adherence to precise lengths and angles in prior art computer generated maps works against how people conceptualize routes.

Computer generated route maps can be classified into four main mapping styles: route enhancement maps, overview / detail trip planning maps (Trip Tik), and two-dimensional nonlinear distortion maps. Route enhancement maps simply highlight the route on a general road map of the region, as shown in FIG. 1. Since the purpose of general road maps is to provide an understanding of the entire road system in a region, such maps typically employ constant scale factors and represent unusual details throughout the map. Constant scaling as shown in FIG. 1, generally causes one of two problems. Either detailed turn information is lost because the scale factor is too large, or the scale factor is small enough to show detail, but the map is too large. As general road maps are not optimized to show any particular route, an enhanced road map will often suffer from both the large scale factor and the downside of size. The clarity of the route on a route highlight map depends on the highlight style as it is the only property that differentiates the route from other roads. Usually the route is colored differently, but because general road maps provide context information about the entire map, the map is cluttered with extraneous information that makes it difficult to perceive the route and particular reorientation points.

Trip Tik maps are similar to route enhancement maps, but they are specially designed to communicate a particular route. As shown in FIG. 2, a Trip Tik map is usually spread over multiple rectangular pages, and each page is oriented so that the path runs roughly down the center of the page. Each of the Trip Tik pages employs constant scaling, but the scaling factor differs across pages. Changing the scale factor from page to page allows Trip Tik to display turn information in greater detail when needed. But nevertheless,

ES 2 373 095 T3 as the map is spread over many pages and the orientation and scale factor varies from page to page, it is difficult to form a general understanding of the overall route.

Overview / detail maps combine multiple maps displayed at different scales to present a single route, as shown in FIG. 3. One of the maps (eg FIG. 3A) is scaled by a large factor so that it provides an overview of the entire route. Since a large scale factor reduces the readability of local turn details, maps are provided showing turn-by-turn information (eg, FIG. 3B). A constant scale factor is used for each of the maps, but the scale factor differs between maps. Although an overview / detail map may seem like an effective combination, such maps are not satisfactory in practice. The overview map rarely presents more than the overall direction and context of the route. Although maps provide detailed turn-by-turn information for each turn, the use of different maps for each turn, often with different orientations and scales, makes it difficult to understand how the maps correspond to each other. Therefore, the navigator has difficulty in forming the cognitive model of the route.

Another route representation technique is described in US 5,945,927, describing a bird's eye view of a road map surrounding the current position of a vehicle in which a point of view is placed at a predetermined position on the sky in a direction opposite to the destination set with the present position of the vehicle for reference and has a line of sight that looks down on the road map so that the part of the road map that surrounds the present vehicle position can be seen as a scale enlarged and the remaining part of the remote road map from the present position and closer to the set destination can be seen in a gradually decreasing scale shape.

To ensure clear communication of all reorder points, some parts of a route representation may require a small scale factor while others require a large scale factor. Researchers have described attempts to use two-dimensional nonlinear image distortion techniques on general road maps to provide a more contextual view of, approach (See, for example, Flexible Three-Dimensional Surfaces: For the Effective Presentation of Information Visual de Carpendale et al. Proceedings of the ACM Symposium on User Interface Software and Technology, UIST 95, 1995, 217-226; Keahey's Problem of Generalized Detail in Context, Proceedings of the IEEE Symposium on Information Visualization, IEEE Visualization 1998). These techniques allow users to choose regions of the map that they want to focus on and then apply non-linear magnification, such as spherical distortion, to magnify these focused regions. Such a two-dimensional distortion allows detailed information to be represented only where it is relevant and often produces general maps of the area that can be conveniently rendered on a single page. However, the main problem with non-linear two-dimensional distortion is that the edge regions between the magnified and non-magnified portions of the map suffer extreme distortion.

In an effective route map, all essential components of the route, especially the roads, are easily identifiable. The route is clearly marked and is easily apparent even at a glance. The map contains only as much information as is necessary and is easy to transport and manipulate. As additional goals of such a design, the content of the maps, the accuracy, and the presentation style must be carefully optimized. The content of the maps includes important parameters such as the beginning and end of the route, as well as the reorientation points. Although all maps are abstract representations of a route, there are a range of styles that can be used to represent a map, with associations varying in precision and realism. An appropriate presentation style can greatly affect the readability and clarity of a map. Retina properties such as line color and thickness are used to draw attention to important features on the map. The presentation style can also help the user in interpreting how closely the map corresponds to the real world. Another important goal of map design is the proper use of context information. The amount of context information included in the map greatly affects the usefulness of the map. Useful context information includes labels or names for a road on the route as well as context information along the route such as buildings, traffic lights, or stop signs. When drawing a road map by hand, most people commonly use contextual information to indicate reorientation points and, less frequently, to communicate progress along a road.

Environmental psychological studies have shown that human-generated route maps contain distortion, there are three main types of distortion: (1) imprecise road lengths, (2) incorrect turning angles and intersections, and (3) road shape simplified. For example Tversky and Lee, COSIT 99 Proceedings Conference, 1999, 51-64 asked a group of students to sketch a road map between two locations near the Stanford University campus. Although he encouraged the participants in his study to represent roads and intersections accurately, most did not. Most of the intersections were drawn at right angles regardless of their actual angle, and 71 percent of the participants used simple generic curves and straight lines to represent the roads. Even when participants tried to communicate the shape or length of the road accurately, they typically misrepresented these attributes. Such distortion in the map is indeed beneficial in that it increases the flexibility available to the map maker in designing and plotting the map. Variable scaling of the length of

ES 2 373 095 T3 each of the roads allows the map maker to ensure that all reordering points are visible, although the flexibility in the choice of turning angles and the curvature of the road allows to simplify the map. Such distortions can simultaneously improve the readability and convenience of the roadmap with little adverse effect on its clarity and completion.

Hand-drawn road maps often feature a good combination of readability, clarity, completion, and convenience, as shown in FIG. 4. Instead of using a constant scale factor, hand-drawn maps only maintain the relative ordering of roads by length. Although this ensures that the longer roads appear longer than the shorter roads on the map, each of the roads is scaled by a different factor. Often the map designer does not know the exact length of the roads and only knows their lengths relative to each other. The flexibility of relative scaling allows hand-drawn maps to fit within a manageable size and remain legible.

Hand-drawn route maps typically remove most of the contextual information not found directly along the route. This strategy reduces overall clutter and improves clarity. The intersection angles on hand-drawn maps are generally incorrect, the precise shape of roads is often poorly represented, and roads are typically rendered as generic straight or curved lines. These distortions make the map simpler and only remove unnecessary information. The hand-drawn route maps are presented in a typical sketchy pen and ink scribble style. Many navigators are familiar with such hand-drawn maps and the sketchy style is a subtle indicator of map inaccuracy.

To improve roadmap clarity, many algorithms have been developed to smooth, interpolate, and simplify roads on a roadmap. In the area of ​​map representation, the best-known simplification algorithms are the Algorithms for reducing the number of points required to represent a digitized line or its cartoon by Douglas & Peucker, the Canadian Cartographer 10 (2), 1973, 112- 22; An iterative approach to the polygonal approximation of closed plane Ramer curves, Computer Graphics and Image Processing. 1, 1972, 244-56; Generalization of lines by repeated elimination of points from Visvalingam & Whyatt, Journal of Cartography. 30 (1), 1993, 46-51; and Map Outlining: Simplification of Geographic Shape by Revolution of Discrete Curves by Barkowsky, Latecki, and Richter, in Freksa, Brauer, Talk, and Wender (eds.): Spatial Cognition II, Springer-Verlag, Berlin, in press. Given a piecewise curved line as a set of shape points, all of these procedures remove a subset of the shape points to produce a simpler curve. Examples of shape points 3302 and pivot points 3306 are provided in FIG. 33A. Each of these procedures uses different criteria / metrics to decide which form points to remove and which to retain. As roads become simpler, both the perception benefits and the processing speed increase. The most extreme form of simplification replaces the piecewise line road with a single line segment from the first point of the shape to the last point of the shape. Although this extreme approach produces a good approximation in most cases, it can cause the map to become erroneous. Prior art algorithms for simplifying roads on a road map can generate three types of undesirable results:

(i) False Intersections. Roads that were not crossed before the simplification are falsely crossed after the simplification. An example of false intersection 3310 is found in FIG. 33A.

(ii) Loss of Intersections. Roads that were crossed before the simplification no longer intersect after the simplification. An example of intersection loss 3312 is found in FIG. 33B.

(iii) Inconsistent Turning Angles: The turning angle between roads can change substantially, even to the point that a left turn can appear as a right turn. An example of wrong turning angle 3314 is found in FIG. 33C.

Based on the foregoing background it is clear that an improved system and method for making computer generated maps is necessary in the art. There is also a need in the art for a computer generated mapping system and method that avoids the difficulties encountered in existing mapping algorithms, such as the use of extraneous information and constant scaling.

Summary of the invention

The present invention provides an improved system and method for making computer generated maps as defined in the appended claims. In the present invention, each of the roads on a route is scaled individually. The scale factor for each of the roads is optimized using an objective function that considers various factors such as the number of false intersections and the number of roads that are shorter than a minimum threshold length. In this way, the climbed route enters a predetermined viewing region without loss of information about important turns. Refinement against the objective function is performed by one of many possible search algorithms such as greedy searches, simulated annealing programs, or gradient runs. Greedy search algorithms are described in the Introduction to Algorithms by Cormen et al., Eds. Cormen, Leiserson, & Rivest, The MIT Press, Cambridge, Massachusetts, 1990, 329-355. Simulated annealing was first revealed by Kirkpatrick and

ES 2 373 095 T3 others, in the article Optimization by Simulated Annealing. Science 220, 1983, 671-680. Unlike prior art procedures, some embodiments of the present invention provide simplification algorithms that ensure that problems such as false intersections, missed intersections, and inconsistent turn angles in the final scaled roadmap do not occur. .

Map clutter is eliminated on the scaled map by refining the label positions against a new objective function that minimizes the number of roads that the labels intersect, the number of labels that intersect each other, and the distance along the path between a label and the center of a road that corresponds to the label. In one embodiment, simulated annealing is used to find a solution to the new objective function. The final scaled route map is laid out to look like a hand-drawn map. The clearly rendered map communicates each reorientation point in a readable and convenient way.

An embodiment of the present invention provides a method of rotating the route map for the best fit of the screen aspect ratio. In this procedure, you define a collection of waypoints on the route map. Each of the waypoints in the collection corresponds to a position of an intersection on the route map. The collection of the reference points forms a distribution in a two-dimensional space. Therefore, they can be fitted with a probability distribution function that defines the mean position of the reference point collection in two-dimensional space as well as the furthest position in which a member of the reference point collection is located. extends in a first direction away from the middle position (for example, a first extension) as well as the farthest position to which a member of the reference point collection extends in a direction that is orthogonal to the vector between the middle position and the position of the first extension (i.e., a second extension). The first mean extent and the second extent provide a description of the outer boundary of the reference points and a bounding box is calculated denoting this outer boundary. The bounding box is centered on the middle position and the sides of the bounding box are determined by the positions of the first extent and the second extent. The orientation of the bounding box is determined by the vector between the middle position and the position of the first extent. Based on this orientation, the route map is rotated an amount that is sufficient to reorient the bounding box in a predetermined orientation, thereby forming a rotated route map. A portion of the rotated route map is presented below, thereby optimizing the representation of the route map.

Another embodiment of the present invention provides a method for placing an annotation or label on a route map. In the procedure, the roadmap is divided into an initial grid. The grid is made up of cells in the grid. The candidate cells of the grid are identified, within which the annotation or label can be placed. Each of the candidate cells in the grid is free of objects associated with the roadmap. When the annotation or label does not fit in a single candidate cell in the grid, a search is conducted for cells in the grid that have enough adjacent grid cells free of objects. This search is subject to the requirement that the candidate grid cell, and one or more of the adjacent grid cells free of objects, must be able to accommodate the annotation or label. When no candidate cell of the grid is found during the identification or search steps, a grid subdivision scheme is performed. The grid subdivision scheme subdivides a portion of the grid cells, into the initial grid, to form a new grid. The identification and search steps are then repeated using the new grid. When multiple candidate grid cells are found, each candidate grid cell is scored based on the density of objects in the grid cells bordering each candidate grid cell. The candidate cell in the grid that borders cells in the grid that have the lowest density of objects is selected as the candidate cell in the grid, and the other candidate cells in the grid are discarded. The annotation or label is positioned in the candidate cell of the grid, thereby placing the annotation or label on the roadmap.

In another embodiment of the present invention, a plurality of labels are positioned on a route map. For each of the labels in the plurality of labels, the following steps are performed:

(i) A plurality of constraint definitions are associated with the tag. Each of the constraint definitions in the plurality of constraint definitions uniquely defines a bounding box, label orientation, and layout style.

(ii) An initial constraint definition is selected from the plurality of constraint definitions.

(iii) a center of the label is positioned at a location within the bounding box defined by the initial constraint definition in accordance with the orientation of the label and the layout style defined by the initial constraint definition.

The method further comprises choosing a label from the plurality of labels and determining a first score (S1) using an objective function. The objective function is determined by the position of the chosen label on the road map. The constraint definition is then selected from the plurality of constraint definitions associated with the selected tag. The selected constraint definition is applied below. The application of the definition of constraint includes the stage of repositioning the center of the

ES 2 373 095 T3 label inside the bounding box defined by the restriction definition, according to the orientation of the label and the layout style defined by the restriction definition. A second score (S2) is calculated using an objective function that considers the position of the repositioned label. The new position for the label is accepted according to a function that is determined by a comparison of S1 and S2. The stages of choice, determination, application, calculation and acceptance are repeated until a first occurrence of the exit condition occurs. Exemplary exit conditions include the achievement of a suitable low score or the occurrence of a predetermined number of repetitions of the steps of choosing, determining, applying, calculating, and accepting.

Yet another embodiment of the present invention provides a method of preparing a route map that describes a trajectory between a beginning and an end. In this procedure, the trajectory is obtained from the beginning to the end. The trajectory comprises an initial set of elements. Each of the items includes enough information to determine an address. Also, each element cuts at least one other element in the initial set of elements. A first element in the initial set of elements includes a beginning element and a second element in the set includes the end. A different burst factor is applied independently to each of the at least two elements in the initial set of elements. Applying the different scale factor to each of the at least two elements produces a scaled set of elements. The total height and total width of the representation of each of the elements in the scaled set of elements is estimated. An image component is then selected based on a function of the total height and the total width. Finally, an image of the scaled roadmap is formed representing each of the items in the scaled set of items.

Another embodiment of the present invention includes a method of adding a crossing street, and a label of the crossing street associated with the crossing street, to a route map that includes a major road. In the procedure, an intersection point is determined at which the crossing street intersects the main road. The crossing street is placed on the road map with the restriction that the crossing street intersects the main road at a first test position that is randomly chosen from a segment of the main road that includes the point of intersection. The label of the crossing street is positioned in a second test position within a predetermined area. The default area includes the intersection point. The length of the crossing street is adjusted so that the crossing street passes under the label of the crossing street and intersects the main road. The first or second test position is disturbed by a random amount and a score is obtained from a function, that is, a scoring function. The size of the random amount used to disturb the first or second test positions is typically a small magnification that is designed to see if a pinch in the first or second test positions leads to an improved score. However, sometimes the size of the random quantity used to disturb the first or second test positions is considerably larger, to prevent the scoring function from being trapped in a local minimum. The scoring function is determined by the location of the crossing street and the label of the crossing street on the route map. The disturbance and obtain stages are repeated until the score reaches a threshold value or the disturbance and obtain stages have been executed a predetermined number of times. The crossing street and the crossing street label are added to the roadmap when the score reaches the threshold value. Also, the crossing street and the crossing street label are not added to the route map when the disturbance, obtain and determine steps have been executed the predetermined number of times before the score has reached the threshold value.

In yet another embodiment of the present invention, a method of preparing a route map is provided that describes a trajectory between a beginning and an end. In this procedure, the trajectory is obtained from the beginning to the end. The trajectory comprises an initial set of elements. Each of the elements includes enough information to determine a direction, and each of the elements cuts to at least one other element in the initial set of elements. A first element in the initial set of elements includes the beginning and a second element in the initial set of elements includes the end. A different scale factor is applied independently to each of the at least two elements in the initial set of elements. Applying the different scale factor to each of the at least two elements produces a scaled set of elements. A presentation of each of the elements in the scaled set of elements is created to form an intermediate map. A set of N breakpoints is identified on the intermediate map. Each of the breakpoints in the set of N breakpoints occurs at one element in the scaled set of elements, and a minimum value for N is determined by the expression:

N> S / M where,

S is the number of elements in the scaled set of elements; Y

M is the default maximum number of items.

The intermediate map is then divided into a set of N feature maps, each of the segment maps including a different breakpoint. The set of N segment maps therefore comprises the route map.

ES 2 373 095 T3

Another embodiment of the present invention provides a method for simplifying a road on a road map. In the method, the road is approximated as a piecewise curved line that includes a plurality of shape points. Each of the shape points in the plurality of shape points is marked by a line segment to a respective shape point in the plurality of shape points. At least one point where the road intersects another road on the route map is added to the plurality of shape points as an intersection point. Each point of the shape in the plurality of points of the shape is not (i) a first point of the shape, (ii) a last point of the shape, or (iii) a point of intersection. A check is made for the detection of false intersections between the road and another road on the route map and, when a false intersection is found, the first point of the marked shape and the last point of the shape marked in the plurality are unmarked dotted shape. The checking step is repeated until no false intersection is found or there is no point of the shape marked in the plurality of points of the shape. When a point on the shape is marked, the piecewise curved line is modified by replacing the marked point on the shape and each of the line segments connected to the marked point on the shape with a new line segment originating from a point on the shape. shape or intersection point immediately preceding the marked point of the shape and ends with a point of the shape or intersection point immediately after the marked point of the shape. When a point of the shape has been unmarked, the piecewise curved line is modified by replacing the new line segment associated with the point of the shape with (i) a first line segment that is delimited by the point of the shape or intersection point immediately preceding the marked point of the shape and the point of the shape and (ii) a second line segment that is delimited by the point of the shape or intersection point after the marked point of the shape and the point of the shape. Thus, the piecewise curved line represents a smoothed road corresponding to the road on said road map.

Brief description of the drawings

FIG. 1 is a prior art route highlight map.

FIG. 2 is a prior art Trip Tik map.

FIG. 3 is a General View / Detail map of the prior art.

FIG. 4 is a hand-drawn map of the prior art.

FIG. 5 is a map that is generated in accordance with an embodiment of the present invention.

FIG. 6 illustrates a system for generating a route map in accordance with one embodiment of the present invention.

FIG. 7 illustrates the processing steps used to optimize the length of individual roads on a route map using a greedy algorithm, in accordance with one embodiment of the present invention.

FIG. 8 illustrates the processing steps used to optimize the length of individual roads on a route map using a simulated annealing program, in accordance with one embodiment of the present invention.

FIG. 9 illustrates the processing steps used to optimize label positions on a route map using a simulated annealing program, in accordance with one embodiment of the present invention.

FIG. 10 illustrates a map before and after the realization of the road extensions so that the labels are optimally associated with the corresponding roads.

FIGS. 11A, 11B, and 11C illustrate the conceptual steps used to identify the longest axis of a route and to rotate this axis in a predetermined direction, in accordance with one embodiment of the present invention.

FIG. 12 illustrates a general problem of placing annotations on a road map.

FIG. 13 illustrates the processing steps associated with a solution to the general problem of placing annotations on a road map in accordance with one embodiment of the present invention.

FIG. 14 illustrates the spatial subdivision of a route map to identify regions of the route map that are suitable for the placement of annotations as well as labels.

FIG. 15 illustrates a generalized problem, which occurs in a spatial subdivision approach to placing a label or annotation in a restricted area, in which no empty grid cells can be found.

FIG. 16 illustrates how non-uniform subdivision is used to solve the problem of using spatial subdivision to place a label or annotation in a restricted area.

FIGS. 17A and 17B illustrate the use of bounding boxes and FIGS. 18A and 18C illustrate the use of vectors of

ES 2 373 095 T3 guidelines that are presented in some definitions of constraints in accordance with an embodiment of the present invention.

FIGS. 18A, 18B, 18C, 18D, 18E, and 18F illustrate various layout styles that are featured in some constraint definitions in accordance with one embodiment of the present invention.

FIG. 19 illustrates the processing steps used to optimize label positions on a road map using a simulated annealing program that includes the use of constraint definitions, in accordance with one embodiment of the present invention.

FIG. 20 provides an overview of one embodiment of a layout module 688 that makes use of expanded constraint definitions, in accordance with one embodiment of the present invention.

FIG. 21 illustrates the components of an example image and text boxes used to compose shapes, in accordance with one embodiment of the present invention.

FIGS. 22A, 22B, and 22C illustrate various forms of outlet in accordance with one embodiment of the present invention.

FIG. 23 illustrates a scaled road map with crossing streets in accordance with one embodiment of the present invention.

FIG. 24 illustrates the general problem of determining an amount of visual clutter in an image based on image points of a road map.

FIG. 25 illustrates a road map with various feature points, such as exit numbers, restaurant locations, and city names included in accordance with one embodiment of the present invention.

FIG. 26 illustrates a cluttered road map that would be difficult to use while driving.

FIG. 27 illustrates the route map of FIG. 26 divided into two segment maps which, taken together, comprise the route map of FIG. 26.

FIGS. 28A, 28B, 28C and 28D illustrate various intermediate and segment maps in accordance with one embodiment of the present invention.

FIG. 29 illustrates a route map with a corresponding insert in accordance with one embodiment of the present invention.

FIG. 30 illustrates how the use of an insert can be used to avoid the distribution of a predominantly North-South or East-West route map in accordance with one embodiment of the present invention.

FIG. 31 illustrates how the use of an insert can be used to associate readable labels with roads that do not have readable labels on a corresponding main route map, in accordance with one embodiment of the present invention.

FIG. 32A illustrates a road map before simplifying curves (roads or features) and FIG. 32B illustrates the route map of FIG. 32A after simplifying the curves, in accordance with one embodiment of the present invention.

FIGS. 33 illustrate how highway simplification can introduce false intersections (33A), missed intersections (33B), and inconsistent turning angles (33C).

FIG. 34 illustrates how a road is treated as a set of shape points into which intersection points are entered, in accordance with one embodiment of the present invention.

FIG. 35 illustrates the intersection of roads r-ι and r2 at point 3502.

FIGS. 36A and 36B respectively illustrate two different methods for identifying shape points to remove or retain roads on a road map that are not part of a ramp, in accordance with one embodiment of the present invention.

FIG 37 illustrates aspects of shape points on a ramp that are measured to assess the relevance of a particular shape point on a ramp on a route map during a simplification procedure, in accordance with one embodiment of the present invention. .

FIG. 38 illustrates shape points on a ramp on a route map, in accordance with one embodiment of the present invention.

ES 2 373 095 T3

FIG. 39 illustrates how a turn angle consistency check is performed when considering leaving a ramp from a road map, in accordance with one embodiment of the present invention.

FIGS. 40A and 40C illustrate portions of an unscaled road map while FIGS. 40B and 40D show corresponding scaled route maps illustrating respectively how scaling can lead to false intersections and intersection losses.

FIG. 41A illustrates how an intersection loss is scored and FIG. 41B illustrates how a misplaced intersection is scored in accordance with one embodiment of the present invention.

FIGS. 42A, 42B, and 42C illustrate various false intersection scenarios, showing for each of the false intersection points in which direction the closest end point must travel to eliminate the node formed by that false intersection point.

FIG. 43 illustrates a knot that is produced by a false intersection when scaling a road map.

FIGS. 44A and 44B illustrate procedures for the resolution of false intersections, in accordance with the various embodiments of the present invention.

FIGS. 45A and 45B illustrate two types of intersection loss that arise during route map scaling.

FIGS. 46A and 46B illustrate procedures for solving intersection losses, in accordance with the various embodiments of the present invention.

FIGS. 47A and 47B illustrate the utility of using extended intersections, in accordance with one embodiment of the present invention.

FIG. 48 illustrates how an extended intersection can work against the resolution of a false intersection during route map refinement.

FIG. 49 illustrates a way to determine which extended intersections to add to the refinement score, in accordance with one embodiment of the present invention.

Like reference numerals refer to corresponding parts throughout the various views of the drawings.

Detailed description of the invention

The present invention provides a system and method for generating maps that have the benefits and characteristics of a hand-drawn map. The automatic generation of roadmaps of this style is complex. Aspects of map distortion can accentuate reorientation points, but can also have detrimental effects such as introducing false intersections. Creating an effective roadmap requires searching a large space of possible map layouts for an optimal layout. An efficient multi-stage algorithm is disclosed that couples a road layout refinement module with a label and annotation placement module. The resulting map is presented using subtle perceptual cues, such as a handcrafted wavy style for drawing the tracks, to communicate scale and shape distortion.

The objectives of the design of the present invention are:

(i) Roads should be variably scaled so that all roads and reorientation points are clearly visible and easily labeled.

(ii) If road A is longer than road B, then road A should be noticeably longer than road B on the map.

(iii) The representation of a road need only drive the general curvature and significant changes in orientation.

(iv) The precise angle of the intersection of two roads is not important; instead it is sufficient to clearly communicate the action to be taken (turn to the left, turn to the right) and a generalized orientation.

(v) The beginning and the end of the route should be clearly marked.

(vi) A schematic style should be used to present a road to represent an imprecision of scale and orientation.

(vii) The resulting map should fit into the desired viewing region, such as a simple sheet of paper, a computer screen, and / or a window on a graphical user interface.

ES 2 373 095 T3

Generating a computer-based map in accordance with the design goals identified above is more difficult than generating a map in conventional computer-based styles. Variable road scaling provides some flexibility in choosing the length of each of the roads to produce a clear and legible map. However, the relative ordering of roads by length should be kept fixed and no false intersections should be introduced on the map. The space of all possible roadmap arrangements is extremely large, and therefore a blind search for an arrangement that satisfies the design goals of the present invention is not feasible. Instead, a multiphase heuristic build and test approach is used to obtain a map that satisfies the design principles of the present invention. FIG. 5 illustrates a map generated using the methods of the present invention.

General architecture

We now turn our attention to FIG. 6, which is a system according to one embodiment of the present invention. FIG. 6 illustrates a network 620 that is operated in accordance with the present invention. Network 620 includes at least one user computer 622 and at least one server computer 624. User computer 622 and server computer 624 are connected over transmission channel 626, which can be any wired or wireless transmission channel.

User computer 622 is any device that includes a Central Processing Unit (CPU) 630 connected to random access memory 650, network connection 634, and one or more user input / output (i / o) devices. 638 including output means 640. In some embodiments, system memory 650 includes read-only memory (ROM). Output means 640 is any device capable of communicating with a person and includes, for example, a monitor, voice user interfaces, and / or an integrated graphic medium such as a mini-screen present in web phones. Typically, user computer 622 includes a main non-volatile storage unit 636, preferably a hard disk controller, for storage of software and data. Furthermore, the user computer 622 includes one or more internal buses 632 for interconnection of the aforementioned elements. In a typical embodiment, memory 650 includes an operating system 652 and an internet browser 654.

In some embodiments of the present invention, user computer 622 is a handheld device such as a Palm Pilot. Accordingly, in such embodiments, the user computer 622 may have no disk 636 and the browser 654 is seamlessly integrated into the operating system 652.

The server computer 624 includes standardized server components, including a network connection device 660, a CPU 662, a main non-volatile storage unit 664, and a random access memory 668. In addition, the server computer 624 includes one or more buses. internal 666 to interconnect the elements mentioned above. Memory 668 stores a set of computer programs, modules, and data to implement the processing associated with the invention. In particular, a preferred embodiment of the memory 668 includes an operating system 680 and an HTTP server 682. The memory 668 further includes the address analyzer 684, the road layout module 686, the label layout module 688, the annotations module 690, and a map rendering module 692. In some embodiments of the present invention, memory 668 also includes an address database 694 and / or a context database 696. As will be discussed in further detail later, the server computer 624 further includes a shape simplification module 697 for smoothing roads on a route map, the map verticalization module 698 for optimizing the dimensions of a map. map scaled to the dimensions of the view region used to represent the scaled roadmap, and a map dividing module 699 for slicing a complex scaled route map into a plurality of segment maps.

The address analyzer 684 reads addresses from a source, such as a file, a database external to the server 624, or a database resident in the server 624. The address analyzer 684 translates the addresses into a graph. The nodes in the graph represent intersections, and the edges represent the roads that connect the intersections. In one embodiment, system 620 does not contain a database of roads. Instead, all information about the map is obtained from text addresses stored outside of the facility. In another embodiment, the server 624 contains the address database 694, which is used to identify a suitable route between a source and a destination.

After the addresses have been analyzed by the address analyzer 684, the roads on the route map are scaled with the road layout module 686. In one embodiment, the road layout module 686 applies a constant scale factor to the entire map so that the map fits in the viewing region that has predetermined dimensions. As a result of this uniform scaling, the map often contains many roads that are too small to view or label. To remedy this, each of the roads on the map, starting with the smallest roads, is scaled by road layout module 686 until the roads on the map are clearly visible. Since only the length of the roads is increased at this stage, the map ends up being larger than the size of the viewing region. Thus, in the later stages, certain aspects of the map are reduced to obtain a map that is adapted to the dimensions of the desired viewing region.

ES 2 373 095 T3

In one embodiment of the present invention, the size of the map is reduced by repeatedly initializing a plotting procedure. In this embodiment, the road layout module 686 executes the plotting procedure until the entire route has been plotted without identifying a highway that exceeds the dimensions of the viewing region. In the plotting procedure, each successive road on the route is examined, starting at the origin of the route, until a road extends out of the vision region, that is, an offensive road is identified. When an offensive road is identified, each road that has been laid is examined to see if it can be shortened. A candidate road can be shortened if it is (i) longer than a specified minimum length, (ii) the relative order of roads by length remains fixed even after the candidate has been shortened, and (iii) false ones are avoided intersections. In one aspect of this embodiment, the road layout module 686 shortens the candidate roads using a greedy approach such that the candidate shortens as much as possible, in order from longest to shortest, until the offensive road is returns to the interior of the vision region.

Label layout module 688 is used to place labels on the scaled map produced by road layout module 686. To date, proper labeling of individual roads has been an insoluble problem. Label layout module 688 solves this problem by refining a new objective function that uses a simulated annealing program. Simulated annealing has been used to refine label positions in prior art processes. Edmondson et al. In Cartography 33, 1997, 12-23, However, unlike Edmondson, who uses a limited set of discrete label positions, the present invention considers a continuous range of positions for label placement, and label placements are not limited to positions that are directly above or below the road. Furthermore, the present invention uses a more exhaustive objective function that considers the number of roads each label cuts, the number of labels each label cuts, the distance the label is from the center of the road associated with the label, and whether the label is above or below the associated road. Finally, the present invention is advantageous in that the roads are extended when the label corresponding to the road is long.

Annealing module 690 adds decorations, such as road extensions, to the route map of the present invention. In addition, module 690 adds an icon for the starting and ending points of the route. Road extensions accentuate reorientation points and allow a longer range of label positions to be considered. In this phase, all roads are stretched a small fixed amount. Then only the roads that need to be extended for the chosen labeling pattern are further lengthened. FIG. 10 illustrates the benefits of applying road extensions. In FIG. 10, 1002 represents a road map before the road extension while 1004 represents the same road map after the road extension. The labels now snap to the corresponding roads and the map is easier to read. Geographical and / or business context information is added to the route map by the annotation module 690 to help guide the user through the desired route. In one embodiment, such context information is obtained from context database 696.

The map display module 692 displays the scaled road map. In this phase, a sketchy pen and ink style is applied to each of the roads on the road map. That is, instead of drawing the roads as straight lines, a variation is introduced in the curve and width of each of the roads to generate a hand-drawn appearance. In an approach similar to that of Markosian et al., SIGGRAPH 97 Proceedings Conference, 1997, 415-420, each of the roads is broken into small segments and the position of each of the points is shifted slightly both in the direction of the tangent as normal to the direction of the segment. These points are then joined with a non-uniform rational b-spline (NURB) fit line to create the final stroke. A NURB is a curve that interpolates the data. In this way, given a set of points, a curve is generated that passes through all the points. The thickness of the roads is then adjusted to emphasize the road and de-emphasize the road extensions generated by the 690 annotation module.

Now that an overview of the invention has been disclosed, several advantages of the present inventions are apparent. First, the present invention discloses a method for the automatic generation of a route map that has the clarity of a hand-drawn map. Such a map is produced using a new scaling function in which each of the roads is scaled individually using the design criteria of the present invention. In addition, a new procedure for the positioning of labels on the map is revealed. Refined label positions help provide a roadmap that has improved clarity.

Map scaling

We now turn our attention to the detailed embodiments of the road layout module 686. The present invention contemplates several different implementations of the road layout module 686. Different embodiments of the road layout module contemplated by the present invention include but are not limited to uniform scaling, non-uniform fixed scaling, as well as refinement of individual scale factors using greedy search or simulated annealing program. .

ES 2 373 095 T3

In uniform scaling embodiments, a single scale factor is calculated that allows the graph created by direction analyzer 684 to fit into a desired viewing region. For viewing regions that have been defined by an arrangement of x by y image points (pixel), a unique scale factor of pixelPerMilla is calculated, by an assignment such as:

pixelPerMilla = CalculatePixelPerMilla ();

in which, the CalculatePixelPerMile () function determines the maximum number of pixels per mile of a road that it can have without causing the global route to exceed the desired pixel-based viewing region. One of ordinary skill in the art will appreciate that a unique scale factor can be calculated for viewing regions that are based on metrics other than pixels using functions analogous to CalculatePixelPerMilla (). Once a uniform scale factor has been identified by a function such as CalculatePixelPerMile (), the uniform scale factor is applied to the length of each of the roads and the intersection points between consecutive pairs of roads are updated to reflect the change in the length of the roads. For pixel-based viewing regions, applying the uniform scale factor to each of the roads reduces a conversion from miles to pixel. Thus, in such embodiments, the application of the constant scale factor to each of the roads takes the form:

(101) for each Road r {(102) r.lengthPxls) r.lengthMiles * pixelPerMile;

(103)} (104) SetRoadIntersectionPoints ();

In non-uniform fixed scaling embodiments, road layout module 686 includes a rescaleByInterval () function that slices the range of road lengths (0, infinity) found on the route into N consecutive intervals [0, x1), [x1, x2), ... [xn-1, xn), [xn, infinity). The function then scales the roads differently depending on the interval at which they fall. Small roads, which fall in the first intervals, are climbed larger, while longer roads are climbed to be shorter. In one embodiment, the roads that fall in the final interval are captured at some maximum length. In another embodiment, roads that fall in the first interval are not allowed to fall below a minimum length. In yet another embodiment, the scale factor that is chosen for each of the intervals is subject to the restriction that the relative order of the roads by length remains fixed. In embodiments where the route is scaled to a pixel-based view region, each road is scaled by the uniform scale factor calculated by the CalculatePixelPerMilla () function described in the uniform scaling embodiment. Thus, an implementation according to the non-uniform scaling performance, has the stages:

(201) RoadArrangement () (202) {(203) for each Road r {(204) r.lengthMiles = rescaleByInterval (r.lengthMiles);

(205) r.lengthPixels = r.lengthMiles * pixelPerMile;

(206)} (207) SetRoadIntersectionPoints ();

(208)}

We now turn our attention to FIG. 7 illustrating an embodiment of the present invention in which road layout module 686 refines the length of roads on the map using a greedy search algorithm. In processing step 702, the road layout module 686 first calculates a conversion factor from pixel to miles and applies this factor to each of the roads on the map so that the map fits into the viewing region. desired. Next, in processing step 704, the roads are shortened in length. The relative order of the roads, in terms of length, on the map as determined in processing step 704 is maintained throughout the remaining processing steps illustrated in FIG. 7. In some embodiments, deviations in this relative ordering are allowed by paying a penalty. In processing step 706, all of the small roads are increased until each of the roads is longer than a set minimum length. Because the processing step 706 only lengthens the roads, the road map is likely to not fit in the desired viewing region after the processing step 706 has been executed.

To reduce the map to fit within the desired viewing region, a search is performed for roads that can be shortened. In processing step 708, the route is traversed from the origin of the route. Each of the roads on the route (710 - 714) is examined until a road is identified that extends out of the region of vision (offensive road). When such a road is identified (710 - Si) a list of candidate roads is collected in the portion of the route that has been traveled before identifying the offensive road (720). To qualify a road as a candidate, a road traveled must be able to be shortened without changing the relative order of roads by length and without falling below a minimum road length. Furthermore, a candidate road must be able to be shortened without creating any false intersections between roads. Finally, the candidate road should be oriented within ± 90 degrees of the offensive road. Once it has been generated

ES 2 373 095 T3 a set of candidate roads, they are ordered by length, from longest to shortest (722).

Once the candidate roads have been ordered, a shortening procedure is initiated. The shortening procedure has the advantage of the computational efficiency of a greedy algorithm for shortening roads (724). The shortening procedure runs through each of the candidate roads in the ordered set of candidate roads and shortens the candidate as much as possible (726) before advancing to the next candidate in the ordered set (732). After the greedy algorithm is applied to a candidate road, a check is made to see if the offending road has returned to the interior of the viewing region (728). If the offensive road has turned within the viewing region (728 - No), the shortening procedure ends and control returns to processing step 708.

When the greedy algorithm has been applied to each of the candidate roads in the ordered set without satisfactorily returning the offended road within the viewing region (730 - Si), the shortening procedure repeats the procedure of applying the greedy algorithm to each one of the roads on the candidate list (724) until the offensive road is returned within the viewing region (728 - No). The procedure in FIG. 7 continues until the entire route can be traveled without identifying a road that exceeds the dimensions of the vision region (714 - Si, 780). If such a route fails, the shortening procedure of steps 720-732 is executed and a new attempt to travel route 708 is started.

Sometimes an identified road that matches the candidate requirements listed above will not be added to the set of candidate roads because there is some other road on the route that is the same length. Roads that are the same length as the identified road are called block roads. If there is a blocking road, the identified road cannot be added to the set of candidate roads because, if it were shortened, the relative ordering of the roads by length, as identified in processing step 704, would be destroyed. The occurrence of blocking roads is of interest because, in some circumstances, they prevent the processing steps of 724-732 from returning the offending road within the viewing region (728 - No). In some embodiments, when a certain number of iterations of processing steps 724 to 732 fail to effect a solution (728-No), one or more roadblocks are shortened using the greedy algorithm discussed above. Next, if the offensive road still exceeds the dimensions of the vision region, a new set of candidate roads (720) is generated and processing steps from 724 to 732 are executed until the offensive road no longer exceeds the dimensions vision region (728 - No).

FIG. 8 illustrates another embodiment of the road layout module 686 in which the length of the roads on the map is refined with a simulated annealing program. In processing step 802, a single scale factor is applied to each of the roads on the road map. In one embodiment, which is in accordance with this aspect of the invention, the scale factor is used to size the map produced by the address analyzer 684 so that it fits within the dimensions of the desired display region. In another embodiment, the map is sized so that each of the roads on the map is longer than a selected minimum length so that each of the roads on the map is readable in the desired viewing region.

In the second phase of the processing step 802, an initial parameter t is chosen. The use of a parameter t to obtain better heuristic solutions for a combinatorial optimization problem has its roots in the work of Kirkpatrick et al., Science 220, 4598, (1983). Kirkpatrick and others indicated the procedures used to find the low-energy state of a material, in which a single crystal of the material first melts by increasing the temperature of the material. The temperature of the material is then slowly lowered to near the freezing point of the material. In this mode, the true low-energy state of the material is determined, rather than some high-energy state such as a crystal. Kirkpatrick et al. Indicated that the procedures for finding the low-energy state of a material can be applied to other combinatorial optimization problems if a suitable analogy with temperature can be developed as well as an appropriate probabilistic function, which is driven by this analogy with temperature. . The art has called the temperature analogy an effective temperature. Therefore, the parameter t will be called from now on an effective temperature. It will be appreciated that any effective temperature t can be chosen in processing step 802. One skilled in the art will further appreciate that refinement of a target function using simulated annealing is most effective when choosing high effective temperatures. There is no requirement that the effective temperature adhere to any physical dimension such as degrees Celsius, etc. Actually, the dimensions of the effective temperature used in the simulated annealing programming adopt the same units as the objective function that is the subject of optimization.

In one embodiment, an effective start temperature is chosen that is easily reduced by ten percent on a periodic basis, such as 1.0 / log (3) * 3. In another embodiment, the starting value of t is based on a function of one or more characteristics of the route to be climbed, such as the number of roads on the route, the number of intersections on the route, and / or the length of the route. the route. In another embodiment, the start t value is selected based on the amount of resources available to calculate the simulated anneal schedule. For example, the starting value of t is reduced below a previously specified default value when the annealing program is to run on a server that is currently refining several different paths or on a client.

ES 2 373 095 T3 relatively slower. In yet another embodiment, the starting value of t is related to the form of the probability function used in processing step 814. It has been found, in fact, that the effective temperature does not have to be very large to produce a probability substantial to maintain a worse score. Therefore, in some embodiments, the effective starting temperature t is not large.

Once a single scale factor has been applied to each of the roads on the roadmap and an effective starting temperature has been assigned, an iterative procedure begins. A counter is initialized in processing step 804 and, in processing step 806, the quality of the map (E1) is evaluated using an objective function. It will be appreciated that the utility of the map produced by the simulated annealing program is dependent on the development of an objective function that accurately balances the various features of the map that need to be optimized. In one embodiment, the objective function is dependent on the number of false intersections that each of the roads on the route makes, the number of roads on the route that no longer have the same relative length as they had before the program was started simulated annealing, and the number of roads on the route that fall below a minimum length. An objective function according to this embodiment is:

<img file="ES2373095T3_D0001.tif" />

in which,

W1, W2, and W3 are independently selected weights;

false_intersection, is the number of false intersections made by road i;

N is the number of roads on the route;

Num_w / o_rel_long is the number of roads that are no longer the same relative length as they were before the simulated annealing program was started; and num_carret_cortas is the number of roads that are shorter than a minimum length threshold.

After the quality (E1) of the map has been measured using the objective function, a scale factor is randomly generated and applied to a randomly selected road (808). In one embodiment, the scale factor is chosen randomly from an allowable range, such as zero to two. Thus, in such an embodiment, a random number generator is used to identify a number in the range of zero to two, such as 0.6893. The random number is then applied to a randomly selected road on the route as a constant scale. For example, if the number is 0.6893 and the randomly selected road is index j road on the roadmap, index j road is shortened by 31.07 percent. In another embodiment, the allowable range for the random number is -0.1 to 0.1 and therefore, in such embodiments, the application of the randomly chosen scale constant is capable of altering the length of the index road. j by no more than ten percent.

After the length of the index road j has been adjusted by the scale factor, the quality of the map (E2) is calculated using the same objective function used in processing step 806 (810). When the quality of the map has improved (E2 <E1) (812 - Yes), then the change made to the length of the road of index j is accepted (830). When the quality of the map has not improved (E2> E1) (812 - No) the change made for the length of the road of index j is accepted with the probability of:

- exp ^- «^ΔΕ> ^{/ k} (1)

From the form of equation (1), it will be appreciated that the probability that the change is accepted, when (E2> E1), is less at lower effective temperatures t. Equation (1) is implemented according to processing steps 814 to 818 in FIG. 8. In processing step 814, exp^{- [(ΔΕ) /} *^t]. In processing step 816, a number P is generated_ran in the range from 0 to 1. If P_ran is less than exp ^{- [ΔΕ) / k}*^t)] (818 - Yes), the change made for road of order j in processing step 808 is accepted (830). If Pran is greater than exp^{[(ΔΕ) 1 k}*^t] (818 - No), the change made to the index road j in the processing step 808 is rejected (840). It will be appreciated that probability functions other than that discussed in equation (1) are within the scope of the present invention.

Accepting the conditions of (E2> E1) on a limited probabilistic basis is advantageous as it provides the refinement system with the ability to escape local minimum traps that do not represent a global solution to the objective function. One skilled in the art will therefore appreciate that probability functions other than that of equation (1) will further the objectives of the present invention. Representative probability functions include, for example, functions that depend linearly or logarithmically on the effective temperature, rather than those exponentially dependent on the effective temperature as described in equation (1).

ES 2 373 095 T3

Processing steps 806 to 840 represent an iteration in the refinement procedure. At processing step 842, an iteration count is advanced. When the iteration count does not exceed the maximum iteration count, the procedure continues to step 806 (844-No). When the iteration count equals the maximum iterations indicator (844 - Si), the effective temperature t (846) is reduced. One skilled in the art will appreciate that there are many different types of schedules that are used to reduce the effective temperature t in various embodiments of processing step 846. All of these schedules are within the scope of the present invention. In one embodiment, the effective temperature t is reduced by ten percent. In another embodiment, the effective temperature t is lowered by a constant value. For example, the effective starting temperature set in processing step 802 could be 20,000 and this effective temperature could be lowered by 300 each time processing step 846 is executed. In another embodiment, the percentage decrease in effective temperature is computed in processing step 846 as a function of the number of roads to climb.

When the effective temperature has been reduced by an amount in processing step 846, a check is made to determine whether the simulated annealing program (848) should be terminated. In the embodiment illustrated in FIG. 8, the procedure is terminated (848-Si, 850) when the effective temperature t has fallen below the effective temperature low threshold or E2 falls below a predetermined low quality threshold. The low effective temperature threshold is any suitably chosen effective temperature that allows a sufficient number of refinement cycle iterations at relatively low effective temperatures. When it is determined that the annealing program should not end (848-No), the procedure continues at step 804 with the reset of iteration count i.

In another embodiment of the present invention, a distinctly different output condition is used from that illustrated in FIG. 8. In this alternative embodiment, a separate counter is maintained. This counter, which could be referred to as a stage counter, is increased each time t is decreased in step 846. When the stage counter has exceeded a predetermined value, such as fifteen, the simulated annealing procedure ends (850). In yet another embodiment, a counter tracks the number of consecutive times the arbitrary scale factor is rejected (840). When a fixed number of arbitrary changes in a row has been rejected, the route map is considered optimized and the procedure terminates (850).

Map annotation

In one embodiment, the annotation module 690 is used to deterministically place context information on the map after the map has been scaled by the road layout module 686. In one aspect of this embodiment, the context information represents geographic points of interest and helps guide the user through the route to the destination. In another embodiment, the context information represents a form of advertisement that is paid for by subscribers. In one example according to such embodiments, the subscriber is a fast food chain and the marks represent the location of each of the fast food franchises that is associated with the fast food chain. It will be appreciated that an important advantage of the present invention is that the road maps do not contain superfluous content. Thus, the route maps of the present invention are particularly well suited for use in conjunction with geographic landmarks that are paid by subscribers. In one embodiment of the present invention, the memory 668 of the server 624 includes a context database 696 that is populated with context information that is provided and paid for by advertisers.

Tag refinement

Identifying an optimal position for each of the labels on the route map improves map quality by reducing clutter and object overlap. The present invention optimizes label position by minimizing a new objective function that scores the position of a label using a unique set of label parameters. Importantly, instead of considering a small number of discrete positions for label placement, a continuous range of positions is considered within a region around the center of the road to be labeled. This region includes positions that are not directly above or below the road being labeled. When a position is selected that is not directly above or below the road, the road is extended to the label position.

In one embodiment, the objective function is optimized using a simulated annealing program. FIG. 9 illustrates an embodiment in accordance with the present invention. In the processing step 900, each of the labels is placed in the center of the road corresponding to the label and an initial effective temperature t is selected. It will be appreciated that the effective temperature t can be set over a wide range of possible effective temperatures in processing step 900. In one embodiment, an effective starting temperature is chosen that is easily lowered based on a periodic ten percent, such as 1.0 / log (3) * 3. In another embodiment, the effective start temperature is based on a function of one or more characteristics of the route to be optimized, such as the number of labels in the route, the amount of context information along the route, and / or or the length of the path. In another embodiment, the effective start temperature is selected based on the amount of resources available to perform the simulated anneal calculations. For example, the initial effective temperature is set to a low value when the annealing program is running on a server that is currently refining several other routes or a

ES 2 373 095 T3 client with a relatively slow central processing unit. In yet another embodiment, the effective starting temperature t is determined by the nature of the probability function that is used to accept scores having S2> S1.

In processing step 902 the step counter is set to zero. The stage counter is increased each time the effective temperature t has been lowered. After the initialization steps of processing step 900 have been performed, counter i is set to one (902) and label j is randomly selected (904). The quality of the position of the index label j (S1) is measured using an objective function, which is designed to measure the quality of the label position, in processing step 906 and in processing step 908 the label of index j is reset by a random amount. In step 908, the quality of the repositioned index label j (S2) is measured. An important advantage of the present invention is that the index label j is repositioned within any continuous range of values ​​rather than a limited number of discrete positions. Furthermore, the objective function used to calculate S1 and S2 provides an improved procedure for evaluating the quality of a label position. In one embodiment the objective function includes the following components:

(301) (302) (303) (304) (305) (306) (307) (308) collect all the objects that cut to the index label j for each of the objects that cut {ROAD case:

score + = HIGHWAY_PENALTY; LABEL case:

score + = TAG_PENALIZATION; case ANNOTATION:

score + = PENALTY_NOTE;})

On line 301, all objects that intersect label of order j are collected. Such objects include, for example, roads, other labels, and annotations such as context information. The objective function loops through each of the collected objects (line 302). When the object is a road, a road penalty is added to the score (line 304), when the object is a tag, a tag penalty is added to the score (line 306), and when the object is an annotation, it is adds a scoring penalty to the score (line 308).

In some embodiments, the objective function includes one or more additional components. One such component is an off-screen penalty. When the index tag j is positioned so that a portion of the tag exceeds the boundary of the viewing region, an off-screen penalty is added to the score. Another component is a penalty for the distance from the center of the corresponding road. This penalty is determined by taking the product of a centering penalty and the normalized distance from the j-order label to the center of the road. Additional components in the objective function represent various constraints that are imposed on the position of the label. Constraints are used for deviations in label positions that are consistent with the design criteria of the label position. For example, in one embodiment, it is preferable to position a label above the road rather than below the road. This adds a below_the_road penalty to the score for the position of the label that is below the road corresponding to the label. Another restriction penalty asks if a road should be extended so that the road runs alongside the label side. When it is determined that a road extension will provide a better label match to the road, a road extension penalty is added to the objective function score. Yet another restriction penalty is used when the tag is positioned away from the center of the corresponding road. In such cases, an arrow is positioned on the map to indicate the relationship between the label and the corresponding road and an arrow penalty is added to the objective function.

In one embodiment, the objective function has the form:

(401) (402) (403) (404) (405) (406) (407) (408) (409) (410) (411) (412) (413) float score = 0.0 // Get the objects that cuts to the label for each of the objects {ROAD case:

score + = HIGHWAY_PENALTY;

LABEL case:

score + = TAG_PENALTY;

case ANNOTATION:

score + = PENALTY_NOTE;

} // Is the label visible in the view region?

if not {score + = PENALTY_OUT_SCREEN;

ES 2 373 095 T3 (414) (415) (416) (417)}

score + = normalized distance from the center of the road * PENALTY_CENTRATE;

score + = restriction penalty;

return score;

When the quality of index position j has improved (S2 <S1) (912 - Yes), the new label position for label of order j is accepted (930). When the quality of the map has not improved (S2> S1) (912 - No) there is a probability (2) that the new position for index label j will be accepted. From equation (2) it will be appreciated that for the cases in which (S2> S1), the probability that the change in the position of the label is accepted decreases as the temperature t is reduced. Equation (2) is implemented according to processing steps 914 to 918 in FIG. 9. In processing step 914, exp^{- [MS) kí]}. In processing step 916, a number P is generated_ran, in the range from 0 to 1. If P_ran is less than exp ^- (918 - Yes), the change made for the position of the index label j in the processing step 908 is accepted (930). If P_ran is greater than exp ^{- [(ÚS) / kt>]} (918 - No), the change made for the position of the index label j in the processing step 908 is rejected (940). It will be appreciated that probability functions, other than the function shown in equation (2) and the processing step 914 are within the scope of the present invention. Actually, any probability function that is dependent on the effective temperature is adequate.

Processing steps 904 to 940 represent an iteration in the annealing procedure. In processing step 914, an iteration count is increased. When the iteration count does not exceed the maximum iteration count (944 - No), the procedure continues in step 904. When the iteration count equals the maximum iteration indicator (944 - Si), the effective temperature t becomes the step counter (946) is reduced and advanced. One skilled in the art will appreciate that there are many different possible types of schedules that are used to reduce the effective temperature t in various implementations of processing step 946. All of these schedules are within the scope of the present invention. In one embodiment, the effective temperature t is reduced by ten percent each time processing step 946 is executed. In another embodiment the percent decrease in effective temperature t in processing step 946 is calculated as a function of the number of labels to be scaled. After processing step 946, a check is made to determine whether the simulated annealing program (948) should be terminated. When it is determined that the annealing program should not be terminated (948-No), the procedure continues at step 902 with the reset of iteration count i.

In the embodiment illustrated in FIG. 9, the procedure is terminated (948 - Yes, 950) when a maximum number of stages has been executed. In one embodiment the maximum number of steps executed is fifteen. In embodiments other than that illustrated in FIG. 9, criteria other than step count are used in processing step 948 to determine when the simulated annealing procedure should be completed. Such criteria include termination of the procedure when the effective temperature t has fallen below a low effective temperature, when E2 or E1 falls below a low quality threshold, or when the number of consecutive times the new position has been rejected. the label exceeds a threshold value.

Map presentation

The final phase of the procedure is the presentation of the route by the map display module 692. In this phase, the route map is humanized. In some embodiments, the techniques used to humanize the map include modeling the roads in a schematic pen and ink style, adding a break symbol to long roads that have been scaled down significantly by road layout module 686. , providing an indication of the length of the road for long roads on the route, adding an arrow to indicate which is North, and / or adding inserts that show enhanced details of the route.

The map display module 692 produces the schematic style by breaking each of the roads into small segments and slightly shifting the position of each of the elements both in the normal direction to the line and in the directions of the line. The rotated segments are then joined with a NURB to create the final stroke. In addition, the thickness of the roads is adjusted to emphasize the route and de-emphasize the extensions of the routes. In a preferred embodiment, a handwriting font is used for the labels.

Overview of alternative realizations for roadmap abstraction and visualization

Embodiments for producing scaled road maps have been described in detail. Details of alternate implementations for roadmap scaling are provided in the following sections. The full appreciation of these alternative embodiments is best obtained by first providing an overview of the basic steps of the procedure performed by these alternative embodiments.

Get route directions. First, the addresses are obtained by the address analyzer 684 to

ES 2 373 095 T3 from a source such as the address database 694 (FIG. 6). Although the address database is represented so that it is on the same server 624 as the address analyzer 684, it will be appreciated that there is no requirement that the address database 694 reside on the same server. In reality, the address database 694 can take a number of different forms and reside at any address that is in communication with the transmission channel 626.

Road simplification. Once the road directions are obtained, an initial road map is constructed. Next, as will be described later in further detail, a step through the highway shape simplification module 697 is performed in the initial route map simplification. If successful, the Road Shape Simplification module 697 removes one or more shape points from some of the roads on the roadmap, thereby reducing the complexity of the roadmap without sacrificing the readability and usability of the roadmap. Map. Additionally, the reduced complexity of a simplified roadmap facilitates the computationally intensive map refinement and scaling that occurs in post-processing stages.

Map page layout. At the map page design stage, the dimensions of the viewing region that the map will render or print are considered. A layout template is chosen by the road layout module 686 based on the dimensions of the viewing region. In addition, the road map is optionally rotated by the map verticalization module 698 to optimize the road map dimensions with the viewing region dimensions. When the route map includes multiple stages, the map splitting module 699 is invoked to slice the route map into a plurality of segment maps in a way that is consistent with the selected layout template.

Layout of roads. At this stage, the road layout module 686 scales each of the roads independently (ie, non-uniformly). Non-uniform scaling is driven by an optimization algorithm such as simulated annealing to achieve a suitable scaled map. The objective function used by the optimization algorithm uses a new scoring strategy that is designed to quantify the quality of the map scale.

Label layout. After the map has been scaled, the roadmap is populated with the road labels by the label layout module 688. Each of the labels is associated with a restriction definition that defines the boundaries at which it can place a label and the format of the label. Using these constraint definitions, the label layout module 688 refines the label locations using an optimization algorithm that has an objective function that quantifies the quality of the label position.

Annotation of the map. Road junctions, terrain markings, and the optional North arrow are added to the map during the map annotation stage. The annotation module 690 identifies suitable landmarks that will assist the navigator while it is using the roadmap. Such landmarks can be inferred from a source such as a 606 context database. It will be appreciated that the annotation module 690 can be used in some embodiments for commercial benefit. For example, licensing schemes are displayed in which a retailer pays to have a location of each of the franchises positioned on the map as landmarks.

Presentation of maps. Other stages of the map scaling procedure consider the road map in an abstract sense. At the map display stage, the components of the roadmap, including the main route, crossing streets, landmarks, and the North arrow are reduced from an abstract sense to a real image. In one embodiment, this image is a pixel-based image. The procedure step is performed by a map presentation module 692.

Now that an overview of this alternate embodiment series has been provided, we will examine further aspects of the embodiment series in detail.

Alternative scoring functions used in road layout refinement

As outlined in the overview, an important aspect of the map scaling procedure is performed by the road layout module 686. The road layout module 686 scales each of the roads on a road map in a unique way. not uniform. In embodiments in which the road layout module 686 includes a simulated annealing program, the following steps are performed:

1. Generate an initial road layout by increasing all short roads to a desired minimum length.

2. Obtain an initial score E for the initial road layout using an objective function and set an initial effective temperature.

3. As long as E is greater than an acceptable score, the number of iterations is less than the maximum number of iterations allowed, and the effective temperature is above a low threshold level, repeat steps 4 through 8.

ES 2 373 095 T3

Four. Choose a random road and increase or shrink it by a random amount; rescale all roads to fit within the viewing region.

5. Get a new E score for the new road layout generated in stage four.

6. If the new score E is less than the initial score E, accept the new road layout generated in stage four.

7. If the new score E is greater than the initial score E, accept the new road layout according to decreasing probability, to escape local minima.

8. Set the effective temperature.

It will be appreciated that the simulated annealing protocol outlined above and described in detail in FIG. 8 is not limited to any specific scoring function. Actually, various embodiments of the road layout module 686 use a wide array of scoring functions to determine the initial score E₁(806 FIG. 8) as well as the new E2 scores (810 FIG. 8). Applicants have described an objective function in accordance with an embodiment of the road layout module 686 that is determined by (i) the number of false intersections that each of the roads i makes on a road map, (ii) the number of roads that are no longer the same relative length as they were before the simulated annealing program was started, and (iii) the number of roads that are shorter than a minimum threshold length

In another embodiment of highway layout module 686, processing steps 806 and 810 in FIG. 8 use a scoring function represented by the following representative code.

(501) Score () (502) Score = 0.0 (503) Score + = ScoreIntersection () (504) Score + = ScoreBarajar () (505) Score + = ScoreRoadLength () (506) Score + = ScoreProportion () (507) Score + = Endpoint Direction Score () (508) Endpoint Score + = Distance Endpoint Score ()

Each of the sub-scores considers a specific aspect of the road layout and is prioritized as follows:

<td>Highest priority</td><td>Intersections: maintaining existing intersections and not introducing false intersections. Road Length - Scaling of all roads to make them readable. Shuffling: maintaining the relative lengths of the roads. Direction of the end point: maintenance of the global orientation of the route. Proportions: maintenance of the proportions in the lengths between roads.</td>

<td>Lowest priority</td><td>Distance to end point: maintaining the distance between the starting and ending points of the route.</td>

In this embodiment, the scoring function used by the highway distribution module 686 assigns a higher priority to those aspects of the highway distribution that are most important to solve. For example, a map with missing intersections or false intersections can be misleading. On the other hand, maintaining overall distance and route orientation are useful but not required for a navigator to follow the route. Thus, resolving intersections is given a higher priority than maintaining distance from the end point in this embodiment of highway distribution module 686.

Representative code line 502 initializes the Score variable to zero. The variable Score represents E1 (806 FIG. 8) or E2 (810). Next, lines 503 to 508 each potentially add an amount to the value of the Score variable. Higher values ​​of the score represent higher values ​​of E1 and E2 and thus represent poor solutions. Each of the functions that contributes to the overall Score value on lines 503 to 508 is discussed in more detail below.

IntersectionScore (). The first function to contribute to the Score variable in the representative code is the IntersectionScore () function on line 503. Proper maintenance of the intersections between the

ES 2 373 095 T3 roads is the highest priority in the unveiled scoring function. At anneal initialization, all roads on the roadmap are increased to their desired minimum lengths. Increasing roads can lead to two problems: intersections can be introduced between roads that should not be cut (false intersections), or two roads that should be cut are no longer cut (loss of intersections). FIG. 40 illustrates two scenarios. FIGS. 40A and 40C each represent an original map while FIGS. 40B and 40D represent disturbed maps. FIG. 40b depicts a situation where a false intersection 4002 arises. FIG. D represents a situation where a 4004 intersection loss occurs. Both cases of missed and false intersections can be extremely misleading and are therefore severely penalized in any proposed distribution that has either of these problems.

The role of the scoring function in highway distribution module 686 is to guide the distribution algorithm to the desired distribution. One approach to further this goal is to add a constant flat penalty when any of these conditions exist. However, the scoring function does not provide adequate guidance because the same penalty is always added to the score regardless of the severity of the missing or false intersection. Suppose the route contains a missed intersection as shown by 4004 in FIG. 40D. If the distribution is disturbed and the missing intersection points end up closer to each other but do not exactly match, the intersection score for this map will not change. The algorithm are know that moving the lost intersection points closer together generates a better distribution. In other words, the annealing algorithm is less likely to converge. Thus, in this embodiment, a score is constructed that reflects the severity of the intersection problems in a way that suggests how they can be solved rather than using a constant penalty for each of the missing or false intersections. What follows is a description of how false and missing intersections are simply resolved independently by the disclosed scoring function. Here is a description of how a score should change when there are both false and missed intersections on a single map.

Missed and misplaced intersections. If two roads should intersect but do not (intersection loss), a factor is added to the score that refers to the distance between the appropriate intersection point on each of the roads. The appropriate intersection point is calculated from the parametric value of the original intersection on the unscaled map. If the roads should and do intersect but at the wrong point (misplaced intersection), a factor is also added which is related to the distance between the appropriate intersection point on each of the roads. The score weight for a displaced intersection is much less than for a missed intersection. This score is illustrated in FIG. 41. FIG. 41A depicts how an intersection loss is scored while FIG. 41B represents how a misplaced intersection is scored. The general formulas for calculating the intersections are:

loss score = d * LOSS_POINT_WEIGHT misplaced score = d * BAD_PLACEMENT_POINT_WEIGHT where d is the Euclidean distance between the two points that should intersect as shown in FIG. 41.

Unique false intersections. False intersections occur when the path incorrectly bends on itself, forming a loop or knot. To eliminate false intersections, the knot must be undone. To remove any individual knots it is desirable to make the point of the false intersection move towards the end of the nearest end (in pixels along the road) of the path (or similarly make the point of the nearest end moves toward the false intersection point). FIG. 42 illustrates various false intersection scenarios, showing for each of the false intersection points in which direction the closest end point must travel to eliminate the node formed by the false intersection point. FIG. 424A represents the simplest case, a false intersection 4202. The endpoint 4204 simply needs to move to the right to solve the false intersection. FIGS. 42B and 42C show in which direction the end points should move to solve each of the false intersection points independently. FIG. 42B depicts a situation in which multiple false intersection points 4208 are near the same end point 4206. The two false intersection points 4208 are pulling end point 4206 in opposite directions. FIG. 42C represents the case of multiple false intersection points (4214, 4216) that are close to different end points (4210, 4212). In this case, the false intersection points 4214 and 4216 are entirely independent of each other.

Calculating the score for a single false intersection point is relatively straightforward. It is desirable to move the false intersection point towards the nearest end point of the route, or alternatively to move the nearest end point towards the false intersection point. FIG. 43 illustrates a node that is produced by the false intersection 4302. One way to solve the false intersection 4302 is to push the endpoint that is closest to the false intersection 4302 toward the false intersection. To determine which end point is closest (4304 or 4306) to the false intersection 4302, the distance between each of the end points and the false intersection is calculated and compared. The end point that is closest to the false intersection is then moved toward the false intersection.

Viewing each of the false intersections independently, the score for each of the points of

ES 2 373 095 T3 false intersection is calculated as the distance in pixel along the path to the point of the nearest end multiplied by a weight of the score. This is equivalent to conceptually constructing a scoring hill along the path that guides the false intersection point to the nearest end point where it can be removed. Therefore, the score for a single false intersection can be calculated as false score = d * FALSE_POINT_WEIGHT where d is the distance in pixel to the end point along the path, as opposed to the straight-line distance, as shown shown in FIG. 43. However, as illustrated by the scenario in FIG. 42B, if the score is calculated for each of the false intersections in this way, then when there are multiple false intersections the scores will push the endpoint in opposite directions. However, this problem is solved by always counting only the score for the innermost false intersection (that is, the furthest from the end point). The difference between counting all false intersections and only the innermost false intersection is shown in FIG. 44. FIG. 44 illustrates the situation where, if the scores for both false intersections 4404 are counted, the end point 4402 is pulled equally in both directions, resulting in a plateau in the scoring function as a movement of the end point 4402 in either direction direction does not change punctuation. FIG. 44B illustrates the situation where only the innermost false intersection is counted for each of the end points. In the situation described in FIG. 44B, once the innermost false intersection has been resolved, the remaining false intersection becomes the innermost false intersection and is subsequently resolved. In situations such as that of FIG. 42C, where there are two false intersections but both are closer to different end points, both scores are counted against these respective end points.

False intersections and loss of intersections. In general, when both false intersections and lost intersections occur on the same map they can be scored as described above, and in most cases the scores will interact appropriately to solve both problems. However, there is an exceptional situation. This situation occurs when an intersection loss occurs within the loop formed by a false intersection. Various variations of this situation are illustrated in FIG. 45. In FIG. 45A, a lost intersection point 450 is within the loop formed by a false intersection 4504. In FIG. 45B, both points 4506 are within the loop formed by the false intersection 4508. In both situations shown in FIG. 45, one score may push in one direction and the other score in the other direction, resulting in a deadlock in which neither problem can be solved. FIG. 46 shows the same routes as FIG. 45, but with arrows 4610 added to indicate the direction in which the two scores would move to endpoints 4602 and 4604.

An important point about the situations presented in FIG. 45 is that the resolution of the missing intersection often resolves the false intersection. In FIG. 45, it is assumed that there is an intersection, which occurs right between the wrong roads. It is quite often the case where an intersection loss occurs within the loop of a false intersection, that the false intersection is simply the misplaced lost intersection. This situation is solved with an additional rule: if there is any missing intersection point within the loop formed by a false intersection, a constant penalty is added for the false intersection, not a score based on a hill. Thus, both cases shown in FIG. 45 will use a constant penalty for the false intersection, since they both contain at least one missing intersection point within the false intersection loop.

With this introduction an algorithm can now be established to score false and missing intersections with lines 601 to 633 of the illustrative code.

(601) empty false_intercept_score (Own * road, Different * road (602) if (lost_intersection_in_loop) {(603) // false intersection loop contains a missed intersection (604) if (end_point_more_next_road (own, different)) {(605) own IncreaseScore (CONST_FaLSa_INTERSECCIÓN):

(606)} if not {(607) // there is no lost intersection in loop (608) if (end_point_next_highway (own, different)) {(609) (610) (611) (612) (613) (614) ( 615) (616) (617)}}} own IncreaseScore (pixelAtEndpointMostNext * HILL_FALSE_INTERSECTION);

// Calculate the maximum possible extended intersection score. All // false intersection scores must be increased by the // maximum extended intersection score to ensure that there are no // valleys between resolving all false intersections // and entering extended intersections.

own IncreaseScore (ExtendedIntersectionScoreMax);

ES 2 373 095 T3 (618) (619) (620) (621) (622) (623) (624) (625) (626) (627) (628) (629) (630) (631) (632) (633) empty MissingIntersectionScore (Own * Road, Different * Road) {double MissingIntersectionScore = 0.0;

// We know where the two roads should have crossed in terms of T // values ​​along the road. Calculate the distance between these two points.

for (each missing intersection between its own and another) {double dist = (own pt - different pt) .length ();

// Before the roads touch use a higher penalty. After // they touch, reduce the constant penalty to ensure that the // anneal will hold the touch.

if (there is no intersection between its own and the other) {double scoreLoss = dis * INTERSECTION_LOSS;

own increaseScore (Road :: IINTERSEC, LostPt); } if not {own increaseScore (road: INTERSEC, dist * INTERSECTION_BAD_PLACED);

} } }

Examining lines 601 through 633 of the illustrative pseudo-code in detail, it will be seen that an additional score MaxIntersectionScore is added for false intersection scores. This function is described later with an explanation of the concept of extended intersections.

Extended intersections. In addition to avoiding actual intersections between roads, it is desirable to avoid having roads that pass close enough to each other that they appear to touch. These situations are handled in one embodiment of the highway layout module 686 using the concept of an extended intersection. Extended intersections between two roads are calculated by extending both end points of each of the roads by a fixed number of pixels, and then checking whether the resulting roads intersect. This concept is illustrated in FIG. 47. In particular, in FIG. 47A, the roads do not actually intersect but are close to each other. In FIG. 47B, when the roads are spread by a fixed number of pixels, the roads are cut. If there is an extended intersection between two roads, it is scored as follows for each of the roads:

(a) if the intersection occurs on the extended portion of the highway, as for highway 4702 in FIG. 47A, then the pixel number from the end of the extended road is calculated and multiplied by a fixed constant.

(b) if the intersection occurs within the unextended portion of highway, such as highway 470A in FIG. 47A, then a fixed constant is added to the score, which is equal to the largest penalty that can be assigned for an intersection with the extended portion of the road.

There is a complication with handling extended intersections. When it comes to solving a false intersection, extended intersections often cause many local minima in the search space. This is illustrated in FIG. 48, where the extended intersection 4802 works against the resolution of the false intersection 4804. To reduce the number of local minima in the search space explored by the objective function as much as possible, only intersections extended toward the score are counted when they are not likely to counteract the resolution of a false intersection. Implementing this criterion requires two things:

(a) know when an extended intersection counts, and when it does not count, and (b) add the highest possible score from the extended intersection to the false intersection base score. Otherwise, when a false intersection is solved, the objective function begins by counting a number of extended intersections, and its increased score can outweigh the decrease in the false intersection resolution score. This can cause a substantial local minimum in search space that would prevent resolution of most false intersections. However, in a preferred embodiment of the road layout module 686, the maximum score for the extended intersection is added to each of the false intersection scores. This ensures that the resolution of a false intersection will result in a decrease in the score.

One way to determine which extended intersections to add to the score is to divide the road into false intersection intervals. All roads between a map end point and a false intersection, or between a pair of false intersections, are considered to be in the same false intersection interval. This concept is illustrated in FIG. 49. In FIG. 49, the same route shown in FIG. 48, but the route is segmented by false intersection intervals. In particular, there are three false intersection intervals in FIG. 49; (A) from the start point 4802 to, but not including, the first road with a false intersection, (BCDE) which is from the road with a false intersection to the next road with a false intersection and (FGH) which is from the last false intersection to the end point. Extended intersections are only counted between roads

ES 2 373 095 T3 in the same false intersection interval. Thus, the extended intersection shown in FIG. 48 would not be counted. If only the extended intersections occurring between roads at the same false intersection intervals are added, then the problem depicted in FIG. 48 will not occur.

ScoreBarajar (). The second function to contribute to the Score variable in the representative code is the ShuffleScore () function on line 504. The purpose of ShuffleScore () is to keep the relative lengths of the different roads on the scaled roadmap the same as when they were in the unscaled route map. In the BarajarScore () function, for each of the road pairs A and B on the road map, the order of the roads by length on the scaled map is compared to the order of the roads by length on the unscaled map. original. If the ordering has changed, roads A and B are considered shuffled and a factor is added to the Score variable to reflect this. In one embodiment, however, roads are only considered shuffled when their difference in length is greater than a perceptual threshold. Typically, the perceptual threshold used is dependent on the resolution and size of the viewing region that is used to display the roadmap as well as factors such as whether the full scaled roadmap is being rendered in the viewing region in opposition to a scaled-up segment of the scaled roadmap. The purpose of the penalty applied by the ShuffleScore () function is to ensure that, whenever possible, the relative ordering of roads by length is maintained on the scaled roadmap.

In a representative objective function used by an embodiment of the road layout module 686 Barajar Score () is represented by the following expression:

For each pair of roads (A, B)

Compare the order of the roads by longitude on the current map with the order of the roads by longitude on the original map. If the ranking has changed then add a constant penalty to the score to reflect this. Roads are only considered shuffled when their difference in length is greater than a perceptual threshold.

RoadLength Score (). The overall goal of the non-uniform scaling of maps that is implemented by the road layout module 686 is to make all the roads on the route large enough to be readable. This is followed by the third function (RoadLengthScore ()), which contributes to the Score variable as found on line 505 of the representative code. In the RoadLengthScore () function, the current longitude of each of the roads on the roadmap is compared to a predetermined minimum desired length. If a road is less than the minimum desired length, then a factor is added to the Score variable. The magnitude of this factor is a function of the power of the difference between the current length of the offensive road and a predetermined minimum acceptable road length. The predetermined minimum acceptable road length is set to ensure that the road is long enough to be identifiable on the scaled road map. In some embodiments of the present invention, the predetermined minimum acceptable road length is designed considering the dimensions of the viewing region 640 (FIG. 6) used to represent the scaled route map or the number of pixels in the viewing region. 640. In one example, when the viewing region 640 is a 1024 by 768 pixel arrangement, the predetermined minimum acceptable road length is 20 pixels. In another example, the predetermined minimum acceptable road length is set as four percent of the length of the shortest dimension of the viewing region 640. Thus, if the viewing region 640 has a screen that is 5 by 6 centimeters, the predetermined minimum acceptable road length is set at 0.2 centimeters.

In a representative objective function used by one embodiment of the road layout module 686, RoadLengthScore () is represented by the following expression:

For each of the roads (A)

Compare the current length with a predetermined minimum desired length. If it is less than the desired minimum length then add a factor to the score. The factor is related to the power of the difference between the current length and the desired minimum length. The desired minimum length is set to ensure that the road is long enough to be perceived and labeled and that the relative lengths are preserved.

ScoreProportion (). The fourth function that contributes to the Score variable is the ProportionScore () function, which is on line 506 of the representative code. One of the lowest priority contributions to the Score, the function ScoreProportion () is used to maintain the proportions between the different lengths of roads. The ProportionScore () function examines each of the A roads on the scaled route map whose length is greater than the default minimum acceptable road length described in the description of the RoadLengthScore () function above. For each such A road on the scaled road map, the ratio of the road length is compared to the next shortest road and the next longest road on the road map. The proportions obtained from these comparisons are matched with the corresponding proportions obtained from the unscaled road map. When the ratio of road A to the next longest road and the next longest road

ES 2 373 095 T3 short on route map differs significantly on route maps, scaled and unscaled, a penalty is added to the Score variable. The purpose of the ProportionScore () function is to preserve the proportions of the road lengths in the scaled roadmap from the unscaled roadmap that has enough space.

In a representative objective function used by one embodiment of the road layout module 686, the ProportionScore () function is represented by the following expression:

For each of the roads (A) whose length is greater than its minimum desired length:

Compare the ratio of this road length to the next shortest road and the next longest road, limiting the ratios to five, since in a non-uniform limitation it is difficult to maintain any higher ratio. Assign a penalty such as:

penalty = absolute value of (current ratio - original ratio) * SCORE_PROPORTION

EndpointAddressScore (). The fifth function to contribute to the Score variable in the representative code is the EndpointAddressScore () function (line 507). This function adds a factor to the Score variable to reflect the difference in orientation between the start and end directions on the unscaled roadmap and the scaled roadmap. The magnitude of the factor added to the Score variable by this function is dependent on the extent of the difference in orientation between the start and end directions on the scaled and unscaled road maps. Large differences in orientation get a large magnitude while small differences get a small magnitude.

In one embodiment of the road layout module 686, the EndpointAddressScore () function is represented by the following expression:

penalty = absolute value of (original bearing angle - current bearing angle) * ORIENTATION_POINT

EndpointDistance Score (). The sixth function to contribute to the Score variable in the representative code is the EndpointDistanceScore () function on line 508 of the representative code. This function adds a factor to the Score variable that reflects the difference in distance between the start and end point addresses on the original unscaled roadmap and the current scaled roadmap. This feature is particularly useful for road maps that have a global U shape. This feature ensures that the beginning and end of the road map are not too close to each other.

In one embodiment of the road distribution module 686, the EndpointDistanceScore () function is represented by the following expression:

penalty = (desired length - current length) / desired length * DISTANCE_LENGTH

It will be appreciated that the scoring function represented by lines 501 to 508 of the representative code merely illustrates one type of scoring function that is used in some embodiments of the road layout module 686. In fact, many permutations of the function are possible. score represented by lines 501 to 508 of the representative code. Such permutations include the use of only a subset of the outlined functions in the representative code to construct the value of the Score variable. For example, in some embodiments, only the IntersectScore () and RoadLengthScore () functions are used. Other permutations of the scoring function illustrated by the representative code include the relative weighting of the component functions so that some of the functions have a greater influence on the value of the Score variable. Thus, for example, in some embodiments, the contribution of the IntersectionScore () function to the Score variable is weighted up relative to the contribution of the RoadLengthScore () function. Such weighting schemes can be dynamically imposed based on factors such as the complexity of the route, the size of the viewing region used to represent the route, the presence of anomalies such as a road on the route that is much longer than any another road on the route, as well as user-specified preferences.

Additional refinement realizations of labels

Another important aspect of the overall process for producing a high-quality map is performed by the label layout module 688. The label layout module 688 places and optimizes the labels that correspond to the various roads on the road map. A new feature of the label distribution module 688 is that it will fix the label position for certain roads during refinement.

FIG. 9 illustrates one embodiment of the label dispensing module 688 (FIG. 6). Many different types of objective functions can be used to refine the position of labels in the procedure illustrated in FIG. 9.

ES 2 373 095 T3

Two such objective functions are described by lines 301 to 308 and lines 401 to 417 of the illustrative code. In the embodiments described above, a simulated annealing program was used to place the labels within a continuous range of positions of a region around the center of the road corresponding to the label. Such a region is called a constraint. The type of restriction used in the embodiments described above is illustrated in FIG. 17A. In FIG 17A, item 1802 illustrates the continuous range of positions that can be used to place the label corresponding to road 1802. Item 1804 serves as a constraint since the center of the label is constrained to lie somewhere within of element 1804. FIG. 17B illustrates the placement of tag 1806 at one such acceptable location.

The label arrangement module 688 described in this section is constructed under the definition of constraint used in the preceding claims. The definition of expanded constraint is used by the objective function in the simulated annealing program of label layout module 688 to identify a suitable label position, orientation, and style. Constraint components in the definition of expanded constraint include (i) a bounding box (eg, item 1704 in FIG. 17A), (ii) an orientation (eg, item 1710 in FIG. 17C, (iii ) a layout style (eg, FIG. 18A to 18F), and (iv) a scoring strategy.

The bounding box defines where the center of the label layout can be positioned. Thus, in FIG. 17B, ​​a label placed using the constraint defined by box 1704 can be positioned such that the center of the label falls anywhere in box 1704. Orientation vectors define how a label should be rotated. Label 1706 in FIG. 17A is positioned alongside a vector that is parallel to the longitudinal axis of the corresponding bounding box 1804. Using the expanded constraint definition, the labels can take alternate orientations. For example, the label can be oriented so that it is perpendicular to the longitudinal axis of the corresponding bounding box. FIG. 17D illustrates the placement of a label in a rotated position.

The layout style defines what text and images are created and how they are combined to make up the label when the given constraint is selected during annealing. FIG. 18 provides several styles of sample layouts. The layout style illustrated by FIG. 18A is a simple layout style in which the main name for a street or highway is represented. The layout style illustrated by FIG 18B combines an image of an arrow with the main name for a street or highway. The layout style illustrated by FIG. 18C combines the main name for a street or highway with the mile marking along the highway. The layout style illustrated by FIG. 18D provides a highway number as text placed on top of a shield image. The layout style illustrated by FIG. 18E provides a box of the words. Finally, the layout style illustrated by FIG. 18F provides a highway number placed on top of a shield image with miles marking along the corresponding highway.

The scoring strategy defines which base penalties are used with each of the constraints. The magnitude of the base penalty for a particular constraint is chosen considering the type of layout style that is associated with a constraint. For example, a layout style that does not include a distance tag (FIG. 18A, 18E) is penalized more than one that does (FIG. 18C). A representative scoring strategy in accordance with one embodiment of the present invention is provided in Table 1. Each of the rendering styles has a base weight and a position score. In the scoring strategy provided by Table 1, lower scores represent improved label positions. In addition, the scoring strategy provided in Table 1 is designed to provide an objective function that allows a distribution module 688 to find optimal positions for labels on the road map.

ES 2 373 095 T3

Table 1: Representative Scoring Strategy for Label Positions

<td>Distribution Style</td><td>Base Weight</td><td>Position Score</td><td>Warnings</td>

<td>Highway Shield</td><td> 0,0</td><td>+ penalty * (distance from the center of the label to the center of the corresponding road)</td><td>Applicable only to motorways with known motorway numbers</td>

<td>Road name directly above or below the road</td><td> 0,1</td><td>+ 0.1 for under the road vs. above the road + penalty * (distance from the center of the label to the center of the road)</td><td></td>

<td>Road name on the road extension</td><td> 0,3</td><td>+ penalty * (distance from the center of the label to the center of the road)</td><td>Applicable only to roads where the road continues past the intersection with the next or previous road (i.e. not a T intersection)</td>

<td>Road name + arrow pointing the road</td><td> 1.0</td><td>+ penalty * (distance from the tip of the arrow to the center of the road);</td><td></td>

<td></td><td></td><td>+ penalty for the angle between the label, the road and the horizontal or vertical screen + 0.0; 90 degrees + 0.6; and others + 1.0</td><td></td>

In the scoring strategy outlined in Table 1, the base score assigned to the base layout style is further defined by (i) the presence or absence of word boxes and (ii) if there is no distance label, a label of distance directly to the right, or a distance label directly below the label. Additionally all position scores in Table 1 are further determined by whether there is distance labeling and word boxing. When there is no distance label, an additional 1.5 units are added to the punctuation and when the road name is twenty characters or more and there is no text box an additional 1.0 units are added to the punctuation.

Turning attention to FIG. 19, an illustrative pre-processing phase in accordance with the present invention is illustrated. First, a highway 1902 is selected on the road map (FIG. 19A). Next, a random restriction definition for the road is chosen from a set of possible restriction definitions. Each of the constraints in the set of possible constraint definitions includes a bounding box definition, an orientation vector, a layout style, and a scoring strategy. For example, constraint definition 1904 (FIG. 19A) includes the illustrated bounding box, an orthogonal orientation, a leading name plus a distance arrangement, and a default scoring strategy. Other possible constraint definitions besides the 1904 arrow constraint are possible. For example, in FIG. 19B, other possible definitions of restrictions include extended road restrictions and highway shield restriction. The remaining steps in the illustrative pre-processing step are handled with the assumption that restriction definition 1904 is selected by the pre-processing procedure. Once a constraint definition has been selected, the next step is to randomly select a position within the bounding box that is associated with the constraint. In FIG. 19C, such a position is illustrated by element 1910. Finally, using the layout style and orientation vectors associated with constraint 1904, label 1912 is positioned for highway 1902 (FIG. 19D).

Turning attention to FIG. 20, an overview of the embodiment of layout module 688 that makes use of the expanded constraint definitions is illustrated. The procedure begins with the 2002 processing stage. In the 2002 processing stage a set of potential constraint definitions is associated with each of the labels to be placed on the scaled roadmap. Execution of processing step 2002 results in a set of potential restriction definitions, such as those depicted in FIG. 19B, which are associated with each of the tags to be refined by the tag layout module 688. It will be appreciated that the processing step 2002 will exclude restriction definitions that are not appropriate for a particular class of tags. For example, a restriction definition that includes a highway shield layout style will not be included within the set of potential restriction definitions associated with a label for a small road on the route map during the 2002 processing stage. During the 2004 processing stage, a constraint definition is selected for each of the labels in the scaled roadmap from the set of constraint definitions associated with

ES 2 373 095 T3 for each of the labels during the processing step 2002. In one embodiment of the layout module 688, an optimal constraint definition is selected for each of the labels from a set of heuristics. Such heuristics include, for example, rules for specifying an optimal restriction definition for a highway. In another embodiment of layout module 688, no set of heuristics is used to choose a constraint definition from the set of potential constraint definitions and a constraint definition is randomly selected for each of the labels from the set of constraint definitions associated with the tag during the 2002 processing stage. Once a constraint definition has been chosen for a tag in processing step 2004, the center of the tag is positioned within the bounding box associated with the constraint definition according to the orientation vectors associated with the definition of restriction. In one embodiment, the center of the label is positioned in the center of the bounding box. In another embodiment, the center of the label is positioned at a random location within the bounding box.

In the processing step 2006, a check is made to determine whether any label positions can be set. In the check, the boundaries of the label are compared to the constraint boundaries of each of the labels on the map. If there is no overlap between the boundaries of a given tag and the constraint boundaries of all other tags in the roadmap, then the given tag is fixed at its current position as there is no chance that the given tag will cut another tag during further refinement. In some embodiments, labels are set only in step 2006 if the restriction definition selected during processing step 2004 was based on a set of heuristics designed to select an optimal label. Thus, in such embodiments, when the restriction definition selected during the processing step 2004 is randomly selected, the label is not set during the processing step 2006.

During the processing stage 2008, an initial effective temperature t is selected and the counter i to one (2008) is set. In the processing stage 2010, the index label j from the set of labels that have not been set in the processing stage 2006 is randomly selected. The quality of the position of the index label j (S1) is measured using an objective function in the processing stages 2012 and in the processing stage 2014 the index label j is repositioned by the positioning of the label according to the bounding box, orientation vectors, and the layout style of a different constraint definition in the set of constraint definitions associated with the index tag j during the processing step 2002. In particular, the center of the index tag j is randomly positioned within the boundaries of the bounding box of the different constraint definition. In the processing stage 2016, the quality of the newly positioned index label j (S2) is measured. The objective function used during the 2012 and 2016 processing stage is any function capable of evaluating the quality of a label position on a roadmap. For this purpose, the objective function could be that of lines 301 to 308 or lines 401 to 417 of the illustrative code described in other embodiments of the label arrangement module 688 above.

When the quality of the index position j has improved (S₂ <S₁) (2018 - Yes), the new label position for index label j is accepted (2026). When the quality of the map has not improved (S2> S1) (2018 - No), there is a probability

- exp ^{- S k} * β that the new label position for index label j is accepted. The probability that the change in label position will be accepted decreases as the effective temperature t decreases. The probability function is implemented as the processing steps from 2020 to 2028 in FIG. 20. In the 2020 processing stage, exp is calculated^{- [IAS} ' * ⁵. In processing step 2022, a number Pran is generated, in the range from 0 to 1. If Pran is less than exp^{- l}^^S>'^kt] (2024 - Yes), the change made for the position of the index label j in the processing step 2014 is accepted (2026). If Pran is greater than exp^{- I (iS>}'^{k tl} (2024 - No) the change made for the position of the index label j in the processing step 2014 is rejected (2028). It will be appreciated that probability functions other than the function displayed in processing step 2020 are within the scope of the present invention. Actually, any probability function that is dependent on the effective temperature t is adequate.

The processing stages from 2008 to 2028 represent an iteration in the annealing procedure. In the processing stage 2030, the iteration count i is increased. When the iteration count i does not exceed the maximum iteration count (2032 - No), the procedure continues in step 2010. When the iteration count equals the maximum iterations indicator (2032 - Yes), the temperature is reduced effective t and the step counter (2034) is increased. Those skilled in the art will appreciate that there are many different possible types of schedules that are used to reduce the effective temperature t in various implementations of processing step 2034. All of these schedules are within the scope of the present invention. After processing step 2034, a check is performed to determine whether the simulated annealing program (2036) should be terminated. When it is determined that the annealing program should not be terminated (2036 - No), the procedure continues in step 2008 with the reset of iteration count i.

ES 2 373 095 T3

Layout templates

As road maps are often used when driving or navigating, it is important to present maps and text in a convenient format such as a simple 8.5 by 11 inch (21.59 by 27.94 cm) form. ). In one embodiment of the present invention, each of the shapes contains various image templates, such as the scaled road map or a conventional overview map, as well as text boxes for text directions, estimated distances, and time. In one embodiment of the present invention, predefined shapes are provided that define the layout and size of each of the image templates and text boxes. Example image templates and text boxes are provided in FIG. 21. FIG. 21A is a text box that provides header information while FIG. 21B is an image template that provides a scaled roadmap. There are different sizes of image templates to accommodate scaled roadmaps of various sizes. FIG. 21C is a text box providing text directions, FIG. 21D is an image template that provides an overview map, and FIG. 21E is an image template that provides a detailed map.

Several factors are used to consider which image template to use for a scaled roadmap. Such factors include, for example, the estimated aspect ratio of the scaled roadmap (e.g. the ratio of the total width of the scaled roadmap to the total height of the scaled map), the number of items (i.e. roads) on the scaled roadmap, and the global orientation of the scaled roadmap. Sample code for a procedure to select an image template is provided on lines 700 to 723 of the sample code.

(700) function SelectTemplate () {(701) Aspect Ratio = map Estimate Aspect Ratio ();

(702) integer num_roads = map GetNumStepsOrig ();

(703) (704) if ((Aspect Ratio &lt;0.60) || ((Aspect Ratio &lt;0.70) &amp;&amp; (num_roads &lt;15))) {(705) select elongated vertical image template for scaled roadmap ( FIG. 22A) (706) if (num_roads &lt;20) height_scaled_path_map = 500);

(707) if not {(708) // this is a long path, so extra pixel is required in vertical dimension (709) scaled_path_map_height = 700; } (710) yes no, yes (Aspect ratio> 2.0) {(711) select elongated horizontal image template for scaled roadmap (FIG. 22B) (712) yes no {(713) select square image template for the scaled route map (FIG. 22C) (714) if (num_roads <15) height_scaled_route_map = 400;

(715) if not, yes (num_roads &lt;25) {(716) // this is a long route (717) height_route_map _scaled = 500;) (718) if not {(719) // This is a really long route ( 720) scaled_path_map_height = 600;} (721)}} (722) set dimensions of text, overview map, detail map, and scaled roadmap (723) to the default values ​​in this template}

In the sample code, the aspect ratio of the scaled roadmap is estimated on line 701 and the number of items or roads in the roadmap is determined on line 702. On lines 704 and 705 of the sample code , a decision to choose an elongated vertical image template 2202 (FIG. 22A) for the scaled roadmap is done when the estimated aspect ratio of the scaled roadmap is less than 0.6 or when the aspect ratio is less than 0.7 and the number of items or roads in the map of scaled path is less than 15. The vertical elongated image 2202 has a variable height that is determined by lines 706-709 of the sample code. Accordingly, when the number of roads on the road map is twenty or less, the vertical elongated image 2202 is assigned a height of 500 pixels. When, the number of roads on the road map is more than twenty, the vertical elongated image 2202 is assigned a height of 700 pixels.

When the aspect ratio of the scaled road map is greater than 2.0 (line 710 of the example code), the elongated horizontal image template 2204 (FIG. 22B) (line 711) is selected. For roadmaps scaled with any other aspect ratio, square image template 2206 (FIG. 22C) (lines 612-613) is selected. Like item 2202, item 2206 is of a variable height that is determined by the number of roads on the scaled roadmap as shown in lines 715 through 720 of the sample code. Finally, in lines 722 to 723 of the sample code, the dimensions of the remaining image templates are provided and the 2250 text boxes that are provided in the output form are positioned around the

ES 2 373 095 T3 image template including the roadmap scaled to obtain a 2260, 2270 or 2280 fixed dimension shape.

Context information

All the information represented in a roadmap can be divided into two categories: (1) the route information and (2) the context information. Route information includes information that is necessary to follow a route. The roads along the route and their labels are examples of necessary route information. Context information is secondary information that is not directly about the route, and is not necessary to communicate the basic structure of the route. Examples of context information include landmarks, roads that intersect the road (ie crossing streets), and the names of cities, parks, and bodies of water near the route. Context information can make the geography of the route easier to understand, provide validation that the navigator is still on the correct route, and help identify important decision points along the route.

In one embodiment of the present invention, two basic types of context information are handled, crossing roads and point characteristics. In this embodiment, the names of the cities are considered as characteristics of the point. Adding context information to the roadmap first requires deciding what context information should appear on the roadmap. This choice is made difficult by the fact that the context that is important to one person is not necessarily important to another person. Although some basic rules and preferences that can be used to choose context information are described in the following example, it will be appreciated that the present invention is modeled such that any context selection algorithm can be used.

In one example, each major crossing street that intersects the roads on the main route of the route map, as well as the first crossing street after each of the turn points on the main route is added to a route map as context information. Cross streets before the turn helps the navigator monitor progress toward the turn, and the last crossing street before the turn provides a warning that the turn is approaching. The first crossing street after the turn helps the navigator determine that the proper turn has been missed. The three main classes of point features useful for use on a road map are: (i) highway exit signs, (ii) roadside buildings and businesses and turn points, and (iii) city ​​names. preferably highway exit signs, particularly the exit number, are included because they make it much easier for the navigator to figure out which exit to take to access the next road on the route. Selecting which businesses to include is more difficult, as there is no simple way to identify the most outstanding buildings or businesses along a route. However, if the map was designed for a particular business partner such as McDonalds, all McDonalds along the route can be added automatically. Finally, it is desirable to include most of the major city names near the main route. For example, for a route between Santa Cruz CA, and Hayward CA, the labels for Cupertino, San José, Milpitas, and Fremont are added to the route map as context information. Cities are chosen based on their proximity to the route, their population, and their area. The names of the cities help the navigator in understanding the global geographical position and the orientation of the route.

Once the context information has been selected, it should be placed on the roadmap. The context can be set by the annotation module 690 at any time after the roads have been established on the main route by the road layout module 686 (FIG. 1). The context layout is generally done right after the tag layout module 688 runs. If context is placed before label layout, the label layout scoring algorithm used by label layout module 688 is modified to check for intersections between context and labels. In one embodiment, the selection of context information to be displayed on the map is not guaranteed that it will actually be displayed and displayed. If the context layout algorithm used by annotation module 690 cannot find a better placement for the context information, the algorithm may choose not to include this context information.

In one embodiment of the present invention, the approach used by the annotation module 690 to place the crossing streets is very similar to the approach used for the placement of the point features on the road map. The algorithm for placing the crossing streets will be described in detail first. Next, the differences in the algorithm used in one embodiment of the annotation module 690 to place the point features will be briefly described.

Placement of crossing streets. FIG, 23 shows a scaled route map with various crossing streets located along the route. A crossing street is specified by (i) the intersection point of the street with the main route, (ii) the name of the crossing street, (iii) the shape points that define the shape of the street, and optionally , (iv) the importance of the crossing street. The importance value for each of the crossing streets can either be supplied or it can be calculated as the first stage in the placement of the crossing streets. In one embodiment, the names of the crossing streets and their relative importance are obtained from the context database 696 (FIG. 1). In another embodiment, predefined rules are used to calculate the relative importance of a particular crossing street. The last major crossing street before a turning point on the main route is considered

ES 2 373 095 T3 relatively important because such crossing streets are useful as a warning signal that the turn is approaching. Thus these crossing streets are given the highest relative importance. In this embodiment, the crossing road immediately after the turn point is given the next highest importance because such streets help navigators to check whether they have missed the proper turn. Crossroads are especially useful near the destination of the route, where the navigator is presumably less familiar with the territory. Therefore these crossing streets are given a higher importance than the crossing streets near the beginning of the route.

In the present invention, two search-based approaches are provided for establishing the crossing streets. The first approach considers each of the crossing streets, one at a time, in order of importance. If the importance is equal, the crossing street is randomly selected from the equally important crossing streets. Next, a search is made for a good placement for the road. If a good placement is found, the junction road is drawn in the rendering phase of the procedure. If a good placement is not found, the crossing street is not drawn during the rendering phase and is therefore not included in the map.

The second approach to establishing crossover streets looks for a good placement of all crossover streets simultaneously. All crossing streets are placed on the map. Each of the crossing roads can also be hidden rather than laid. Then the placements are optimized.

The first approach to setting the crossing streets is faster than the second approach but may not find an optimal placement for all the crossing streets. The second approach to selecting the crossing streets may take longer than the first approach but is less constrained and therefore can produce a better overall placement.

Regardless of whether the first approach or the second approach is taken by the annotation module 690 to set the crossing streets, a search-based approach is performed to optimize the placement of the crossing streets. This requires two basic functions: disturbance and punctuation. The disturbance function is used to change the layout of a particular crossing street while the scoring function evaluates the current placement of the crossing streets. The scoring function is used in the search-based approach to determine whether the disturbance improved the layout of the map. Such determination is made according to a search algorithm. Representative search algorithms that can be used include greedy algorithms, gradient descent, simulated annealing, Tabu searches, and A * as discussed by Zbigniew and others in How to Solve It: Modern Heuristics, Springer-Verlag, Berlin, Germany, 2000, Greedy A * / IDA * searches, simulated annealing, and choline scaling (gradient descent) as reviewed by Russell et al. In Artificial Intelligence: A Modern Approach, Prentice Hall, 1995, and genetic algorithms as examined by Golderg in Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

In one embodiment, the disturb function is designed as follows:

Disturb () randomly select one of the following variables and change it:

- the position of the intersection of a crossing street with the main path;

- the position of the label of the crossing street; or

- if the crossing street is included in the map or if it is hidden

When Disturb () changes the position of the crossing street label, the disturbance is subject to the restriction that the street label falls within a predetermined area that includes the intersection of the crossing street. In one embodiment of the present invention, the shape of the predetermined area is a square and the square is centered on the intersection of the crossing street. Accordingly, the position of the crossing street label that is associated with the crossing street can be disturbed by an amount as long as the crossing street label remains in the square. Once the position of the intersection of the crossing street with the main path and the crossing street label has been chosen, the crossing street is extended to pass under or above its label and pass slightly beyond from the intersection with the main road.

In one embodiment, the scoring function that is used to evaluate disturbances is designated as follows:

Scoring () the placement of each of the crossing streets is scored based on several criteria as follows:

- the distance between the current intersection point of the crossing street and the main path and the true point of intersection between the crossing street and the main path;

- the number of other objects on the map that overlap the crossing street, weighted by the amount of overlap;

- the number of other objects on the road map that overlap the label of the crossing street, weighted by the amount of overlap;

ES 2 373 095 T3

- the position of a label of the crossing street next to the crossing street, using the same restriction-based score as in a normal label arrangement;

- the amount of visual clutter / density around the crossing street; Y

- if the crossing street is hidden; hiding the crossing street is penalized by an amount proportional to its importance so that it encourages the search to place the crossing streets rather than simply hiding all of them.

The most complicated aspect of the scoring criteria is the notation for density or visual clutter. The present invention encompasses several different methods of calculating visual density for a fixed focus region centered on the street / crossing tag. To appreciate these procedures, reference is made to FIG. 24 showing a portion of the route map 2402 that includes a focus area 2404 with a crossing street for which a measure of visual clutter is sought. Using FIG. 24 for reference, representative metrics may include:

(1) Convolve a pixel-based image of the roadmap with a Gaussian kernel in the focus region 2404 using the luminance value of each of the pixels within the focus region.

(2) Calculate the area of ​​each of the objects in the focus region 2404 multiplied by the average luminance for the object. Box 2406 drawn in FIG. 24 illustrates the area of ​​an object in the focus region 2404. The result of multiplying the target area and the average luminance is divided by the distance from the center of the crossing street to the center of the object. Visual density is fixed to the sum over all objects in the focus region. An equation that describes this metric is:

Total objects in focus area

Σ i-1

Object Area ¡x Average Object Luminance ¡

Distance between object i and the center of the focus region

Metric 1 is expensive from a computational point of view. Metric (2) is faster, but a less accurate approximation of visual density. When one crossing street is established at a time, disturbances are made between disturbance and score until the score reaches some acceptable threshold, and the placement is maintained, or the iteration count reaches a maximum. If the score never goes below the threshold, the crossing street is not included in the roadmap. When all crossing streets are set at the same time, a variety of search-based algorithms can be used to minimize the overall score. In such embodiments, the overall score is calculated as the sum of scores for each of the crossing streets. Representative search-based algorithms that can be used include greedy algorithms, gradient descent, simulated annealing, Tabu search, and A * as discussed by Zbigniew and others in How to Solve It: Modern Heuristics, Springer-Verlag, Berlin , Germany, 2000, A * / IDA * greedy searches, simulated annealing and hill scaling (gradient descent) as reviewed by Russell et al. In Artificial Intelligence: A Modern Approach, Prentice Hall, 1995, and genetic algorithms as examined by Golderg in Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

Placement of point features. FIG. 25 shows a road map with various point characteristics, such as exit number, restaurant locations, and city names included. A point feature is specified by:

- An ideal location (latitude, longitude) for the point feature and any linear or circular constraint region specifying the acceptable positions for the point feature. In the case of a city name, the characteristic would be allowed to appear anywhere within a circle inscribed within the city limits. This region must be deformed within a non-uniform coordinate system of the map;

- the name of the feature, or an image, to show the location of the feature; Y

- optionally, the importance of the characteristic.

Just as in the case of crossing streets, the importance of a point feature can be provided or can be calculated during layout. In one embodiment, all highway exit signs are given equal importance unless their importance values ​​are provided a priori. For city names, importance is calculated by multiplying the proximity of the city region to the route, the city population, and the city area. Thus in this embodiment, large cities, with high populations, close to the route are considered more important. Buildings and businesses are given higher importance when they are at intersections as opposed to those next to roads on the road map. Furthermore, according to this embodiment, a higher importance is assigned to businesses that are on smaller roads near the beginning or end of the route than those that are on longer roads such as expressways and expressways.

ES 2 373 095 T3

As with crossover streets, point features can be placed one at a time, or all at the same time. The ideal location and its surrounding constraint region are well defined in the original coordinate system of the constant scaled map. To place the point features first we must deform the ideal point and constraint region within the non-uniform coordinate system of the scaled roadmap. Since the coordinate system is non-uniform, a constraint-based optimization procedure is used to perform the deformation. A variety of deformation-based deformation techniques have been developed and are known as transformation techniques. See, for example, Metamorphoses of Characteristics Based Images by Beier and Neely, Proc. SIGGRAPH 92, 35-42 (1992). Also, for an overview of deformation techniques see Deformation and Transformation of Graphic Objects by Gomes et al., Morgan Kaufmann (1998). Any of the procedures described in these references can be used to deform the ideal point and constraint region into a non-uniform coordinate system of the scaled roadmap.

The main differences in the search-based layout between crossing streets and point features are in the disturbance and scoring functions, which are described below. When the point characteristics are refined the disturbance and scoring functions have the format:

Disturbance ()

Randomly select one of the following variables and change it

- the position of the point feature within the region of acceptable positions.

- whether or not the point feature is included on the map.

Punctuation ()

The placement of each of the point characteristics is scored on the criterion:

- the number of other objects on the map that overlap with the point characteristic, weighted by the amount of overlap;

- the distance between the current location of the point feature and its ideal location;

- if the point characteristic is hidden - again the penalty is proportional to the importance of the point characteristic; Y

- amount of visual clutter / density.

Vertical setting techniques

In some embodiments of the present invention, the memory 668 of the server computer 624 includes a map verticalization module 698 (FIG. 6). The verticalization module 698 is used to optimize the orientation of the scaled roadmap with respect to the dimensions of a given viewing region. Optimizing the map orientation is particularly advantageous in cases where the size of the viewing region used to render the road map is small. In such situations, typically only a portion of the scaled roadmap is rendered. When only a portion of the scaled roadmap is displayed, the user is provided with the option to scroll the scaled roadmap to view the entire route. To avoid confusion, it is advantageous to orient the scaled roadmap so that the longitudinal axis of the scaled roadmap coincides with the direction of travel. In one embodiment the direction of travel is vertical and the scaled road map is oriented by the map verticalization module so that the longitudinal axis of the scaled road map is vertical. Aligning the longitudinal axis of the scaled road map with the direction of travel maximizes the amount of information that is represented in a miniature viewing region and provides a convenient mechanism for the consistent provision of map layouts. The user can review the entire rotated scaled map using the scroll option.

Mapping the map vertically is particularly advantageous on handheld devices such as personal digital assistants (PDAs). Given the dimensions of the viewport of a typical PDA, it is desirable to offer scaled route maps that have the dimensions constant by Y, where Y varies according to the number of stages or the distance of the route within the route map. In this way, if the route is short enough, the entire scaled route map is rendered in the view region of the PDA. However, if the route includes multiple stages and has a fairly long longitudinal axis, the longitudinal axis is oriented so that it is aligned with the scroll bar. In this way, the user obtains a consistent arrangement with only vertical scrolling.

Now that an overview of the benefits of map orientation has been covered, a procedure for calculating map orientation is described. First, the position of each of the intersections along the main path is calculated on the scaled roadmap. These intersection points are then fixed with a probability distribution. The probability distribution could be, for example, a binomial distribution, a Poisson distribution, a Gaussian distribution, or any other suitable probability distribution. When using a Gaussian distribution, the center of the distribution is the mean of the intersection points, the

ES 2 373 095 T3 axes of the distribution are the eigenvectors of the covariance matrix, and the extensions of the distribution are the eigenvalues ​​of the covariance matrix. The probability distribution defines the axes and the extents along those axes for the route. As illustrated in FIG. 11A, from these axes, the narrowest bounding box 1100 containing the entire path is determined. From bounding box 1100, the longest (dominant) axis of the path is calculated. The direction of the longest axis is used to determine the amount by which the scaled roadmap is rotated so that it runs in a predetermined direction. In FIG. 11, the beginning of the route is marked by a hatched circle and the end of the route is marked by an open circle. As the starting point of the route is known, it is possible to rotate the map so that the starting location is always at the bottom (FIG. 11B) or always at the top (FIG. 11C) of the region. Of vision. Thus, the verticalization procedure is used to ensure that the limited space of the viewing region is fully utilized and to ensure that the starting location of each of the maps represented rests consistently in the same region of the region. Of vision.

It will be appreciated that if the aspect ratio of the probability distribution used to determine the axes of the scaled road map indicates that the map is roughly square, the verticalization is not performed. In one embodiment, the probability distribution used is a Gaussian distribution and verticalization is not performed when the aspect ratio of the scaled roadmap is less than or equal to 1.98.

The sample code used to calculate the longitudinal axis on a scaled roadmap and rotate the scaled roadmap is provided below.

<td> (801)</td><td>buleano Map :: Put in vertical ()</td><td></td>

<td> (802)</td><td> {</td><td></td>

<td> (803)</td><td>Vector2 Map Orientation [2];</td><td></td>

<td> (804)</td><td>double extension [2];</td><td></td>

<td> (805)</td><td>SetGauss Points (numPtsIntersection, PtsIntersection, center, axes,</td><td>extensions);</td>

<td> (806)</td><td colspan="2">// Verticalize the map only if the aspect ratio in coordinate axes&gt; 1.98</td>

<td> (807)</td><td colspan="2">// Calculate the Aspect Ratio as extent [1] / extent [0] as it should be</td>

<td> (808)</td><td>// since the second extent is classified to be the longitudinal axis.</td><td></td>

<td> (809)</td><td>double Aspect Ratio = extent [1] / extent [0]</td><td></td>

<td> (810)</td><td>yes (Aspect Ratio&gt; 1.98 {</td><td></td>

<td> (811)</td><td>// Assume that the Map Orientation vectors are of unit length</td><td>. The vectors of</td>

<td> (812)</td><td colspan="2">// orientation are sorted in increasing order, so the second is used to</td>

<td> (813)</td><td>// calculate the angle of rotation</td><td></td>

<td> (814)</td><td>double angle = atan2 (OrientationMap [1] .v, OrientationMap [1] .u);</td><td></td>

<td> (815)</td><td>Rotate (- angle);</td><td></td>

<td> (816)</td><td>return true;</td><td></td>

<td> (817)</td><td> }</td><td></td>

<td> (818)</td><td>return false;</td><td></td>

<td> (819)</td><td> }</td><td></td>

<td> (820)</td><td>null SetGausspoints (integer NumPoints, const Vector2 * point,</td><td></td>

<td> (821)</td><td>Vector2 &amp; Center, Vector2 Axis [2], double Extension [2]</td><td></td>

<td> (822)</td><td> {</td><td></td>

<td> (823)</td><td>// Calculate average of points</td><td></td>

<td> (824)</td><td>for (int i = 1; i &lt;NumPoints; i ++)</td><td></td>

<td> (825)</td><td>Center + = Point [i]</td><td></td>

<td> (826)</td><td>Center / = NumPoints</td><td></td>

<td> (827)</td><td>// Calculate covariances of points</td><td></td>

<td> (828)</td><td>double SumXX = 0.0, SumXY = 0.0, SumYY = 0.0</td><td></td>

<td> (829)</td><td>for (i = 0; i &lt;NumPoints; i +++)</td><td></td>

<td> (830)</td><td> {</td><td></td>

<td> (831)</td><td>Vector2 Diff = Point [i] - Center;</td><td></td>

<td> (832)</td><td>SumXX + = Dif.u * Dif.u:</td><td></td>

<td> (833)</td><td>SumXY + = Dif.u * Dif.v;</td><td></td>

<td> (834)</td><td>SumYY + = Dif.v * Dif.v;</td><td></td>

<td> (835)</td><td> }</td><td></td>

<td> (836)</td><td>SumXX / = NumPoints;</td><td></td>

<td> (837)</td><td>SumXY / = NumPoints;</td><td></td>

<td> (838)</td><td>SumYY / = NumPoints;</td><td></td>

<td> (839)</td><td>// solve autosystem of the covariance matrix</td><td></td>

<td> (840)</td><td>Autofunction E (2);</td><td></td>

<td> (841)</td><td>E (0, 0) = fSumXX;</td><td></td>

<td> (842)</td><td>E (0, 1) = fSumXY;</td><td></td>

<td> (843)</td><td>E (1, 0) = fSumXY;</td><td></td>

<td> (844)</td><td>E (1, 1) = fSumYY;</td><td></td>

ES 2 373 095 T3 (continued) (845) E.ResolverAutoSystem ();

(846) Axis [0] .u = E.Get Autovector (0,0);

(847) Axis [0] .v = E. GetAutovector (1,0);

(848) Axis [1] .u = E. GetAutovector (0,1);

(849) Axis [1] .v = E. GetAutovector (1,1);

(850) Extension [0] = E.GetAutovalue (0);

(851) Extension [1] = E.Get AutoValue (1);

(852) }

On line 805 of the sample code, a call is made to the SetGaussPoints procedure. The SetGaussPoints procedure is coded by lines 820 to 852 of the sample code. On lines 823 to 826 of the sample code, the SetGausspoints procedure calculates the average of all intersections on the scaled roadmap. On lines 827 to 838 of the sample code, the SetGaussPoints procedure calculates the covariances of the intercepts. On lines 839 to 851 of the sample code, the SetGausspoints procedure solves the autosystem of the covariance matrix. This information is used in the main body of the sample code. More specifically, on line 809 of the sample code, an aspect ratio is calculated. As defined herein, the aspect ratio is the ratio of the lengths of the two axes corresponding to the scaled roadmap, as determined by the SetGauss Points procedure. In the embodiment described by the illustrative code, the scaled roadmap is not reoriented if the aspect ratio is less than 1.98. If the aspect ratio is greater than 1.98, then the scaled roadmap is rotated so that the longest of the two axes calculated by the SetGaussPoints procedure lies in a predetermined direction such as vertical. This rotation is done by lines 814 and 815 of the sample code.

Although the above example describes the verticalization of a scaled roadmap, it will be appreciated that the verticalization technique is not limited to scaled roadmaps. Actually, any image that has a collection of points that can be fixed by a probability distribution can be optimized to represent over a viewing region using the techniques of panning.

Finding empty space

As discussed above, the annotation module 690 (FIG. 6) is used to place terrain markings and other annotations on the scaled roadmap to help guide the user. However, the identification regions of the map that are suitable for the placement of such annotations present a special problem. Simply stated, the problem is the need to use efficient procedures to identify suitable regions of the map for placement of the annotations. Suitable regions are regions of the map that are not overpopulated with other objects. In FIG. 12, the North arrow annotation 1202 is added to the route map to indicate the direction. In one embodiment of the present invention, the placement of the North arrow annotation 1202 is restricted to the upper left quadrant of the map to present a consistent appearance between maps. Thus, the problem formulated by FIG 12 is the identification of regions in the upper left corner of the road map that is suitable for the placement of the North arrow annotation 1202.

FIG. 13 details the processing steps used to efficiently identify gaps on a road map in accordance with one embodiment of the present invention. This free space is used to place annotations and labels on the road map. In processing step 1302, the map is split into a grid. Typically, the grid used in processing step 1302 is uniform, so that each of the cells in the grid is the same size. The number of objects on the road map that touch each of the grid cells produced in the processing step 1302 is tracked. In this way, it is possible to determine discrete areas of the road map that have relatively few objects. At processing step 1304, candidate cells of the grid are identified within which the target entry can be placed. In some embodiments, the region in which the candidate cells of the grid are searched is restricted to a specific region of the road map. In one example, a bounding region is assigned to each of the city labels in which the label can be placed. This bounding region is close to the actual city on the road map.

When the annotation or label is larger than a single grid cell, processing step 1306 is used to search for grid cells with enough vacant adjacent grid cells to contain the object. If no candidate is found after search 1306 (1308 - No), a grid subdivision scheme is started (1310). Such subdivision is necessary to search through the map at a higher resolution to identify a set of adjacent grid cells that can be used for annotation or labeling.

Processing step 1310 is implemented using any one of a number of different

ES 2 373 095 T3 possible grid subdivisions. For example, various schemes that have been used for partitioning of three-dimensional space in disciplines such as ray tracking can be adopted for use in two-dimensional roadmap space. Such schemes are found in An Introduction to Ray Tracking, Ed. Andrew S. Glassner, Academic Press, Harcourt Brace Jovanovich, Publishers, New York (1989), In one embodiment, the grid subdivision scheme used in processing step 1310 is a form of uniform spatial separation such as that discussed in Section 5.2 of An Introduction to Ray Tracking id. For example, in a uniform spatial separation grid scheme, each of the original grid cells is divided into four cells. In another embodiment, the grid subdivision scheme used in processing step 1312 is a non-uniform spatial subdivision such as discussed in Section 5.1 of An Introduction to Ray Tracking id. Non-uniform spatial subdivision techniques are those that divide space into discrete regions of variable size as a function of the density of objects present in space. Thus, in a non-uniform spatial subdivision approach, the portions of the roadmap that are more densely occupied by objects such as roads, labels, and annotations, are subdivided into smaller grid cells than the roadmap portions. which are sparsely populated.

After the route map has been subjected to a grid subdivision scheme in processing step 1310, the procedure continues to loop back to processing step 1304. When processing step 1304 is executed again, A search is conducted for candidate cells of the grid within which the label or annotation can be placed using the grid subdivision generated in processing step 1310. What's more; When the annotation or label is too large to fit within a single grid cell, a search is identified for adjacent grid cells that can collectively accommodate the label or annotation. Processing steps 1304, 1306, 1308, and 1310 are repeated until a candidate position is found on the road map (1308-Si). In some embodiments, processing steps 1304, 1306, 1308, and 1310 are only repeated a predetermined number of times. If, after processing steps 1304, 1306, 1308, and 1310 have been repeated a predetermined number of times, a candidate location has not yet been identified, the annotation is rejected and not placed on the route map. In some embodiments, when a label or annotation has been geometrically constrained to a particular region of the route map and no candidate position has been found on the route map, step 1304 and / or 1306 is repeated using less stringent constraints. For example, when a city tag is restricted to being within a fixed region of the geometric city center on the roadmap and no candidate position is identified in the fixed region during a first pass through the stages of processing 1304, 1306, 1308 and 1310, the processing step 1304 and / or 1306 is repeated using a larger fixed region centered on the position of the city on the road map.

When the processing step 1304 or 1306 identifies multiple candidate positions in which to place the target label or annotation (1312 - Yes), the candidates are evaluated by an evaluation mechanism that considers the density of objects in the grid cells that are neighboring of the candidate position. In some embodiments, the candidate location that has neighboring grid cells with the lowest occupancy is selected. In other embodiments, factors other than the occupancy of neighboring cells are considered. For example, in some embodiments, candidate evaluation is a function of both the occupancy of neighboring cells as well as the absolute distance between the candidate position and some reference point. In such embodiments, candidate positions that are closer to a benchmark are weighted upward relative to candidate positions that are farther from a benchmark. Such evaluation embodiments are useful for city labels, road labels, and for the placement of geographical markings on the ground. When a single candidate position has been selected by processing step 1314, or a single candidate position has been found by processing step 1306 (1316), the annotation or label is placed at the candidate position and the procedure ends (1318) .

FIG. 14 illustrates how the spatial subdivision of a road map is used to identify suitable grid cells for the placement of the North Arrow 1202 annotation. In FIG. 14, the route map is divided into a grid in accordance with processing step 1302 (FIG. 13). A candidate cell of the grid within which the annotation can be placed is identified in processing step 1304. In this example, step 1304 is constrained to the upper left corner to consistently place the North arrow annotation 1202 in this region of the map. Because step 1304 successfully identified a candidate grid cell using the initial partition calculated in processing step 1302, there is no need to initiate a grid subdivision scheme 1310 and repeat processing steps 1304, 1306, and 1308. . Instead, the North arrow annotation 1202 is placed in an empty grid cell that is bordered by grid cells that have the least possible occupancy according to processing step 1314.

FIG. 15 illustrates a situation that occurs when processing step 1304 and / or 1306 (FIG. 13) attempts to identify a contiguous grid cell or set of grid cells in a restricted area and no candidate grid cell is identified. In FIG. 15, the tag Somewhere, USA 1502 is restricted to the area identified by the oval 1504. However, the initial grid generated by the processing step 1302 (FIG. 13) has failed to produce a suitable candidate cell from the grid (1308 - No). Therefore, the subdivision scheme of grid 1310 is executed. FIG. 16 represents the roadmap after using a uniform spatial separation to subdivide only the grid cells in the restricted area of ​​the

ES 2 373 095 T3 route map. In this subdivision, each of the original grid cells in the restricted area is subdivided into four new grid cells. Next, processing steps 1304 and 1306 are repeated using the new grid scheme. Since the tag Somewhere, USA 1502 is too long to set in the new grid cells, the processing step 1304 will fail. However, when processing step 1306 is executed, a candidate location that is composed of two adjacent cells in the grid is identified and the label is placed at the identified candidate location (1308 - Yes, 1312 No, 1316, 1318). FIG. 16 shows the placement of the label Somewhere, USA 1502 after the execution of processing step 1318.

In some embodiments of the present invention, the spatial subdivision scheme used in processing step 1310 is facilitated by the use of a hierarchical data structure known as the Quadtree region. See, for example, Applications of Spatial Data Structures, by Hannan Samet, Addison-Welsley Publishing Company, New York (1990), pages 2-8. A Quadtree region is a hierarchical data structure that is based on the successive subdivision of a limited image arrangement within four quadrants of the same dimension. In the classical application of a Quadtrre region, if a given arrangement does not consist entirely of ones or entirely of zeros, it is subdivided into quadrants, sub-quadrants, and so on, until blocks are obtained that consist entirely of ones or by integer of zeros. In this way, the image is subdivided using a variable resolution data structure. The Quadtree region is used in some embodiments of the present invention in the 1310 grid subdivision scheme. In such embodiments, the grid subdivision scheme only subdivides the selected grid cells into the initial grid. Typically, the cells in the grid that are selected by subdivision are chosen from the restricted area.

Trip Tiks and inserts

In some cases, when a map is scaled unevenly, it is difficult to make all roads visible within a given viewing region. Due to this difficulty, some embodiments of the present invention include a 699 map splitter module (FIG, 6). The map splitting module 699 makes use of inserts and / or Trip Tiks when it is difficult to make all roads visible within a given viewing region. Map splitting module 699 includes algorithms for determining when inserts and TripTiks should be used within a scaled route map. When a determination is made that an insert should be made, the map splitting module decides what portion of the map should be boxed, and where the insert should be placed within the main scaled roadmap.

TripTiks. When a route contains a large number of roads and segments, it may not be possible to scale all the roads so that they are large enough to be readable even within the image size. In this situation it is desirable to slice the scaled route map into several separate segment maps. In one embodiment of the present invention, map splitting module 699 uses the following algorithm to determine whether a scaled route map should be split into a set of segment maps:

- generate an intermediate map that includes each of the roads (element);

- define a maximum number of elements (M) allowable in any given map; Y

- when a map contains S roads (elements), where S> M, then divide the map evenly into N segment maps so that N> S / M.

However, in some cases some additional issues are considered. One such issue is the means by which the main route on the road map is connected through a plurality of segment maps. Various procedures for the representation of such connectivity information in some embodiments of the map splitting module 699 include:

- the use of a special connection point icon at the end point of the last road on the first segment map and the use of the same special connection icon at the start point of the first road on the subsequent segment map ; Y

- share some roads between each of the successive segment map pairs.

Furthermore, connectivity between successive segment maps is ensured by preserving the shape of the main route and in particular the shape of any roads shared through successive segment maps. To ensure that the shape of the roads shared through successive segment maps remains exactly the same on each of the segment maps, the simplification of the shape is preferably done for the entire route on the intermediate map as a set, as opposed to to the maps in separate segments.

The problems that the map splitting module is designed to alleviate and the algorithms used in some embodiments of the map splitting module 699 are illustrated with reference to FIGS. 26 to 28. FIG. 26 describes an entire route in a single image 2602. Although the entire route is visible, the map is very cluttered and would be difficult to use while driving. Also, if the route has more roads (elements) it would not be possible to label all the roads on the route. FIG. 27 splits image 2602 (FIG. 26) into two separate segment maps 2702 and 2704 which, taken together, comprise the route map of FIG. 26. The addresses in

ES 2 373 095 T3 segment maps 2702 and 2704 are more legible and understandable than the corresponding addresses in image 2602.

Returning to FIG. 28, the importance of preserving the shape of shared roads is illustrated through successive segment maps. In FIG. 28A, an intermediate map 2802 is shown that is about to be divided into two segment maps by the breakpoint 2804 between element CA-17 and Autovía Cabrillo. In FIG. 28B, intermediate map 2802 has been divided into segment maps 2810 and 2820. Both segment maps 2810 and 2820 have the full shape. In contrast, in FIG. 28C intermediate map 2802 has been divided into segment maps 2830 and 2840 which do not retain the original shape of intermediate map 2802. That is, in FIG. 28C the route shape has been simplified separately in segment maps 2830 and 2840. As a result, element 2834 Autovía Cabrillo has a different shape in segment maps 2830 and 2840. FIG. 28C represents an undesirable representation of the global route corresponding to the elements in maps of successive segments, that is to say, Autovía Cabrillo has a different shape. A more desirable situation is depicted in FIG. 28D. In FIG. 28D simplification of the route shape is performed on intermediate map 2802 to divide the intermediate map into segment maps 2850 and 2860.

Some routes, called multi-segment routes, contain multiple points on the path between the start point and the end point of the main route. Multi-segment routes are handled many like Trip Tiks in one embodiment of the present invention. Consequently, the multi-segment route is divided into separate segment maps at each of the trajectory points: the first image shows the route from the start point to the first point of the trajectory, the second image shows the route from the first point of the path to the second point of the path, etc. With multi-segment routes, the same repeating convention is used for a connection icon, in this case a path point icon, and / or a set of shared roads across successive maps. Furthermore, the simplification preferably occurs before dividing the route so that the shape of each of the roads and the overall shape of the route does not change in each of the images.

Inserts

In the map presentation phase, two objectives are optimized. The first goal is to ensure that all roads on the roadmap are large enough to be legible. The second objective is to maintain the overall shape of the route, as well as the position of all intersection points between roads. Despite the flexibility in road scaling provided by the present invention, it is difficult to achieve both objectives for some roads in a single image. FIG. 29 illustrates how it is sometimes difficult to fully optimize for both goals. In scaled roadmap 2902 depicted in FIG. 29, it is readily apparent that:

1) Some roads are too small to maintain overall shape, or to maintain intersection points. Readability has been sacrificed in favor of minimizing shape and topological distortions.

2) The scaling of many small roads causes the overall shape of the road to be severely distorted. In this case, the global shape has been sacrificed to maintain readability.

3) Scaling short roads so that they are legible causes a false intersection. In this case, the global topology has been sacrificed to maintain readability.

One solution for such routes is to find the set of roads that must remain small to maintain the topology or intersection points and display them in a separate insert image. For example, in FIG. 29, to maintain the intersection between I-74 (2904) and E. Cabin Town Rd (2906) all roads between the two roads are kept very short. By including insert 2908, however, it is possible to increase the road labels between 2904 and 2906 and label these intermediate roads as well. Additional examples of scenarios in which inserts are beneficial are provided with reference to FIGS. 30 and 31. In FIGS. 30 and 31, short roads causing distortion or false intersections are placed in an increased size in circular inserts 3002 and 3102 respectively. By placing the short roads in an augmented insert, the corresponding roads can be shortened on the main scaled route map to the point where distortion of the overall route shape is acceptable or false intersections are avoided. In one embodiment, the insert image is created by running the entire map layout algorithm encoded by the road layout module 686 only on the roads in the insert. Roads that are displayed in the inset and that are too small to label in the main scaled roadmap are labeled only in the inset. In addition, in one embodiment, a single border is placed around the insertion region on the main roadmap and the same unique border is placed around the corresponding image of the insert to help the browser correlate the inserts with the route map. main route. Also, the inset image is placed close to the main map feature it represents. In FIG. 30, the route shown on map 3004 is actually almost entirely North-South. However the scaling of the small roads at the end of the road has made the route appear to be almost circular. This is an example of severe distortion of the shape that is possible on such road maps after the individual roads on the route have been scaled. Using the 3002 insert, the small roads are kept in their original size

ES 2 373 095 T3 on the main map 3006, thus preserving a suitable global North-South orientation. Simultaneously, the small roads have been enlarged in insert 3002 to make them readable in insert. In FIG. 31, the scale of small highways such as US-6, W.36^to Ave, and Wilkes Ave so that they are legible has introduced a false intersection between Wilkes Ave and US-61 on the route map. Using insert 3102 the three roads can be enlarged to be large enough to be visible without introducing the dummy insert.

In one embodiment of the present invention, there are three steps to creating an insert. First, a determination is made on which roads to place in an inset, if any, secondly, the image size of the inserts is determined, and finally, enough space is identified to place the insert in the main map image nearby. of the insert characteristic. With this overview of the procedure in this embodiment, the three steps will now be described in more detail.

Selection of the roads of the insert. The procedure begins by trying to arrange all the roads in a single route map without inserts. After the initial layout a search is made for sets of roads that are very short (in pixel sizes) as well as narrow intersection loops. A check is made to determine if there is excessive shape distortion in the global shape of the route by checking how well the orientation vector is maintained between the start and end points of the global route. If not well maintained, a search is performed for adjacent sets of short roads, such as within a mile of the main route, that were over-increased and are in the direction of the distortion. Such sets of short roads are placed in an inset and the main route map is rescaled so that the oversized roads are reduced to a more precise scale. Finally, a search for false intersections is performed. All roads in the loop created by the false intersection are placed in the inset and the roads in the loop are rescaled on the main route maps to eliminate the false intersection.

Insert image size. The insert size is chosen first by estimating the aspect ratio for the set of roads that will appear in the insert using the same procedure as described for the choice of layout templates. This gives an aspect ratio for the inset image. A scale factor is then chosen for the inset image. The scale factor can be set a priori as a fixed number (that is, 100 pixels) or it can be dynamically calculated as a scale factor based on the number of roads that appear in the insert (that is, the scale factor equal to thirty times the number of roads in the insert). Then the pixel size of the inset image is simply the scale factor multiplied by the aspect ratio.

Placement of the insert on the scaled roadmap. It is desirable to place the insert in the main map image without overlapping any objects in the main image. Thus, the inset should be placed close to the main map feature it represents so that the browser understands the relationship between the inset and the main map. A search for empty spaces is performed in the main map image using the techniques described to find empty space. The search begins in the main image grid cell that contains the features displayed in the inset and spirals around the image starting from this cell until free space large enough to display the inset is found.

- Road shape

In another aspect of the present invention, new algorithms are used for simplifying the shape of a route. Most roads can be immediately simplified to straight lines and this is in fact perceptually preferable. However, some roads must maintain some curvature and the orientation and layout of the intersections between two roads must be kept in line with reality. In some embodiments of the present invention, simplification of the road shape is not implemented. Instead, each of the roads in the route (or path) is specified as a single line segment. In embodiments where road simplification is applied, the route map is processed by road simplification module 697 prior to execution of road layout module 686. Instead of treating each of the roads as a single linear segment, the road simplification module 697 considers each of the roads as a curve of linear pieces, that is, a set of shape points (lat, lon) connected by linear segments. The objective of the road simplification module 697, then, is to reduce the number of shape points on each of the roads thereby simplifying the roads.

There are two main reasons for simplifying each of the roads on a road map. The first and most important reason is that roads with simpler shapes are perceptually easier to interpret as separate entities, and the resulting roadmap has a neater, cleaner appearance. See FIG. 32 for a comparison of the same path without (FIG. 32A) and with the simplification of curves. Second, simpler roads that contain fewer segments require less memory and are faster to process by the road layout module in later layout stages. For example, to calculate the intersection of two roads, it is required to find an intersection between each of the pairs of segments on each of the roads. With fewer road segments this operation becomes much faster.

ES 2 373 095 T3

Elimination of false / missed intersections. In one embodiment, prior to road simplification, road simplification module 697 computes all intersection points between each of the road pairs. Let us consider the situation in which roads n and 12 intersect at points p-ι, p2 and p3 in FIG. 3. 4. Highway simplification module 697 inserts each of the intersection points into the set of shape points for both η and r2, and marks these intersection points as held, as shown in FIG. 34. More specifically, the original sequence of shape points for n is (s1, s2, se, s4, ss, and se). Three new intersection points are inserted into this sequence, one for each of the intersections, resulting in the sequence (s1, p1, s2, s3, p2, s4, s5, s6 and p3). Similarly, these intersection points are also inserted into the sequence for r2. Since these intersection points can no longer be removed, the simplification algorithm cannot cause the loss of intersections. In addition, the road simplification module 697 maintains a separate list of all the actual intersection points between roads. In later stages, the simplification algorithm module 697 only accepts the removal of one or more points from the shape if the removal does not create a new intersection point (that is, an intersection point that is not in the list of points of original intersection). Thus, module 697 ensures that the simplification does not generate any false intersections.

In some embodiments of the present invention, data cleansing is performed after the intersection points have been marked as held. Most of the roads represented on a roadmap intersect with at least two other roads: the previous road on the route at the start point of the road and the next road on the route at the end point of the road . These intersections are called turning points rather than intersections. At a turning point, the navigator switches from following one road to following a different road. The term intersection is used to refer to all other intersections between roads. At intersections, the road being followed does not change. It is extremely rare for two adjacent roads along the route to both join at a turning point as well as intersect each other at a separate location. If they did, the navigator would have turned onto the second road at the first intersection instead of the turning point (see FIG. 35). However, some motorway entrance and exit ramps are exceptions to this rule. Consider some highway A that connects to a ramp that then passes under highway A. From the two-dimensional aerial perspective of the road map, the ramp cuts to highway A and then continues to connect to the highway. Module 697 forces such ramps to be like the other roads by moving all points of the shape between the turning point and the intersection point on road A within the ramp. The road layout module 686 then assumes that adjacent roads never intersect each other and thus the costly calculation of intersection between these roads is eliminated. Also, when a circular ramp is scaled through the road layout module 686, the entire circle is scaled as a unit thereby avoiding concerns about the proper placement of the intersection between the ramp and the previous road.

Election Points for Elimination / Retention of non-ramps. For roads that are not ramps, a very aggressive protocol is used by road simplification module 697 to smooth out such roads. For a given road on the route, the module initially marks every point on the shape except the first, last, and any intersection points as deleted. A pointer is held to the second point of the shape and from the second to the last point of the shape. Next, a false intersection check is made. If a false intersection is found both the second and second to last point of the shape are marked as held. Also, the pointers move to the next points in the innermost way. If no false intersection is found, or the pointers cross over each other, the false intersection check ends.

After performing a false intersection check, a check is performed to identify inconsistent turn angles at the turning point between the previous road and the current road. Various embodiments of the road simplification module 697 use one of two alternative methods for detecting turning angles inconsistent with respect to the coordinate system oriented along the last segment of the previous road. The two procedures are shown in FIGS. 36A and 36B respectively.

In the first procedure (FIG. 36A), a vector is formed between a point of the current shape and the point of the previous shape. This vector is then compared to the vector between the point of the previous shape and the last point of the shape. If the vectors are not in the same half plane, or some other predetermined number of degrees such as a quadrant, with respect to the coordinate system defined by the last segment of the previous road, then the road simplification module 697 retains this point of the shape and continue checking at the next point in the shape.

In the second procedure (FIG. 36B), a vector is formed between the first shape point and the current shape point. This vector is compared to the vector between the point of the current shape and the last point of the shape. If the vectors are not in the same half plane, or some other predetermined number of degrees such as a quadrant, with respect to the coordinate system defined by the last segment of the previous road, then the point of the shape is retained at this point of the form and the procedure continues checking at the next point of the form.

Both procedures of FIG. 36A and 36B traverse the set of shape points from first to last and perform simple angle checks to determine whether or not the shape point should

ES 2 373 095 T3 withheld. The first procedure (FIG. 36A) tends to retain fewer shape points than the second (FIG. 36B). In some embodiments of the highway simplification module 697, the two procedures are combined by running the first and then the second and then holding all the points of the way until some average of the two results. A similar turn angle consistency check is performed by the road simplification module 697 in the turn between the current road and the next road.

Although detailed information is not required to follow most of the following roads, the highway entrance and exit ramps are an exception to this rule. Knowing if a ramp curves around itself to form a cloverleaf or if it slopes only slightly can make it much easier to decipher as a freeway entrance or exit. Therefore the simplification algorithm module 697 uses a different simplification criterion for motorway entrance ramps than for other roads on the route. For ramps, the road simplification module 697 performs a detailed analysis of the shape during the simplification. At each of the interior shape points, the lengths of the two adjacent segments, and the angle between them, are considered, as shown in FIG. 37. In FIG. 37, for a given shape point, the two adjacent segments for the shape point have lengths ¡1 and fe, α is the angle between these two segments and n and n2 are the number of unsimplified segments that are represented by each of the current segments. A measure of relevance to the point of the shape is calculated as:

relevance = (180-a)

AA - + ^M1 «2 .

The higher the relevance measure, the more important it is to retain the point. The road simplification module 697 defines a tolerance value; and if there is at least one point of the shape with relevance &lt;tolerance, the point of the shape with the lowest relevance is marked as removed. The relevance is then recalculated for all remaining points of the form; and if possible, another point is removed from the shape. This procedure is repeated until all points on the shape have a relevance greater than the tolerance or all remaining points on the shape are marked as held.

The relevance measure is based on two observations. First of all, sharper turn angles are more important than shallow turn angles. Since we measure the smallest angle, α between adjacent segments, we use 180 - α in the numerator of the relevance measure to give more relevance to roads with sharper angles. Second, for ramps, the turns between shorter segments tend to be more important than the turns between longer segments (see FIG. 38). Thus, the denominator is the sum of the two adjacent segments. However, it will be appreciated that removing a point from the shape causes a segment to become longer. Therefore if the algorithm were to simply divide by the sum of the adjacent segment lengths, as the procedure continued to simplify the ramp, the relevance measures of the remaining shape points would tend to decrease. In this way, the lengths of the adjacent segments are normalized by the number of unsimplified segments that the current segment replaces.

Elimination of Ramps. Entering or exiting most highways requires taking a short entrance or exit ramp. For long routes (ie 50 miles (80.47 km) or longer) that include many highways, showing all short ramps can clutter the map with unnecessary detail. However, some ramps, particularly near the beginning or end of the route, can be very important to understanding how to follow the route. Therefore, some embodiments of the highway simplification module 697 include a set of heuristics for evaluating the importance of a ramp. When a given ramp does not satisfy this set of heuristics, the ramp is removed. In one embodiment, this set of heuristics is as follows

1. Ramps between highways. The ramps between two highways are less important than those between small roads and highways.

2. First / Last ramp. Never eliminate the first and last ramps on the route as they are probably to go between local, smaller roads and the freeway.

3. Short routes. Keep all ramps for routes smaller than a predefined cut length (eg 50 miles (80.47 km)) or cut stages (ie 20 stages).

Four. Long ramps. Maintain the ramp if it is longer than a minimum ramp length specified in advance (that is, 0.1 miles (160.94 meters)).

5. Short road before / after the ramp. If the road immediately before or after the ramp is shorter than a length specified in advance (ie 0.5 miles (80.47 meters)) keep the ramp.

As in a highway simplification, the three main problems that the highway simplification module 697 seeks to eliminate when removing ramps are the introduction of false intersections, the loss of a true intersection, and the creation of inconsistent turns. To avoid false or missed intersections,

ES 2 373 095 T3 uses the same approach found in the road simplification procedure described above by the road simplification module 697. First, the set of intersection points between each of the pairs of roads. Before allowing the removal of a ramp, a check is made to determine if the removal will add a false intersection to the intersection list or cause an actual intersection to be lost; and if so, the ramp will not be removed.

Turning angle consistency assurance is slightly different when ramps are removed than with road shape simplification. When ramps are removed, the road simplification module 697 checks to make sure that the road continues to appear to be to the right of the ramp after removing the ramp. If this relationship is not maintained, the turn is inconsistent and the ramp cannot be eliminated as shown in FIG. 39. Note that the turn consistency check does not have to be performed on a cloverleaf ramp as they essentially form a circle, because they start and end at the same point, which is the same at the last point on the road before the ramp (n).

To check the consistency of turn, the road simplification module 697 first checks whether the ramp, which is approached as a single line segment between its start and end shape points, turns to the right or left of n. If the ramp turns to the right, then the ramp is removed if the direction of r2 is in the first, second, or fourth quadrant of the coordinate system oriented along η, Similarly if the ramp turns to the left of η , the ramp is removed if the direction of r2 is in the first, second, or third quadrant of the coordinate system oriented along η.

Similar optimization algorithms

Although the examples for tag optimization and path scale optimization include refinement of an objective function using simulated annealing, it will be appreciated that the objective functions of the present invention can be refined using any form of search based on the refinement algorithm. . The search-based representative algorithm includes, but is not limited to: Greedy algorithms, gradient decrease, simulated annealing, Tabu searches, A * as examined by Zbigniew and others in How to Solve It: Modern Heuristics, Springer-Verlag, Berlin, Germany, 2000, greedy A * / IDA * searches, simulated annealing and hill scaling (gradient descent) as reviewed by Russell et al in Artificial Intelligence: A Modern Approach, Prentice Hall, 1995, and genetic algorithms as examined by Golderg in Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

Observation conclusion

The efficient use of data structures and acceleration techniques is useful in implementing the procedures disclosed in the present invention. Typically, the search algorithms described herein require a significant number of iterations to converge, and scoring is done at each iteration. Scoring often involves determining whether various objects on the map intersect, and the costs of these intersection calculations should be minimized. One way to minimize the cost of such calculations is to use a two-dimensional partition grid to subdivide the screen and reduce the number of possible candidate objects for the calculation of any intersection.

It is also possible to significantly reduce the calculation control of the search algorithms by doing a simple analysis before starting a search. In many cases, the algorithm can determine the optimal length of a road or the optimal placement of a label so that it does not detrimentally affect the size or placement of other roads or labels on the map. Therefore, these attributes can be assigned a priori thereby reducing the size of the search space and reducing the running time of the algorithm.

Other realizations

The present invention may be implemented as a computer program product that includes a computer program mechanism embedded in a computer-readable storage medium. For example, the computer program product could contain the address analyzer 684, the road layout module 686, and the map display module 692 (FIG. 6). These program modules may be stored on a CD-ROM, magnetic disk storage product, or any other computer-readable data or program storage product. The software module in the computer program product can also be distributed electronically, via the Internet or otherwise, by transmitting a computer data signal (in which software modules are embedded) over a carrier wave.

It will be appreciated that, although reference has been made to road maps that include roads, the present invention encompasses road maps of any kind. Thus, the route maps of the present invention include, but are not limited to, hiking trails, campus addresses, and graphical representations of mass transit networks in addition to road maps. Furthermore, it will be appreciated that although reference is made in FIG. 6 To a system for generating a road map that has a client / server format, many embodiments of the present invention are implemented using a single computer that is not necessarily connected to the Internet. Furthermore, it will be appreciated that the layout of the software modules shown in FIG. 6

ES 2 373 095 T3 are merely exemplary. For example, embodiments in which the address analyzer 684, said road layout module including memory 686, label layout module 688, annotation module 690, map display module 692, database address data 694, and geographic landmark database 696 independently reside on client 622 and / or server 624 fall within the scope of the present invention as claimed.

The above descriptions of specific embodiments of the present invention are presented for purposes of illustration and description. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed, obviously many modifications and variations are possible in light of the above teachings. The embodiments were chosen and described for a better explanation of the principles of the invention and its practical applications, thus enabling other persons skilled in the art to better use the invention and various modifications as they suit the particular use contemplated. . The scope of the invention is intended to be defined by the following claims.