COPERNICUS: Context-Preserving Engine for Route Navigation with Interactive User-modifiable Scaling

Hartmut Ziegler, Daniel A. KeimComputer Graphics Forum 2008 · DOI · OpenReview

TL;DR

This paper introduces COPERNICUS, a system that generates context-rich route maps by transforming traditional road networks into a network graph metaphor. It addresses the limitations of existing route planners by intelligently extracting and displaying relevant contextual information, allowing for interactive, user-modifiable scaling to present all necessary details on a single page.

What Problem Does This Paper Address?

Current web-based route mapping systems, despite their popularity, often suffer from a lack of visualization innovation. They typically present a static map with a highlighted route, leading to two major issues: 1) crucial details near the origin and destination can be obscured due to fixed scaling, requiring multiple zoom levels and printouts, and 2) they fail to effectively distinguish between relevant and extraneous information, cluttering the map with details far from the intended path. This makes navigation less intuitive and potentially error-prone, especially when relying on traffic signs for orientation. The paper aims to create a more user-friendly and informative route visualization that consolidates all necessary information onto a single, interactive page.

Methods

COPERNICUS employs a multi-stage approach:

  • Context Engine: This core component identifies and extracts relevant contextual information from a geographic database. Key sub-modules include:
  • Determination of Nodes and Edges: Towns are treated as nodes and streets as edges, forming a network graph metaphor.
  • Identification of Highway Network Nodes: Crucial decision points on highways (e.g., ramps) are identified and visualized with directional cues.
  • Concatenated Streets: Identifies and merges consecutive street segments with the same name or number.
  • Cross Street Detection: Uses a matrix to determine the importance of cross streets based on the type of the main street.
  • Town Boundaries: Towns are represented by convex hulls for clarity.
  • Locating Major Cities: Identifies and displays major cities along the route to aid orientation.
  • Landmark Determination: Rules are used to identify and display relevant landmarks (initially gasoline stations).
  • Importance Rating: Heuristics are applied to rank the importance of extracted nodes and edges, optimizing the network graph structure and reducing clutter.
  • Determination of Streets for Rendering: Selects which street segments to display based on their importance, length, and type, aiming for a minimal representation.
  • Interactive Scaling Engine: This novel engine allows for seamless transitions between an undistorted map and the context-rich, distorted map. It uses linear scaling in both horizontal and vertical directions to fit all relevant information onto a single page, while attempting to preserve the general geographic direction of streets. It also incorporates consistency constraints to avoid visual artifacts.
  • Rendering Engine: Draws the final map, including towns, streets, labels, distances, landmarks, and orientation cues, prioritizing context information based on available display space.

Datasets

The paper utilizes geographic data from NAVTEQ for the German street network. This data is stored in an Oracle 10g database with GIS extensions, forming a network graph with millions of nodes and edges, each with numerous attributes.

Key Insights and Ideas

  • Network Graph Metaphor for Routes: Shifting from a simple highlighted path to a network graph where towns are nodes and streets are edges fundamentally changes how routes are visualized, enabling navigation from "node to node" using town names and road signs.
  • Context is King: The system's success hinges on intelligently identifying and prioritizing relevant context (town names, major cities, highway exits, landmarks) over simply displaying all available data.
  • Interactive, User-Modifiable Scaling: The ability to seamlessly scale and distort the map, allowing users to adjust the level of detail and focus, is crucial for presenting complex information on a single page without overwhelming the user.
  • Preserving Geographic Direction: While distortion is used, the scaling engine is designed to maintain the general direction of streets, preventing drastic and confusing visual changes.

Key Results

The paper presents a functional prototype of the COPERNICUS system. While specific quantitative results like accuracy metrics or speedup percentages are not detailed, the qualitative results are significant:

  • Single-Page Visualization: The system successfully generates route maps where all relevant information is clearly visible on a single page, eliminating the need for multiple printouts or zoom levels.
  • Improved Orientation and Navigation: The context-rich display, including town names and major cities along the route, provides better orientation and makes it easier to verify one's position using traffic signs.
  • Seamless Interactive Scaling: The interactive scaling engine allows users to fluidly transition between a standard map view and the context-enhanced view, offering a dynamic and user-friendly experience.
  • Reduced Clutter: The importance rating and space optimization techniques effectively reduce extraneous information, focusing on what is essential for navigation.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that finding an "optimal" layout that satisfies all design principles is an optimization problem, and the system aims for an approximation.
  • While the system aims to preserve geographic direction, some deviation (usually less than 25 degrees) is inherent in the linear scaling.
  • The initial implementation of landmarks was limited to gasoline stations.
  • Future Work:
    • Developing a more aesthetically pleasing map design.
  • Conducting usability tests to gather user feedback.
  • Integrating more types of landmarks and linking them to corresponding web pages.
  • Optimizing the routing engine for simpler, more navigable paths.

Summary updated

BibTeX
@article{ziegler2008copernicus,
  author = {Hartmut Ziegler and Daniel A. Keim},
  title = {{COPERNICUS: Context-Preserving Engine for Route Navigation with Interactive User-modifiable Scaling}},
  journal = {Computer Graphics Forum},
  year = {2008},
  doi = {10.1111/j.1467-8659.2008.01226.x},
}
Figure