stanbul 2004
out in stages,
S:
ree possible
iare a vertex
two objects
two) objects
n one object
:
igure the
type. The
different
able vertices
ined — those
vhich can be
c which are
onsidered as
the vertex F;
the operation
ar, and a new
not intersect
can be
(1)
ygonid is the
ine entities 18
tion of
AT
+ from a
epresented as
(2)
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
where posid is the order in the vertices set, and Lineid is the ID
of the line spatial object.
Complex vertex removal
If simple vertex removal is used on a polygon vertex of
category (b) then there is uncertainty as to how to rebuild the
closed chains making up the polygon, and a hole may result
(Figure 3). Therefore, a two step operation, first removing the
vertex and then ensuring that topological consistency is
maintained is carried out.
Figure 3 Invalid topology in complex vertex removal
Suppose vertex V; selected for removal is a common vertex of n
polygons (FH, P,,..., P,] - therefore n vertices {V,V,,....V,}
are associated with vertex (V;). Each pair consists of one chain.
Thus, to avoid gap generation, the vertex remove operation is
defined as follows:
For a set of polygons (A, P,,..., P,] , the operation of common
vertex (V;) remove is defined as
n-l
F = Pi eu... P € V,, P, =P, js Ur. DV; (3)
m=2
On polygons {AR, B,...,P,
7-1} the operation carried out is
identical to simple vertex removal. However, for polygon P, the
following operation, illustrated in Figure 4 is applied:
n—1
P, 2 P.- Uv, er,
m=2
Figure 4 Sealing a hole generated by complex vertex removal
Ranking of vertices for removal
The operations described above provide a means to identify
immovable vertices, and operations to remove vertices of
different classes. Further criteria are required to rank vertices
for removal and to prevent invalid topologies from being
generated through self intersection. We adapt the line
simplification algorithm of Visvalingam and Whyatt (1993) to
carry out this task. This algorithm is based on the principle of
simplifying lines by removing the vertices which form the
minimum area triangles within the line. By minimising the area
removed from polygons or lines the likelihood of maintaining
shape fidelity with the original object is increased (Visvalingam
and Herbert, 1999). The triangles generated for this operation
are also used for a simple topology check — a vertex can only be
removed of the triangle formed by it and its neighbouring
vertices do not contain any other vertices.
Thus for a polygon with r vertices, n-1 triangles will be
generated, and for a line with n vertices, z-2 triangles will be
generated. Moreover, the start and end vertex of the linc are
defined as immovable vertices. After identification of
immovable vertices, vertices are ranked by triangle area size
order for possible removal if, and only if, the triangle formed
does not contain any further vertices. The vertex with the
minimum triangle area will be removed first. Finally, according
to the vertex type a simple or complex vertex removal operation
is carried out.
4. CLIENT-SERVER ARCHITECTURE
PROGRESSIVE TRANSMISSION VECTOR
DATA
FOR
MAP
In order to implement web-based progressive transmission
client and server side components are required. On the server
side the reduced vertex entities must be generated and
transmitted, whilst on the client side these data must be
appropriately displayed and reconstructed as more vertices are
delivered.
Figure 5 illustrates the prototype architecture for progressive
transmission of vector map data. The whole architecture
encompasses three interrelated components: a client side
component, an application server component, and a data
simplification component. The data simplification component is
responsible for extracting coarser data from a database or files
in real time and for representing the data in the appropriate data
model before the data is sent to the application server
component. The server side of the component was integrated
into the OpenSource Web Feature Server (WFS) provided by
Deegree (Deegree, 2003), allowing the generation of vector
maps in response to a standard OpenGIS WFS call (OpenGIS,
2002). The data simplification in the prototype architecture is
processed in real time in response to queries from the client,
alleviating the need to store a variety of intermediate products
and allowing all maps to be generated from a single source data
set as required.
Application server
Query control
Data distribute
Client side
i
1
1
1 e
1 1 Query
= 1
i
!
i
etworl
nr A.
|
rf
| Spatial entities
| reconstruction |
e -
LJ — Á—— M Bam
D in : | Spatial entities | |
Simplifig jtion | simnlificati | ME m
(, simpli fication | Visualization
eden 1T
27
Figure 5 Prototype system architecture
The client side component deals with visualizing the query
result, allowing querying of the data and reconstructing the
source vector map data.
r
1
1
1
|
I
I
1
1
I
|
!
i
I
I
+
