Istanbul 2004 
IMPLEMENTATION OF PROGRESSIVE TRANSMISSION ALGORITHMS FOR 
VECTOR MAP DATA IN WEB-BASED VISUALIZATION 
B.S. Yang , R. S. Purves and R. Weibel 
GIS Division, Department of Geography, University of Zurich, Winterthurerstr. 190, CH-8057, Zurich, Switzerland 
* bisheng@geo.unizh.ch 
Commission IV, WG IV/1 
KEY WORDS: algorithms, visualization, hierarchy, web based, reconstruction 
ABSTRACT: 
This paper investigates the benefits of progressive transmission of vector data, through designing and developing a hierarchical data 
model to compress vector data for progressive transmission over the internet. The aim of the hierarchical data model is to extract a 
coarse vector data set using vertex removal operations. Furthermore, a set of rules are proposed to control the validity of topology for 
the ‘coarse’ vector data version, and a recovery algorithm is developed to reconstruct the ‘finer’ vector data on the client side. The 
proposed method reconstructs the original data. The overall procedure is to (a) extract coarser data version on the server side on-line; 
(b) transmit coarser data version to the client; and (c) progressively recover more detailed data on the client side. An experimental 
prototype system has been dcveloped to test the performance of the proposed method and illustrate its strengths and weaknesses. The 
experimental results show that the method can efficiently simplify spatial data, can maintain the shapes characteristics of objects 
during transmission, and improves transmission time over internet greatly. 
I. INTRODUCTION 
Initial developments in the delivery of spatial data over the 
internet focused on raster data, for example through the use of 
Web Map Servers (OpenGIS, 2002). Raster data volumes could 
be reduced through the use of progressive transmission (e.g., 
Rauschenbach and Schumann, 1999) and data compression 
techniques (e.g., Kern and Carswell, 1994). However, the desire 
to have access to more functionality, specifically the direct 
querying of objects, together with the development of SVG 
(Scalable Vector Graphics; SVG, 2002) as a successful means 
of viewing and exploring vector representations have refocused 
attention on the delivery of vector data over the internet. Other 
than the delivery of TINs (De Floriani and Puppo 1995; Park ef 
al 2001), much less work has addressed the issues of the 
delivery of vector-based data over the internet. 
In progressive transmission of raster data, detail in an image is 
gradually filled in enabling the user to get a ‘first look’ before 
all of the data have arrived. In the case of vector data, users 
may also wish to carry out operations on the data — for instance 
calculating the approximate area of a polygon - and are 
prevented from doing this until the full data volume has been 
delivered. Progressive vector transmission attempts to not only 
give the user a ‘first look’ at a data set, but to deliver data of 
sufficient fidelity that manipulation of some coarser version of 
the data will produce results consistent with the actual data. 
Cecconi and Weibel (2000) drew attention to the need for 
development of techniques for progressive transmission of 
vector data, and in particular methods for generalising such data 
at different levels of detail. Buttenfield (2000). Bertolotto and 
Egenhofer (1999; 2001) and Han er al (2003) all proposed 
frameworks for progressive vector transmission and discussed 
concepts, challenges, and implementation issues in developing 
viable solutions from the perspective of cartographic 
generalization. 
Le) 
Un 
The key challenges in progressive vector data transmission 
were summarized as (Bertolotto and Egenhofer, 2001): 
* preservation of topological consistency; 
e the complexity of real time generalization; and 
*  rcal time compression and encoding of spatial data. 
Implementations of techniques for progressive vector 
transmission include work by Han and Bertolotto (2003) who 
developed a prototype system using Oracle Spatial™ based on a 
set of cartographic generalization principles. Buttenfield (2002) 
investigated single spatial entity progressive transmission over 
the internet. 
In this paper a methodology for delivering large volumes of 
vector data through progressive transmission is described and 
implemented. A data model has been developed from which, 
through the use of a set of simple rules, an initial vector data 
representation can be transmitted to a client. The coarse 
representation is generated through vertex removal, which is 
optimised to minimise conflicts in topology, together with 
changes in shape. Finer data is reconstructed on the client side 
through the progressive transmission of the missing vertices. A 
client-server architecture to perform these operations is 
described, before a set of experiments using a variety of spatial 
data are performed and evaluated. These experiments are used 
to evaluate the potential of the model and discuss potential 
problems and solutions. 
2. CONCEPT OF PROGRESSIVE 
VECTOR MAP DATA 
TRANSMISSION 
Vector data consists of points, lines and polygons which can be 
considered to be vertices, open chains of vertices and closed