MODELING OF CONFLICTS FOR SCREEN MAP LABELING
[. Petzold ^*, G. Gróger?, L. Plümer®
* Dept. of Geography, University of Zürich, Winterthurerstrasse 109, CH-8057 Zürich, Switzerland -
petzold@geo.unizh.ch
® Inst. for Cartography and Geoinformation, University of Bonn, Meckenheimer Allee 172, D-53115 Bonn, Germany -
(groeger, pluemer)@ikg.uni-bonn.de
KEY WORDS: Cartography, GIS, Modeling, Data Structures, Real-time, Multiresolution, Generalization
ABSTRACT:
Map labeling is one of the most time-consuming and complex tasks during map generation. Additionally, if real-time map labeling is
demanded like for screen maps, traditional automatic labeling approaches are not sufficient since they also do not support user
interaction methods like zooming and scrolling — change of scale and map clip. Thus, we developed a new approach considering
these specific demands for screen maps. The core of our approach is the modeling of possible label conflicts. This includes the
identification of such conflicts depending upon their scale of occurrence and the storage of this information. Therefore, we designed
a purpose-build data-structure, the so-called reactive conflict graph. This data-structure is built up before a user interacts with the
system in the so-called preprocessing phase. It will be exploited during the interaction phase and ensures real-time labeling in a
cartographic adequate way. The developed approach supports the labeling of point, line and area objects. The feasibility is
successfully demonstrated in a component-based prototype.
1. INTRODUCTION
These days the use and importance of screen maps increases and
they supersede more often traditional paper maps, especially in
the context of mobile applications. The reason is their flexibility
and adaptability to the users’ specifications combined with the
potential for interactive navigation in geographic information
systems. This leads to specific demands on the functionality of
screen maps, like scrolling and zooming.
Labeling is one of the most time consuming tasks in the map
generation process, especially since each interaction leads to a
completely new labeling and must be achieved in real-time.
Scrolling demands not only the re-labeling at the clip border and
the added map clip, but a complete new labeling. In addition,
zooming a map not only requires changing the scale, but also a
modification of the label size and is closely related to the
(cartographic) generalization process.
The main goal of cartographic labeling is to avoid overlapping
between labels, since this affects the readability of maps.
Already for a fixed scale the determination of conflicts between
labels is highly time-consuming and the major task during the
labeling process. In general, there exist several possible labeling
positions for each object, which are called “labeling space of the
object”. This requires the determination of potential conflicts
between labeling spaces. These potential conflicts can be pre-
computed and stored in a suitable data-structure to reduce the
running-time during the main labeling process.
Due to the mentioned functionalities, screen maps are not
restricted to a certain scale. Since the occurrence of potential
conflicts depends on scale, the complexity of their
determination and modeling rises significantly. Considering
these difficulties, we developed a data-structure called “reactive
conflict graph,” which models the potential conflicts
independent of scale. The conflict graph is a graph whose nodes
are the objects to be labeled and whose edges represent the
potential conflicts. To take the scale into account, the edges are
228
attributed by the scale range of the occurrence of the potential
conflict between the two objects, which are connected by the
edge. So the reactive conflict graph enables efficient labeling.
Our concept of the reactive conflict graph covers point, line and
area objects to be labeled and takes the different geometric
shapes and properties into account.
During the zooming out, the number of conflicts increases.
Thus, we have to omit objects to be labeled. Deselection criteria
determine these objects, taking into account priorities and
further cartographic constraints. These criteria ensure that the
number of conflicts per object is reduced to an appropriate
level.
2. CARTOGRAPHIC BACKGROUND
This section covers the necessary cartographic map labeling
knowledge needed for understanding this paper as well as a
short discussion about the difference between paper (static) and
screen (dynamic) maps.
The obvious differences between paper and screen maps come
from the media: The resolution and size of screen maps are a
fraction of the resolution and size of paper maps. So the
symbols in screen maps are less filigree and also the density of
symbols for the same clip and scale is lower. Nevertheless, the
labeling of screen maps should have the same high quality as
paper maps.
Due to the media, screen maps can compensate the mentioned
disadvantages thru interactivity. The interactivity results from
the (screen map) functions of scrolling (changing the map
clipping), zooming (free choice of scale) and integrating
different thematic layers. As a result of the restrictions, the
interactivity and the described functions, screen maps are short-
lived. For a user-friendly interaction, these maps must be
generated on the stroke-of-a-key. This time factor compensates
Interna
the. dis
compat
For si
approat
It is ob
The siz
the maj
change
by an
depend
(refSca
labSize :
shrinkii
previou
In cont
sliding
spaces
and are
boxes f
wee IyogBurpunoq
wed egg
Figure
As sho
not rest
or more
space. 7
30
SC
Figure :
Accord
others. '
as prop:
For labs
the ang
of the |
used (Fi
The lab
a)). Du
object :
define t
huge bu
never |
comput:
the dist:
object, -
