Labels on Maps

From Tech

Jump to: navigation, search

Labeling a map is on of the tough challanges, maybe the hardest on at all.

Contents

[edit] Goals

Most freely available GIS systems are optimezed for speed since they are designed for interactive desktop use or as server sided map making tools that have to handle user requests in real time. Our goal is different: We do not have the resources to run a general map server. What we need is a server sided background process that checks periodicaly for missing maps. Speed is less important than quality. Thus, usual GIS systems are sub-optimal.

[edit] Criteria for good labels

As first described by Imhof, there are several, basicaly simple, rules for good label positioning.

  1. Labels must not intersect.
  2. Labels must not hide important map features.
  3. Labels should be as close as possible to the labeled object.
  4. The label's baseline should either be horizontal, parralel to a longitude circle or reflect the geometrical form of the labeld object.
  5. If a label's baseline is not horizontal, it should be visibly curved.
  6. The curving radius of a baseline must not be lower than a certain limit.

This sounds reasonable and simple, but in fact, this criteria result in rather complex mathematicel algorithms.

We can divide 3 groups of labels:

  1. Point objects like cities, tops of mountains etc.
  2. Line objects like rivers, streets etc.
  3. Area objects like lakes, countries, groups of mountains etc.

Each of them requires a different approach. All of them have to fullfill the above genenral criteria.

[edit] Literature

[edit] Optimisation from the mathematical point of view

Mathematicaly, the problem of finding good baselines and positions for labels is a non-linear optimization problem. We could define an overall energy function E(x_1, x_2, \dots,x_n) in dependency of the degrees of freedom for all labels. A labeling algorithm must minimize this energy in the high-dimensional problem space.

However, the energy E might be split into local energies for each label and terms resulting from label overlaps, thus

E(x_1, x_2, \dots,x_n) = \sum_{i=1}^l E_{loc,i} + \sum_{j=1}^p E_{ol,j}

where Eloc,i is the local energy of the ith label and Eol,j is the overlap energy resulting from the jth label pair.

Most labels are far enough away from most others, so that many Eol,j will be equal to 0.

It seems to be reasonable to optimize each label localy, first, and then to minimize overlap energies in a second step.

There exist several standard algorithms for optimisazion. Basicaly, we can divide them into 2 groups:

  1. Algorithms that need to know the energy gradient
  2. Algorithms that work without knowlege of the gradient

Generaly, algorithms that use the gradient are faster, but tend to hang in local minima. Thus, their usability is limited. Especialy labels for point objects and overlap energy terms produce an egg-box-potential with a lot of local minima. Furthermore, the discrete problem space of point labels does not allow an energy gradient. Here, algorithms that need not to know about the gradient seem to be more adequate. The most popular representants are Simulated Anealing (simulan) and Genetic algorithms.

[edit] Point objects

There are 8 main label posiotions for points: N, E, S, W, NE, SE, SW and NW, where the abreviations mean the geografic direction of the next label corner relative to the point. Eastern directions are slightly higher preferenced than western directions, N and S have even less priority.

In addition, there are some special purpose positions as 45° declined labels, especialy for dense cities along coastlines.

Since we can simply enumerate the different label positions, the problem space for the local energy for point objects is a discrete, one-dimensional space.

[edit] Line objects

Lines like rivers should be labeled by labels with a curved baseline that reflects the polyline of the river. A long river should be labeled by several, more or less equidistant labels. Additionaly, labels close to river mouths should be unambingous. The curvage of the baseline must not be too high. If possible, labels should be placed on rather horizontal parts of the river in order to make reading easier.

Generaly, line labels allow a comperatively wide range of placement along the line and are more flexible than point labels.

The problem of line labeling might be split into 2 parts:

  1. Finding a candidate baseline along the river.
  2. Finding a good position for the label on the candidate baseline.
The ε buffer and the inner circles according to the Knipping-Wolf algorithm. The blue line is more or less arbitrarily choosen from the VMAP0 database. The odd and self-intersecting buffer in the lower part is ugly, but it seems not to have bad impact on the algorithm since the inner circles avvicinate from the outward direction. The thicker black lines are the convex hull from where the algorthm has been started.
The ε buffer and the inner circles according to the Knipping-Wolf algorithm. The blue line is more or less arbitrarily choosen from the VMAP0 database. The odd and self-intersecting buffer in the lower part is ugly, but it seems not to have bad impact on the algorithm since the inner circles avvicinate from the outward direction. The thicker black lines are the convex hull from where the algorthm has been started.

Knipping and Wolf have investigated a high quality algorithm for line labels. The original algorithm is limited to x-monotone polylines, but it should be possible to extend their algorithm for all kind of lines. Instead of starting with an arc between the leftmost and the rightmost point, we could aply the line finding algorithm on each edge of the convex hull.

When the candidate baseline has been constructed, the local energy function depends on a one-dimensional, continuous problem space. If we want allow labels on both sides of the line, we have to add a discrete flag to the problem space that determines the side of the label.

[edit] Literature

[edit] Errata

There is a calculation error in L. Knipping's thesis on p. 20. The correct term for λ is

\lambda_{1,2} = -\frac{p}{2} \pm \sqrt{ \left(\frac{p}{2}\right)^2 - q},

with

\frac{p}{2} = \frac{(\vec{n}\vec{C} + c + r)\vec{n}\vec{v} - (\vec{C}-\vec{M})\vec{v}}{(\vec{n}\vec{v})^2-\vec{v}^2} and q = \frac{(\vec{n}\vec{C} + c + r)^2 - (\vec{C}-\vec{M})^2}{(\vec{n}\vec{v})^2-\vec{v}^2} .

[edit] Area objects

There are 2 1/2 approaches:

  1. The label is placed on the free area, the baseline reflects the area's extension.
  2. There are too many islands in the area, so that there is not enough free space for a label. Then, the label has to be written across islands.
  3. The area is so small that the label has to be placed along the outer edge of the area.

Case 3 leads to line labeling. Cases 1 and 2 are very simular. Case 2 leads to case 1 by simply ignoring all islands (inner rings of the polygon). Case 1 needs to be discribed in more detail.

Since the label should cover the whole area, letters have to be spaced equaly along the whole baseline. Thus, this kind of labeling problem is solved when a good baseline is found.

For finding a good baseline, 2 approaches have been investigated:

  1. Extracting the baseline from the medial axis of the polygon.
  2. Finding a baseline on base of a scalar field.

The medial axis is defined as the set of all points that have more than one nearest point on the edge of the polygon. For polygons without wholes, the medial axis is a branched linework consisting of straight lines and parabel sections. However, it should be sufficient to approximate it with straight lines. The medial axis of a polygon with wholes has a net like structure with one island in each mesh. The construction of the medial axis is closely related to Voronoi-graphs and there exist straight forward algorithms. But after having constructed the medial axis, there still remains the problem of selecting a good path through the medial axis suitable as label baseline. Furthermore, this path has to be smoothed. Done so, a line labeling algorithm could be applied on that path.

The 2nd, scalar field based, approach has shown quite good results and is maybe the better bet.

[edit] Optimizing the baseline using a scalar field

Assumed the polygon to be labeled is a lake, we can define a scalar function r(x,y) that measures the distance from each point (x,y) inside the polygon to the nearest point on the shore. We could understand r as the radius of the largest circle centered in point (x,y) that is completely inside the polygon. That's why it is called radius function. The set of all ridges of the radius function is the medial axis.

Now, we search a B-spline as label baseline. (This is mayby somewhat unorthodox since lines consisting of circular arcs and straight line segment seem to be more usual, but B-Splines are comperatively easy to calculate and esthetic, too). A good baseline should:

  1. be as long as possible
  2. be as far away from the shores as possible
  3. slightly and steadily be curved

The easiest (and often sufficient) case of a B-spline is a spline with 2 end points and 2 control points. Let Pi be the ith (of 4) point where P1 and P4 are the end points. The hull of the spline is a polyline consisting of 3 line segments between succeding points.

Conditions 1 and 2 can be modulated with an energy term

E_{r} := - \int r(s) ds

where s is the curve length parametrisation of the spline. The integral gets large if the spline is long and runs through points far away from the shore.

Condition 3 can be modulated with 2 additional energy terms

E_m = E_{m,0} \cdot (|\bar{\varphi}| - \varphi_0)^2

and

E_s = E_{s,0} \cdot \sigma(\varphi)

where φk are the angles between the line segments of the spline's hull, φ0 is a desired angle somewhat less than 180°, \bar{\phi} is the mean value and σ(φ) is the standard derivation of the φk. Em has its minimum value at 0 if the mean value of the φk is equal to the desired angle φ0. The higher the difference, the higher the penalty energy Em. Es measures the steadiness of the φk. If all φk are equal, the unsteadiness penalty energy Es is equal to 0.

Adding all this 3 energy terms, we get the energy function in dependency on the points Pi. The 8 coordinates of the 4 points Pi are the degrees of freedom for the baseline. All other variables are already defined by the polygon's geometry.

Test runs using a simulan algorithm have produced promissing results.
The green area represents the radius function inside the polygon. The dotted line is a possible label baseline. Here, the factor Es,0 has been choosen somewhat to low what leads to a longer, but too much curved baseline. Islands have been ignored.
The green area represents the radius function inside the polygon. The dotted line is a possible label baseline. Here, the factor Es,0 has been choosen somewhat to low what leads to a longer, but too much curved baseline. Islands have been ignored.

However, it should be possible the calculate the gradient function of the total energy. This would allow to use more efficient optimisation algorithms. Probably, the energy function is mostly smooth enough and has not to bad local minima.

Calculating the gradient of Em and Es analyticaly is not too complicated since the φk are closly dependend on the 4 points defining the hull. The integral in Er could be sufficiently approximated by a sum. It should be sufficient to calculate between 30 and 50 points sj on the spline curve, maybe even less. The good thing with splines is that each sj is given by

s_j = \sum_i B_{j,i} \cdot P_i

,i.e. each sj is the scalar product of a fix vector Bj,i and the 4-dimensional vector of the points Pi. Thus, the derivative \frac{\partial s_j}{\partial P_i} is easy to calculate.

The radius function must be calculated on a comperatively fine grid inside (and outside) the polygon. The radius function must be negative for outside points and should have a steep slope on the polygon's edge. Now, r(s) can be approximated as r(\tilde{s}) where \tilde{s} is the next grid point of s. Combining all this together leads to the approximation

\tilde{E}_r = - \sum_{j} \frac{1}{2} \left( r(\tilde{s}_{j+1}) + r(\tilde{s}_{j})\right) \cdot d(s_{j+1}, s_j)

where d is the euclidean distance of 2 succeding spline curve points. For calculating the gradient field \nabla \tilde{E}_r, we need to know the gradient field \nabla r(\tilde{s}), what needs to be calculated before running the opimisation algorithm.

[edit] Labeling engine

Maps will be neccessary in many differnt clippings and scales. Thus, for each map labels will have to be calculated from scratch. Since optimisation algorithms require a lot of processor power, it will be neccessary to write a label engine in a compilable language rather than an interpreter language. The first choice would be C/C++.

The engine needs to know about all objects to be labeled. It should be able to read this information from an easy to parse object description file or from stdin. The object description should referre to coordinates as used directly on the map rather than geografical coordinates. The information could be provided by a script that also invokes the labeling engine.

The labeling engine's output should be ready to use SVG that can be included into the map as a seperate Inkscape layer.

[edit] Literature

Retrieved from "http://www.wikivoyage.org/tech/Labels_on_Maps"
Personal tools