hul 2004
conflict
by their
e'to be
jer loop
ity and
more
st
ity:
cutObject
f incident
und
de labels
Due to
s have to
is stored
e 3-D-R-
esent the
cale. The
For the
cific map
: conflict
possible
| clipping
ithms are
etzold et.
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
EJ.» one layer - reactive conflict graph
LJ to one discrete scale
"dist area of the layer
node of the reactive conflict graph -
- key of the geometric data-structure
edge of the reactive conflict graph -
key of the geometric data-structure
query area -
area of the static conflict graph
= key of the reactive conflict graph node
M i| inthe geometric data-structure -
y = the height represents the scale interval
i within the object will be labeled
key of the reactive conflict graph edge
in the geometric data-struclure -
the height represents the scale interval
within the potential accur
X-axis
Figure 12 Embedding of the reactive conflict graph in a 3-
dimensional data-structure and the derivation of the
static conflict graph.
6. ANALOGY TO GENERALIZATION
The operation zooming for map labeling encloses aspects of
cartographic generalization for the labeling, mainly the selection
of objects to be labeled or the other way around, the deselection
of objects. For the deselection we developed a few cartographic
criteria and discussed the conflict free space criterion for point
and line objects in subsection 3.3. This kind of criterion can also
be applied to cartographic generalization. In addition, a
simplified case of displacement is treated by the shifting of label
positions.
The usage of an applied reactive conflict graph for the
generalization process will be also a benefit especially for
multiresolution aspects. In this data-structure, all information
necessary for the generalization process can be stored and it
enables an easy and quick access to these information.
Comparable to the introduced labeling process, generalization
algorithms can be based on this data-structure.
7. CONCLUSIONS
In this paper we presented an approach for modeling conflicts
for efficient label placement. It supports the labeling of point,
line and area objects and the operations of zooming and
scrolling. These operations are essential for screen maps.
Together with the developed two-phase-approach it enables
labeling in real-time, which means in a stroke-of-a-key.
Cartographic priority of positions, and minimizing of
information-loss are considered as well.
In contrast to our previous paper (Petzold et.al., 2003) we put
the focus here on the modeling of labeling conflicts. This
encapsulates which label information should be collected, how
it can be calculated and how to represent this information in a
purpose-build data-structure, the reactive conflict graph. The
generation of the reactive conflict graph is done in the so-called
preprocessing-phase.
With the reactive conflict graph, the running-time for the final
labeling in the interaction-phase can be reduced by shifting
time-consuming calculations in a so-called preprocessing-phase
as far as possible. Additionally, heuristics are used to reduce the
running time in both phases.
Essential for our concept is the determination of the labeling
difficulty, which is used to make a preselection of the objects to
be labeled, depending on object priority and scale. In addition,
233
this concept relaxes the restriction to discrete label positions
which is employed in many other approaches and satisfies
cartographic principles.
There is a strong analogy to cartographic generalization,
especially regarding the selection/deselection process and its
dependence on scale and potential to resolve conflicts, as well
as how conflicts are modeled. Thus the concept presented in this
paper can be extended to cartographic generalization.
The feasibility of the concept and the labeling in real-time is
demonstrated by a Java prototype. The point labeling is
implemented completely, while the line and arca labeling is
realized only partially.
References
Christensen, J., 1995. Managing Designs Complexity: Using
Stochastic Optimization in the Production of Computer
Graphics. Ph.D.-Thesis, Harvard University, USA.
Edmondson, S., Christensen, J., Marks, J., Shieber, S., 1996. A
General Cartographic Labeling Algorithm. Manuscript, Harvard
University, Cambridge, Massachusetts, USA.
Glassner, A., 1990. Graphics Gems. Academic Press, San
Diego, USA.
Guttman, A., 1984. R-trees: A Dynamic Index Structure for
Spatial Searching. In: Proc. of ACM SIGMOD Conference on
Management of Data, University of California, Berkeley, USA,
pp 47-57.
Harary, F., 1972. Graph Theory. Addison Wesley.
Imhof, E., 1962. Die Anordnung der Namen in der Karte. In:
International Yearbook of Cartography 1l, Kirschbaumverlag,
Bonn.
Oosterom, P., 1990. Reactive Data-Structures for Geographic
Information Systems. Ph.D.-Thesis, Department of Computer
Science, Leiden University, Netherlands.
Petzold, L, Plümer, L., 1997. Plazierung der Beschriftung in
dynamisch erzeugten Bildschirmkarten. In: Nachrichten aus
dem Vermessungswesen, Reihe I, Heft Nr. 117, Verlag des
Instituts für Angewandte Geodäsie, Frankfurt a. M..
Petzold, I., Plümer, L., Heber, M., 1999. Label- Placement for
dynamically generated screen maps. In: Proceedings of the
Ottawa ICC99, Canada.
Petzold, I., 2003. Beschriftung von Bildschirmkarten in Echtzeit
— Konzept und Struktur. Ph.D.-Thesis, Institute of Cartography
and Geoinformation, University of Bonn, Bonn.
http://hss.ulb.uni-bonn.de/ulb bonn/diss online/landw fak/
2003/petzold ingo/index.htm
Acknowledgements
The research and the prototype were funded by the DFG
(German Research Foundation) in the project “Labeling Screen
maps in real time”. We thank Dirk Burghardt and Robert
Weibel (both Geographic Information Systems Division,
Department of Geography, University of Ziirich, Switzerland)
as well as Axes-Systems AG in Alpnach, Switzerland for their
support, which enabled us to write the paper.
