Algorithms for Labeling Focus Regions
IEEE Transactions on Visualization and Computer Graphics, 18 (12):
2583--2592 (2012)DOI: 10.1109/TVCG.2012.193
Abstract
In this paper, we investigate the problem of
labeling point sites in focus regions of maps or
diagrams. This problem occurs, for example, when
the user of a mapping service wants to see the names
of restaurants or other POIs in a crowded downtown
area but keep the overview over a larger area. Our
approach is to place the labels at the boundary of
the focus region and connect each site with its
label by a linear connection, which is called a
leader. In this way, we move labels from the focus
region to the less valuable context region
surrounding it. In order to make the leader layout
well readable, we present algorithms that rule out
crossings between leaders and optimize other
characteristics such as total leader length and
distance between labels. This yields a new
variant of the boundary labeling problem, which has
been studied in the literature. Other than in
traditional boundary labeling, where leaders are
usually schematized polylines, we focus on leaders
that are either straight-line segments or Bézier
curves. Further, we present algorithms that, given
the sites, find a position of the focus region that
optimizes the above characteristics. We also
consider a variant of the problem where we have more
sites than space for labels. In this situation, we
assume that the sites are prioritized by the user.
Alternatively, we take a new facility-location
perspective which yields a clustering of the sites.
We label one representative of each cluster. If the
user wishes, we apply our approach to the sites
within a cluster, giving details on demand.
