Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2000-03-17
2002-07-23
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C701S201000, C701S212000, C707S793000
Reexamination Certificate
active
06424933
ABSTRACT:
The present invention relates generally to a system and method for generating a route map. More particularly, this invention relates to a system and method for applying a unique scale factor to each road in a route map and for optimizing the positions of labels in the route map. Further, a method for rendering the appearance of roads in the route map is disclosed.
BACKGROUND
Route maps, when well designed, are an effective device for visualizing 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 widespread use of computer-generated route maps. Online mapping services typically provide directions as a set of maps complemented with text descriptions. Such on-line computer-generated maps are unsatisfactory, however, because the algorithms used to generate the maps disregard many of the techniques and principles used by human map-makers.
Effective use of a route map generally requires two distinct activities: (i) following a path until reaching a critical point and (ii) changing orientation to follow another path. Thus, one of the most important types of information route maps can communicate are points of reorientation. That is, where someone must consciously turn from one path to another. However, existing computer-generated route maps fail to effectively communicate points of reorientation because they typically uniformly scale all the roads in the map by a constant scale factor. As an example, for routes of any reasonable length, uniform scaling requires some roads to be very short so that the map will fit in a particular viewport. But it is precisely these very short roads that connect critical turning points. Thus, uniform scaling results in a loss of some of the most critical information found in a route map.
Another shortcoming in prior art computer-generated route maps is that they needlessly depict accurate length, angle, and curvature of each road in the route. Such accurate depictions are made at the expense of map readability. Psychological research indicates that most people distort distances, angles, and curvature when drawing route maps. See e.g., Tversky and Lee, “How space structures language,” Spatial Cognition: An interdisciplinary approach to representation and processing of spatial knowledge, (eds.) Freska, Habel, and Wender, 1998, 157-175; Tversky and Lee, “Pictorial and Verbal Tools for Conveying Routes,” COSIT 99, Conference Proceedings, Stade Germany, 1999, 51-64. Other psychological studies indicate that people maintain such distortions in their own mental representations of a route. See e.g., Tversky, “Distortions in Cognitive Maps,” Geoforum 23, 1992, 131-138. Thus, adherence to accurate lengths and angles in prior art computer-generated maps runs counter to how humans conceptualize routes.
Computer-generated route maps can be classified into four major mapping styles: route highlight maps, TripTiks, overview/detail maps, and two dimensional nonlinear distortion maps. Route highlight 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 display extraneous detail throughout the map. The constant scaling, as exhibited 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 the detail, but the map is very large. Since general road maps are not optimized to show any particular route, a route highlight map will often suffer from both a large scale factor and an inconvenient size. The clarity of the route in a route highlight map depends on the style of the highlighting since that is the only property differentiating the route from other roads. Usually the route is distinctively colored, but because general road maps provide context information over the entire map, the map is cluttered with extraneous information that makes it difficult to perceive the route and the individual reorientation points.
TripTiks are similar to route highlight maps, but they are specifically designed for communicating a particular route. As shown in
FIG. 2
, a TripTik map usually stretches over multiple rectangular pages, and each page is oriented so that the route runs roughly down the center of the page. Each TripTik page employs constant scaling, but the scale factor differs across pages. Changing the scale factor from page to page allows the TripTik to show more detailed turn information where needed. However, because the map stretches over many pages and the orientation and scale factor varies from page to page, forming a general understanding of the overall route is difficult.
Overview/detail maps combine multiple maps rendered at different scales to present a single route, as shown in FIG.
3
. One of the maps (e.g.,
FIG. 3
a
) is scaled by a large factor so that it provides an overview of the entire route. Since the large scale factor of this map reduces the readability of local turn details, maps showing turn-by-turn information are provided (e.g.,
FIG. 3
b
). A constant scale factor is used for each map, but the scale factor differs across the maps. While an overview/detail map may seem like an effective combination, such maps are unsatisfactory in practice. The overview map rarely presents more than the overall direction of the route. Although turn-by-turn maps provide detailed information for every turn, the use of distinct maps for each turn, often with different orientation and scale, makes it difficult to understand how the maps correspond to one another. Therefore, the navigator has difficulty forming a cognitive model of the route.
To ensure clear communication of all of the reorientation points, some parts of a route's depiction 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 focus-plus-context viewing. (See. e.g., Carpendale et al., “Three-Dimensional Pliable Surfaces: For the Effective Presentation of Visual Information,” Proceedings of the ACM Symposium on User Interface Software and Technology, UIST 95, 1995, 217-226; Keahey, “The Generalized Detail-In-Context Problem,” Proceedings of the IEEE Symposium on Information Visualization, IEEE Visualization 1998). These techniques allow users to choose regions of the map they want to focus on and then apply a nonlinear magnification, such as a spherical distortion, to enlarge these focus regions. Such two dimensional distortion allows detailed information to be displayed only where relevant and often produces general area maps that can be conveniently displayed on a single page. However, a major problem with nonlinear two-dimensional distortion is that the regions at the edges between the magnified and non-magnified portions of the map undergo 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 readily apparent even at a quick glance. The map contains only as much information as is necessary and is easy to carry and manipulate. To further such design goals, map content, precision, and rendering style must be carefully optimized. Map content includes important parameters such as a route start and end, as well as points of reorientation. Reorientation points are points along the route at which the navigator must change orientation and switch to a different road. Another important map design goal is the proper use of context information. The amount of context information included in the map greatly affects the utility of the map. Useful context information includes labels or names for a path on the route as well as landmarks along the route such as buildings, stop lights, or stop signs. When drawing a route
Agrawala Maneesh
Stolte Chris
Broda Samuel
Pennie & Edmonds LLP
Teska Kevin J.
Vicinity Corporation
LandOfFree
System and method for non-uniform scaled mapping does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for non-uniform scaled mapping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for non-uniform scaled mapping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2888513