Academic journal article Cartography and Geographic Information Science

"Time Travel" Visualization in a Dynamic Voronoi Data Structure

Academic journal article Cartography and Geographic Information Science

"Time Travel" Visualization in a Dynamic Voronoi Data Structure

Article excerpt


The snapshot approach of current geographic information systems, where independent coverages are generated for each time step, cannot easily maintain the incremental changes of cartographic data evolving in space and time. The limitations of this approach include high data redundancy, due to the inability of conventional GIS models to support incremental changes, causing difficulties in the maintenance of long series of cartographic snapshots (Kraak and MacEachren 1994). Map snapshots tend to be created independently at specific intervals, rather than incrementally, and thus there is no preservation of topological relationships between map elements in different snapshots, and no way of determining the continuity of existence of map elements and their neighbors between snapshots.

Recent research efforts on Geographic Visualization (MacEachren 1998) focus on the use of dynamic maps to change fundamentally the way scientists and others conceptualize and explore geo-referenced data. This approach will allow to the users to shift from inflexible static maps towards highly manipulable dynamic maps. Dynamic maps (MacEachren 1998) are maps that change in response to user action or to changes in data to which they are linked.

In this paper, we present a new approach for dynamic visualization and exploration of spatial data based on Voronoi diagrams, and the reversibility of their operations (Gold et al. 1995; Anton 1996). Visualization can be done dynamically and incrementally, and we will see that this is fully supported by the dynamic spatio-temporal Voronoi data structure. The Voronoi diagram is used because any tessellation of the plane implies topological connectedness, and the Voronoi diagram gives a one-for-one correspondence between map objects and tiles. Moreover, the operations on the Voronoi data structure have a local scope: only the neighbors of the objects involved in an operation might be modified.

Within such a dynamic Voronoi spatio-temporal data structure, as developed by Gold (1992), the map objects (points and/or line segments) are stored as nodes of the dual spatial adjacency (topology) graph: the Delaunay triangulation. Maps are composed of points, curves and surfaces. The ordinary point Voronoi diagram does not allow us accurately to model linear or areal objects (curves and surfaces). Therefore, in order to represent the different kinds of cartographic objects, we need to use the line Voronoi diagram instead of just simply the ordinary point Voronoi diagram. The algorithm used to construct the Voronoi vertices has been described in (Anton and Gold 1997). The changes in this data structure are therefore the changes in the spatial adjacency relationships, that is to say the changes in the Delaunay triangulation (Okabe et al. 1992). This spatial data structure has a dynamic, incremental, and explicit topology (Gold 1992). Within this data structure, the user's commands are changing the map incrementally and locally, and the map objects and their spatial adjacency relationships are visualized all at any point in time (Anton 1995). Furthermore, this approach allows real-time dynamic maintenance of the spatial data structure, as well as dynamic sequential processing of events (Gold 1996). In such a spatio-temporal model based on interactive and local updates, the user is able to visualize map events evolving in space and time.

In order to visualize the evolution of a map, we use the term "time travel" (Atwood et al. 1996). The idea of time travel comes from the scientific visualization community, which describes it as the ability to receive a continuous visualization of spatial data as the map commands execute, coupled with the ability of the user to modify the map interactively at any time (Gold 1994), and immediately see the effects of these changes (Atwood et al. 1996). In visualization, "time travel" results in the ability to display me changes in a map in both directions in time. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed


An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.