International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
chains of vertices respectively". Thus progressive transmission
of vector data in this work is based on the principle of reducing
the number of vertices resulting in either a removal of points or
simplification of lines or polygons. Simplified spatial entities
are therefore transmitted first to the client, and progressively
more vertices are gradually delivered from the server to the
client until either the user interrupts the process or the entire
dataset has been delivered. Figure 1 illustrates the basic concept
of progressive vector transmission for a single polygon.
a te fr
re n FY wry e RR up
+ * + & a x * ^g n *
* + Y » 2g
» / ru ^ E
vy e* 2t
= »- *
= wa
F Tw ==
€ > a — I
1 s à s. a
" * & za E "at
= by " = ee
T En 5 A
* = = " "x
à a =
Y x Asi
Figure 1 The concept of progressive transmission
The challenge in progressive vector transmission is to reduce
the amount of data sent to a client initially, but still allow the
user to perform useful tasks. Furthermore, the algorithms used
must be sufficiently efficient that they can be used in real-time
and therefore not simply move the overhead in delivery of
vector data from transmission to calculation of reduced vertex
sets. [n this paper, we adopt a set of generalization methods
which select suitable vertices for removal (Weibel and Dutton,
1999) without any displacement. A dataset can therefore be
represented as a full set of vertices and their associated chains
and progressively coarser sets of vertices which still maintain
key characteristics of the data.
In the next section of the paper a data structure that facilitates
vertex removal for progressive vector transmission and a set of
rules for carrying it out, whilst maintaining important properties
of the data is introduced.
3. HIERARCHY DATA MODEL FOR VECTOR MAP
DATA
When displaying a map with a user-selected set of layers, it is
impossible to know for what purpose layers have been selected.
Therefore, a simple and logical assumption is to consider all
layers as having equal weight, and to attempt to preserve
topological relationships between and within all layers. To this
end we adopt a simple ‘spaghetti’ data model, where points,
lines and polygons are represented by vertices and open and
closed chains of vertices respectively. Thus a ‘full resolution”
map can be represented as:
"m
Map' iol ton = 24] point, "IU line , & U polygon ,
iz j=0 k=0
In order to produce a reduced vertex version of the map for use
in progressive transmission we must identify a set of rules
which allow us to remove vertices whilst:
a) maintaining the shape of objects; and
b) preventing topological inconsistencies with respect to
the source data.
* In this paper we do not use the terminology of vertices and
nodes (c.f. Burrough and McDonnell, 1998)
26
To meet these constraints vertex removal is carried out in stages,
and requires consideration of the following elements:
e identification of vertex type;
e operations for vertex removal; and
e ranking of vertices for removal.
Identification of vertex type
Vertices in a map can be considered to have three possible
types according to the number of objects which share a vertex
and the number of source layers for that vertex:
a) A vertex which belongs only to one or two objects
from a single layer.
b) A vertex shared by multiple (more than two) objects
from the same layer.
c) A vertex which is shared by more than one object
from multiple layers.
These vertex types are illustrated in Figure 2.
—————
AS d A3
"y A Poly os
|
i
(a) (b) (c)
Figure 2 Vertices of types (a), (b) and (c). In each figure the
open vertex represents the vertex of the appropriate type. The
dashed and solid lines are line and polygon data, of different
layers, respectively.
Ch,
eed
Vertices of type (c) are defined as being immovable vertices
and cannot be removed from a map.
Operations for vertex removal
Two classes of vertex removal operation are defined — those
which can be applied to vertices of type (a) — which can be
considered as simple vertex removal, and those which are
applied to objects of type (b), which can be considered as
complex vertex removal.
Simple vertex removal
Taking polygon entities as an example, supposing the vertex F;
will be removed from the vertex set of a polygon, the Oneration
will cause one vertex and two segments to disappear, and a new
segment to be generated. If the new segment does not intersect
with other spatial entities, the operation is safe.
Thus, this operator will extract a simplified polygon
7 7
Por} fn ius ;
(VV, V
RR NO as
P - P. OV,V, - (x, y, posid, Polygonid) (1)
where M is the order in the vertices set, and Polygonid is the
ID of the polygon spatial object.
V,V,) from the full polygon
T E. V, A a ,.., V, V1 . and the operation can be
tarot
The procedure of the simple vertex removal from line entities is
similar to that from the polygon o objects. Th The operation of
extracting a simplified line Su m VE V e V au from a
full line (VV, weasel epy sen kn, A } can be represented as
QC, DF, V, e (x, v, posid, Lineid) (2)
Intern
where
of the
Comp
If sim
categc
closed
(Figur
vertex
maint:
Suppo
polygc
are ass
Thus, 1
define:
Foras
vertex
Ae
On pol
identic
follow:
Figure
Rankir
The op
immov;
differer
for ren
generat
simplifi
carry oi
simplify
minimu
remove
shape fi
