|
Article Excerpt
Introduction
Data structures supporting variable scale data sets are still very rare. There are a number of data structures available for multi-scale databases based on multiple representations, that is, the data are used for a fixed number of scale (or resolution) intervals. These multiple representation data structures attempt to explicitly relate objects at different scale levels, in order to offer consistency during the use of the data. The drawbacks of the multiple representations data structures are that they do store redundant data (same coordinates, originating from the same source) and that they support only a limited number of scale intervals. Most data structures are intended to be used during the pan and zoom (in and out) operations, and in that sense multi-scale data structures are already a serious improvement for interactive use as they do speed-up interaction and give reasonable representations for a given level of detail (scale).
Need for Progressive Data Transfer
Another drawback of multiple representation data structures is that they are not suitable for progressive data transfer, because each scale interval requires its own (independent) graphic representation be transferred. Good examples of progressive data transfer are raster images, which can be presented relatively quickly in a coarse manner and then refined as the user waits a little longer. These raster structures can be based on simple (raster data pyramid) (Samet 1984) or more advanced (wavelet compression) principles (Lazaridis and Mehrotra 2001; Hildebrandt et al. 2000; Rosenbaum and Schumann 2004). For example, JPEG2000 (wavelet based) allows both compression and progressive data transfer from the server to the end-user. Also, some of the proprietary formats such as ECW from ER Mapper and MrSID from LizardTech are very efficient raster compression formats based on wavelets and offering multi-resolution suitable for progressive data transfer. Similar effects are more difficult to obtain with vector data and require more advanced data structures, though, recently, a number of attempts have been made to develop such structures (Bertolotto and Egenhofer 2001; Buttenfield 2002; Jones et al. 2000; Zhou et al. 2004).
Multi-scale / Variable-scale Vector Data Structures
For single (line) objects, a number of multi-scale/variable-scale data structures have been proposed: Strip-tree (Ballard 1981), Multi-Scale Line tree (Jones and Abraham 1986), Arc-tree (Gunter 1988), and the Binary Line Generalization tree (BLG tree) (van Oosterom 1990). The Strip-tree and the Arc-tree are intended for arbitrary curves, not for simple polylines. The Multi-Scale Line tree is intended for polylines, but it introduces a discrete number of detail levels and it is a multi-way tree, meaning that a node in the tree can have an arbitrary number of children. The BLG tree is a binary tree for a variable scale representation of a polylines, based on the Douglas-Peucker (1973) line generalization algorithm. The BLG tree will be explained in more detail in a later section (see Figure 7). Note that these line data structures cannot be used for spatial organization (indexing, clustering) of multiple objects (as needed by variable scale or multi-scale map representations), so they only solve part of the generalization and storage problem.
[FIGURE 7 OMITTED]
One of the first multi-scale vector data structures designed to avoid redundancy was the reactive BSP-tree (van Oosterom 1989), which supports both spatial organization (indexing) and multiple level of details. Its main disadvantage, however, is that it is a static structure. The first dynamic vector data structure supporting spatial organization of all map objects, as well as multiple scales, was the Reactive tree (van Oosterom 1992; 1994). The Reactive tree is an R-tree (Guttman 1984) extension with importance levels for objects: more important objects are stored higher in the tree structure, which makes more important object more accessible. This is similar to the reactive BSP-tree, but the dynamic structure of the Reactive tree enables inserts and deletes, functions that the BSP-tree lacks. The BLG tree and the Reactive tree are eminently capable of supporting variable-scale/multi-scale maps composed of individual polyline or polygon objects.
Generalized Area Partitioning
The BLG-tree and Reactive-tree structures are not well suited for an area partitioning, since removal of a polygon results in a gap in the map and independent generalization of the boundaries of two neighbor areas results in small slivers (overlaps or gaps). Overcoming this deficiency was the motivation behind the development of the GAP tree (van Oosterom 1993). The BLG-tree, Reactive-tree, and GAP-tree data structures can be used together, while each supports different aspects of the related generalization process, such as selection and simplification, for an area partitioning (van Oosterom and Schenkelaars 1995).
Following the conceptualization of the GAP tree, several improvements were published to resolve limitations of the original data structures (van Putten and van Oosterom 1998; Ai and van Oosterom 2002; Vermeij et al. 2003). This paper introduces the new topological GAP tree, which combines the use of the BLG tree and the Reactive tree and avoids the problems of the original GAP tree--redundant storage and slivers near the boundary of two neighbor areas. Then the implementation of the structure is discussed, followed by an explanation of how to use it for progressive data transfer. Finally, a summary of the most important results is provided, together with suggestions for further research.
GAP Tree Background
The first tree data structure for generalized area partitioning (GAP tree) was proposed by van Oosterom (1993). The idea was based on first drawing the larger and more important polygons (area objects), so as to create a generalized representation. However, one can continue by refining the scene through the additional drawing of the smaller and less important polygons on top of the existing polygons (based on the Painters algorithm; see Figure 1). This principle has been applied to the Digital Land Mass System--Digital Feature Analysis Data (DLMS-DFAD) data strurcture (DMA 1986), because it already had this type of polygons organization. When tested with the Reactive tree and the BLG tree, it was possible to zoom in (zoom out) and obtain map representations with more (less) detail of a smaller (larger) region in constant time (see Figure 2, left).
[FIGURES 1-2 OMITTED]
Computing the GAP Tree
If one has a normal area partition (and not DLMS DFAD data) one first has to compute the proper structure. This is driven by two functions. First, the importance function (for example: Importance(a) = Area(a) * WeightClass (a)) is used to find the least important feature a based on its size and the relative importance of the class it belongs to. Then the neighbor b is selected based on the highest value of Collapse(a,b) = Length(a,b) * CompatibleClass(a,b), with Length(a,b) being the length of the common boundary. Feature a is removed and feature b takes its space on the map. In the GAP tree this is represented by linking feature a as the child of parent b (and enlarging the original feature b). This process is repeated until only one feature is left covering the whole domain, forming the root of the GAP tree. Figure 1 gives a schematic representation of such a GAP tree.
Work by van Smaalen (1996; 2003) focuses on finding neighbor patterns, which might in turn be used for setting up an initial compatibility matrix. Bregt and Bulens (1996) give area generalization examples in the domain of soil maps, based on the same principles. Both van Smaalen and Bregt and Bulens use an adapted classification for the higher (merged) level of objects, instead of keeping the original classification at all levels of detail; e.g., deciduous forest and coniferous forest objects are aggregated into a new object classified as "forest" or "garden," while house and parking place objects form...
|
