us.zuercher.gpx2map.plotter.label
Class LabelPositioningAlgorithm

java.lang.Object
  us.zuercher.gpx2map.plotter.label.LabelPositioningAlgorithm

public class LabelPositioningAlgorithm
extends Object

LabelPositioningAlgorithm uses simulated annealing to position labels near their markers in a way that minimizes overlap of labels.

The basic algorithm is taken from [1]. [1] references [2] and [3], which would probably be a better sources for the limited version of [1] that we implement here, but I was unable to find copies of them on the internet.

The algorithm is:

1. Place each label randomly (I relax this and place them in their preferred positions).
2. Compute N, the number of labels to position.
3. Compute initial labelling's E. If E == 0 (no overlaps), quit.
4. Initialize temperature (T), see below.
5. Repeat until T == 0 or E == 0 or 5N iterations with no change in E:
   1. Decrease T by 10% after every N iterations.
   2. Randomly choose a label and move it's position to another of the eight possible locations relative to its mark, randomly.
   3. Compute E and dE, the change in the labelling's evaluation.
   4. If dE > 0 (new labelling worse than old labelling), undo the repositioning with probability P = 1 - exp(-dE / T).

The initial value of T is such that P = 2/3 when dE = 1. In other words, T = 1 - ln(1/3). This seems very small, but it seems to work.

[1]	Shawn Edmondson, Jon Christensen, Joe Marks, and Stuart M. Shieber. A general cartographic labeling algorithm. Cartographica, 33(4):13-23, Winter 1997. http://www.eecs.harvard.edu/~shieber/Biblio/Papers/gen-label.pdf
[2]	Jon Christensen, Joe Marks, Stuart M. Shieber. 1993. Algorithms for cartographic label placement. In Gary G. Kelly, editor, Proceedings of the American Congress on Surveying and Mapping '93, Vol. 1 pages 75-89, New Orleans, Louisiana, February.
[3]	Jon Christensen, Joe Marks, Stuart M. Shieber. 1995. An empirical study of algorithms for point-feature label placement. ACM Transactions on Graphics, 14(3):203-232, July.

Author:

Stephan Zuercher

Field Summary

private List<Label>	labels List of labels to position.
private int	N Number of labels in labels.

Constructor Summary

LabelPositioningAlgorithm(List<Label> labels)
Constructs a new LabelPositioningAlgorithm for the given list of labels.

Method Summary

void	computePositions() Computes the optimal positioning for the given labels.
private double	evaluatePositioning() Computes E for a given labelling.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

labels

private final List<Label> labels

List of labels to position.

N

private final int N

Number of labels in labels.

Constructor Detail

LabelPositioningAlgorithm

public LabelPositioningAlgorithm(List<Label> labels)

Constructs a new LabelPositioningAlgorithm for the given list of labels.

Parameters:

labels - Labels to position. May be empty, must not be null.

Method Detail

computePositions

public void computePositions()

Computes the optimal positioning for the given labels. Each label is positioned at the preferred position. If no labels overlap, no further work is done. Otherwise, the algorithm described above is used to find an optimal positioning of labels.

This method is safe to call even when the list of labels is empty.

evaluatePositioning

private double evaluatePositioning()

Computes E for a given labelling. E == 0 implies that no lables are overlapping. E == 1 implies that one pair of labels overlap completely.

Future improvement: Modify this to take into account markers and lines so that we can avoid drawing labels on top of them. The rest of the algorithm can probably stay the same, although paper [1] referenced above should be read more closely, since it deals exactly with this type of algorithm.

Returns:

value of E for current labelling.