ave
ype
p of
cts.
rent
] on
ions
d in
ous
on of
ever,
| the
lated
3 ofn
s, and
iginal
s still
e ofa
lygon
using
finally
ps are
lygon
1bered
'alized
sos P?
ration.
e ofa
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
control parameter £,, which relates to the display scale and can
be — as discussed later — for example the length of the shortest
edge in the polygon. Thus, we can think of £, as the length of
the edge which was eliminated during generalization step g, or
alternatively as the length of the shortest edge in polygon P",
Since generalization proceeds using increasing edge lengths, the
sequence of ¢, is monotonically increasing. As a first
consequence of this, one can pre-compute and record all
operations g,, in order to derive quickly any desired
generalization level & by the execution of all generalization
36.
operations e, ..., 2 where Covent SE ud €
However, it is obvious that for most applications, the inverse
operations g^ are more interesting, producing a more detailed
polygon from a generalized one. Thus, we have the sequence
P" ph P Ph up
8
k-1l 8&2 S0
where again one can decide up to which point the polygon
modification should be carried out, characterized by the
corresponding parameier €. This way, the inverse
generalization chain can be used for progressively transmitting
information over a limited bandwidth channel by transmitting
the minimal representation P" followed by a sufficient number
of inverse generalization operations.
4.2 Encoding Elementary Generalization Operations
We call the generalization operations we introduced above
elementary generalization operations (EGO's), because every
generalization chain will be made up of a combination of
EGO's. Each EGO in turn consists of one or more simple
operations (SO's) modifying the polygon. It is obvious that
there are operations which modify the topology of a polygon,
namely the insertion and removal of vertices, and operations
which affect the geometry only. Table 1 shows a list of simple
operations. This list is not minimal, since e.g. a "DV i"
operation is equivalent to “IV i,0”. However, for
convenience and for achieving a most compact encoding, the
operations might be defined redundantly. Knowing the
parameters of a simple operation allows to immediately give the
inverse operation except for the “remove vertex” operation for
which the inverse would require an additional parameter to
specify the location of the vertex to be inserted.
Opcode | Description Parameters Inverse
Operation
IV Insert Vertex | IV «edge id>|RV <edge id +
«rel. position» 1>
DV Duplicate DV <vertex id> RV <vertex id +
Vertex 1>
MV Move Vertex |MV «vertex id>|MV <vertex id>
<dx> <dy> <-dx= <-dy>
RV Remove RV <vertex id> —
Vertex
Table 1: Simple operations used to define more complex
EGO's.
Figure 1 shows how SO's combine to an inverse EGO, which
realizes the creation of an extrusion of a building annex.
Starting from the top left polygon consisting of a simple
rectangle, a number of SO's is applied in order to obtain the
more complex L-shaped polygon to the lower right. It can be
observed that the numbering of the nodes and lines is
continuously adjusted in order to preserve the correct sequence.
Note that infinitely many combinations of SO's can be used to
obtain the same EGO. As long as a sequence does not contain
remove vertex operations, it can be immediately reversed from
a stored history of operations.
v, 2 v; v = Vv
€;
v,
e; e, e; :
e,
V. , V, y
0 e; Y; 0 €, 1
Initial polygon after
IV 1, 60%
€;
Vs Vv,
e;
Ya, V3
es x A
€;
V, A
0 e Vy
after after Mv 3, 2, 0
DV 2
and MV 4, 2, 0
Figure 1: Example for an inverse EGO, forming an L-shaped
building from a rectangular building. The EGO is
decomposed into four SO's.
5. REALIZATION AND EXAMPLES
In the following, we will demonstrate how several
generalization operations can be adapted to generate a sequence
of simple operations described above in order to generate a
generalization chain that can incrementally be sent to a client.
5.1 Line simplification / Point reduction
Simplifying lines or polygon outlines can be accomplished
using filtering techniques or point reduction methods. For point
reduction, different algorithms have been developed that either
locally, regionally or globally investigate a line and decide
upon which point can be omitted. The most popular algorithm is
the globally acting Douglas-Peuker algorithm. In order
decompose the point reduction process into a sequence of
reversible elementary generalization operations, the following
considerations can be made. Similar to generating a BLG tree, a
scale dependent decomposition of a line, is generated by
recursively extending the levels of detail in a tree structure. At
the root of the tree is the most coarse line consisting of start and
endpoint (see Figure 2). The inner nodes represent intermediate
generalization levels specifying line sectors with an associated
generalization level, and the leaves, finally, contain the original
line elements (here, the associated generalization level is
obviously 0). The generalization level or scale in this case is
directly related to the distance of that point from the
corresponding base line. For example in sector AF, at scale
level c a split of the line into the two sectors AC and CF will be
j295
