bul 2004
jects
1g spaces
eveloped
istinction
lification
its. Well-
er, 1990)
een both
identical
n method
on of the
Height
nce scale
veen the
'een both
onent the
ind a line
. labeling
cause the
ferent in
y special
ers of its
1 of these
d right of
ors above
'een point
ie cutting
(Petzold,
point and
p labeling
e labeling
nentioned
] b). it is
led in the
r words —
before the
g time.
ject below
s criterion
flict, but it
legree and
| (Petzold,
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
2003). A short overview can be found in (Petzold et. al., 2003).
This paper is restricted to the criterion best suited for
deselecting point and line objects: conflict free space. It is
insignificant if the conflict partners are labeling spaces or labels
of point or line objects or map objects, which should be
considered as long as they can be represented by a bounding
box.
legend: —
og Obiects to be
labeled
[labeling space
e) : Minden
Glonnu (Westy oot ;
Bielefeld
Münsters
Dortmund
Duisburgu i sen
uDüsseldorf
aKöln Siegen
SE „Aachen Bonn .
. i Le i Euskirchen
Figure 7. Impossibility to label all objects in small scales (a)
and b)) Restriction to less objects necessary:
deselection (c) to e)).
3.3.1 Deselection-criterion for point objects
For a specific scale, the difficulty to label a certain point object
can be determined by the calculation of the remaining free label
space. This can be done by considering the conflict labeling
spaces or conflict labels of other objects.
a) — IT +
San
——————À
| legend: DUM
label to be placed ! ]
| in corresponding r=
size ANN
peer ;
E fi ~ 4 :
L | area | se ~~. first vector of the area ¥,, or Y,,, ifunequal c
fabeling 7a. first vector ofthe area. X,,.or X, if unequal 2
Figure 8 The criterion conflict free space is illustrated in both
figures for the same example, separated for
horizontal a) and vertical labeling spaces b).
conflict free horizontal |c— ls
s symbol
labeling space E y
"s conflict free vertical distance
«, labeling space symbol-labelbox
Ta and y vectors of areas 1, 2, 3 und 4, if unequal &
Therefore the labeling space of a point object is split into areas
(Figure 8). Each area has at most the size of the label. The
distance between the symbol and the bounding box border is
equal to the height in the vertical direction or rather the width in
the horizontal direction of the label to be placed. So there is one
row of these areas around the symbol (Figure 8).
231
For each area, the remaining conflict free labeling spaces are
stored in vectors separately for the horizontal and vertical
directions, as visualized in Figure 8. Conflict free labeling
spaces for the horizontal sliding (above and below the symbol)
guarantee sufficient conflict free space for the label height, but
not automatically for the label width. This must be determined
in a subsequent step described later. This procedure is
analogous for the vertical sliding.
Each area in the corners of the bounding box has two vectors
starting from the closest corner to the symbol — one for the
horizontal and one for the vertical labeling spaces (Figure 8 a)
and b)). Each area (directly) above and below the symbol has
two vectors for representing the remaining. horizontal space
starting both from the closest corners to the symbol (Figure 8
a)). The areas (directly) left and right of the symbol are defined
analogously for the vertical space (Figure 8 b)).
The conflict free labeling spaces represented by the vectors are
evaluated separately for the horizontal and vertical sliding as
shown in Figure 8. Thus the level of difficulty of labeling an
object to a specific scale can be derived by the ratio free
labeling space and the label size. A value greater one for one
free space indicates that this space is huge enough to hold the
label conflict free.
a)
b) SideB
e # or T. joe N E
sir wand, stripeStart, stripeStart .
>. ; ; Jee,
stripeStart, SideA confici ree,
stripeEnd.*
Figure 9 The criterion ‘conflict free space’ for line objects is a
further development of the criterion for point objects.
It can handle conflicts with line and point objects to
be labeled a). The results are conflict free stripes b).
3.3.2 Deselection-criterion for line objects
For a line object, the remaining free label space can be cal-
culated for a certain scale, too. In contrast to point labeling, the
line labels wriggle along the line. Thus only the remaining free
space in one direction — parallel to the line — has to be com-
puted. This can be done by a "projection" of the conflict and
conflict free spaces on the line object from both sides, as
visualized in Figure 9.
4. DATA-STRUCTURE
— REACTIVE CONFLICT GRAPH —
So far we have described methods for determining information
about single conflicts. This section deals with assembling this
information, the data-structure to store this information and how
to build it up. As mentioned in the introduction to section 3, the
developed data-structure will store the conflict information for
