International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
the labeling process. The structure is designed to allow an
efficient labeling in a further step (section 5). In other words: it
will react promptly to the users interaction during the
interaction phase and delivers appropriate amount of detailed
data on labeling requests. These kind of data-structures are
called reactive data-structures (Oosterom, 1990) — in our case
*reactive conflict graph'.
For the data-structure we are using the well-known graph
concept (Harary, 1972). A graph consists of nodes and edges; an
edge connects two nodes. In our case each node represents one
object to be labeled and each edge a potential conflict between
both connected nodes or rather objects to be labeled. A potential
conflict is an overlapping between two labeling spaces.
reactive conflict graph edge
a]
small MA recor oie
üt 3 i , i SC
conflict free potential conflict conflict free
no edge edge no edge
no 2 conflict partners avallable no overlapping
[1owerBound
conflict between both nodes |
small sus Maas puce Cu
NR S
scale
overlapping/conflict]no overlapping
Jeutting scale
‘not labeled labeled - ae : e ‘scale
deselected
Il large
not labeled
labeled scale
deselected
deselection scale
deselect
Figure 10 A conflict edge attributed by a scale interval (top
axis) representing the conflict range. The lower
bound is derived from the larger deselection scale of
the involved nodes (nodel and node2 — two lower
axes). The upper bound is the cutting scale between
the labeling spaces of the involved nodes (second
axis from top).
The characteristic of a conflict is discussed in subsection 3.1 in
detail and visualized in Figure 4. It occurs in a scale-interval.
The upper bound of the interval is the cutting scale and can be
calculated as described in subsection 3.2.
The deselection scale for objects is determined by the
deselection criterion that is developed for the different object
types in subsection 3.3. This deselection-scale of each object is
passed to the involved potential conflicts (Figure 10). A
potential conflict disappears beneath the maximum of the
deselection-scales of the both incident objects.
As you discovered, a procedure to generate the data-structure
was not yet mentioned. In a naive approach, a potential conflict
would be assumed between all pairs of objects and in a further
step thinned out depending on the scale-interval of the conflict
edges. This would lead to a high running-time because a lot of
unnecessary conflicts would be assumed and afterwards deleted.
To avoid these disadvantages we developed an algorithm to
speed up the generation of the data-structure (Algorithm 1). The
data-structure is built up depending upon the object's priority. It
starts with the least important object and considers possible
conflicts to objects with higher priorities. MaxDifficult
represents the lower bound of the number of allowed possible
conflicts. In combination with the previously developed
deselection criterion, this is the minimum remaining conflict
free space. The allowed conflicts cannot be chosen only by their
priority, the scale and distance of occurrence have to be
considered in addition. This is performed in the inner loop
through the sorted cutting-scale-list.
Input: — objects to label with position, reference labeling, priority and
maxDifficulty (maximum labeling difficulty relatively to more
important objects)
Output: reactive conflict graph (nodes and edges)
» for each object in ascending order of priority (priorityObject):
* generate node
* calculate cutting-scale of priorityObject to all more important
objects
* sort these objects in descending order of cutting-scale
* run through cutting-scale-list (cufObject):
. calculate labeling difficulty between priorityObject and
cutObject and all previous elements of cutting-scale-list
if calculated labeling difficulty is higher than maxDifficulty.
then generate edge between priorityObject and cutObject
set upperBound to cutting-scale
else leave loop
* ifcutObject exists
° then set deselect on cutting-scale of cutObject + €
. else set deselect on 0
* for each pair of objects with same priority:
* calculate cutting-scale
* generate edge if cutting-scale greater than both deselect of incident
nodes and set upperBound to calculated cutting-scale
* for each edge:
* set/owerBound to maximum of deselect of incident nodes
* eliminate edge if upperBound smaller than lowerBound
Algorithm 1 Generation of the reactive conflict graph.
Bad Godesberg
Bonn - Leverkusen [1:1.307.001, 1:1.262.000]
Bonn - Bad Godesberg [1:2.247.001, 1:100.000]
Köln - Leverkusen [1:1.307.001, 1:274.000]
Kéln- Bad Godesberg — [1:2.247.001, 1:681.000]
Figure 11 Visualized reactive conflict graph with node labels
and edges attributed with scale intervals. Due to
space constraints, some of the scale intervals have to
be listed below the figure.
5. LABELING
For fast labeling and access, the reactive conflict graph is stored
in a three dimensional geometric data-structure like the 3-D-R-
Tree (Guttman, 1984). The first two dimensions represent the
geometry while the third dimension represents the scale. The
objects’ geometry or its bounding box is stored. For the
labeling, the reactive conflict graph is queried to a specific map
clipping and scale. The result — the so-called static conflict
graph — contains all objects to be labeled and all possible
conflicts between these objects for the specific map clipping
and scale. Details about the usage and labeling algorithms are
described in detail in (Petzold, 2003) and in short in (Petzold et.
al., 2003).
232
Interni
—
z-axis
(scale
14
Figure
The oj
cartogi
of obje
of obj
criterie
and lin
be ap
simpli
positio
The u
genera
multire
necess;
enable:
Compe
algoritl
In this
for eff
line ar
scrollir
Togeth
labelin
Cartog
inform:
In cont
the foc
encapsi
it can I
purpose
generat
preproc
With tl
labeling
time-co
as far a
running
Essenti
difficul
be labe
