Vertical label placement
Labels on a vertical axis may need to be moved up or down from their preferred positions to prevent overlaps. This page describes a fast (linear time) algorithm for vertical label placement that minimises the maximum absolute offset of any label from its preferred position, while respecting limits on how high or low labels may be placed.
In this interactive diagram, drag the points up or down to see the labels being repositioned using the algorithm:
On this page
- Formal statement of the problem
- The vertical label placement algorithm
- Asymptotic running time
- Rust implementation
Formal statement of the problem
Given:
- A set of n preferred positions, P = { p_{1}, p_{2}, … , p_{n} }
- A separation, s
- Limits, p_{min} and p_{max}
Such that:
- The preferred positions are sorted: p_{i} ≤ p_{j} if i < j
- Separation is required: s > 0
- The limits permit all labels to be placed: p_{max} − p_{min} ≥ (n − 1)s
Find a set of permitted positions Q = { q_{1}, q_{2}, … , q_{n} } such that:
- Labels are separated: q_{i+1} − q_{i} ≥ s for all i
- Limits are respected: p_{min} ≤ q_{i} ≤ p_{max} for all i
- Absolute offsets are minimised: max(|o_{i}|), where the offsets are defined by o_{i} = q_{i} − p_{i}, cannot be reduced with an alternative choice of Q
All p_{i}, s, p_{min}, p_{max}, and all q_{i} must be integers.
The vertical label placement algorithm
The vertical label placement algorithm works by transforming the preferred positions into separated clusters, and then transforming these clusters into permitted positions.
Clusters
A cluster represents a set of neighbouring labels whose permitted positions are separated by exactly s. A cluster is represented by a data structure with four fields:
- The start position, p_{start}
- The end position, p_{end}
- The minimum offset, o_{min}
- The maximum offset, o_{max}
For example, if a set of preferred positions { 10, 20, 20 } is transformed into a cluster with permitted positions { 8, 16, 24 } due to a separation of s = 8, then the offsets are { −2, −4, 4}, and hence p_{start} = 8, p_{end} = 24, o_{min} = −4, and o_{max} = 4.
The number of labels in a cluster does not need to be recorded as the permitted positions are just the set { p_{start}, p_{start} + s, p_{start} + 2s, … , p_{end} }.
In pseudocode, we will assume the existence of a function CREATE-CLUSTER(p_{start}, p_{end}, o_{min}, o_{max}) that creates a cluster.
Transforming clusters
The algorithm makes use of three simple functions for transforming clusters.
SHIFT moves an entire cluster by a chosen offset:
SHIFT(cluster, offset)
cluster[p_{start}] = cluster[p_{start}] + offset cluster[p_{end}] = cluster[p_{end}] + offset cluster[o_{min}] = cluster[o_{min}] + offset cluster[o_{max}] = cluster[o_{max}] + offset
BALANCE shifts a cluster to minimise the sum of o_{min} and o_{max}, which is equivalent to minimising the maximum absolute offset within the cluster:
BALANCE(cluster)
imbalance = ROUND-TOWARDS-ZERO((cluster[o_{min}] + cluster[o_{max}]) ÷ 2) SHIFT(cluster, −imbalance)
Note that rounding towards zero, rather than rounding down, ensures that a cluster with o_{min} = −m and o_{max} = m − 1 isn't needlessly shifted so that o_{min} = 1 − m and o_{max} = m, which would not reduce the maximum absolute offset.
LIMIT shifts a cluster to respect the limits:
LIMIT(cluster, p_{min}, p_{max})
if cluster[p_{start}] < p_{min} SHIFT(cluster, p_{min} − cluster[p_{start}]) if cluster[p_{end}] > p_{max} SHIFT(cluster, p_{max} − cluster[p_{end}])
Merging clusters
Using the functions for transforming clusters, we can now define MERGE, which creates a new cluster by merging two neighbouring clusters:
MERGE(cluster_{1}, cluster_{2}, s)
SHIFT(cluster_{1}, cluster_{2}[p_{start}] − cluster_{1}[p_{end}] − s) cluster = CREATE-CLUSTER( cluster_{1}[p_{start}], cluster_{2}[p_{end}], MIN(cluster_{1}[o_{min}], cluster_{2}[o_{min}]), MAX(cluster_{1}[o_{max}], cluster_{2}[o_{max}]) ) BALANCE(cluster) return cluster
MERGE works by shifting cluster_{1} so that its end position is separated from the start position of cluster_{2} by exactly s, fusing the two clusters end-to-end, and then balancing the resulting cluster.
The cluster list
The cluster list is a data structure used to store clusters. It is used as a stack, but must also support iteration to transform the clusters into a set of permitted positions. Most programming languages have a vector type that supports this functionality, while also allowing the required memory to be allocated on initialisation.
In pseudocode, we will assume the existence of a function CREATE-LIST that creates an empty list, and PUSH, POP, PEEK, and IS-EMPTY functions that operate on it as a stack.
Popping from the cluster list
POP-IF-NOT-SEPARATE pops and returns the last cluster from a cluster list if it is not sufficiently separated from a new cluster, and otherwise returns a NONE value and leaves the cluster list unchanged. Most programming languages would represent this with either an option type or a nullable type.
POP-IF-NOT-SEPARATE(list, cluster, s)
if not IS-EMPTY(list) and PEEK(list)[p_{end}] + s > cluster[p_{start}] return POP(list) else return NONE
Transforming the cluster list into positions
POSITIONS transforms a cluster list into a list of permitted positions:
POSITIONS(list, s)
positions = CREATE-LIST() for each cluster_{i} in list position = cluster_{i}[p_{start}] while position ≤ cluster_{i}[p_{end}] PUSH(positions, position) position = position + s return positions
Completing the algorithm
We can now complete the algorithm by defining PLACE:
PLACE(P, s, p_{min}, p_{max})
list = CREATE-LIST() for each p_{i} in P cluster = CREATE-CLUSTER(p_{i}, p_{i}, 0, 0) LIMIT(cluster, p_{min}, p_{max}) while previous = POP-IF-NOT-SEPARATE(list, cluster, s) cluster = MERGE(previous, cluster, s) LIMIT(cluster, p_{min}, p_{max}) PUSH(list, cluster) return POSITIONS(list, s)
PLACE works but iterating over the preferred positions, converting each to a single-position cluster, repeatedly merging this cluster with a cluster popped from the cluster list if they are not sufficiently separated, and then pushing the resulting cluster onto the cluster list.
The limits are applied each time a cluster is created. If limits are not required, the algorithm can easily be modified by removing the p_{min} and p_{max} arguments and the two calls to LIMIT.
Asymptotic running time
As the cluster for each p_{i} may be merged with up to i − 1 previous clusters, it may appear the algorithm has quadratic asymptotic running time — O(n^{2}). However, each merger pops a cluster from the cluster list, reducing the number of clusters available for future mergers. As only n clusters are ever pushed to the list, at most n − 1 mergers can occur, giving the algorithm linear asymptotic running time — O(n).
Rust implementation
A Rust crate containing a reference implementation of the vertical label placement algorithm is available on GitHub.