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:

100% 75% 37% 50% 44% 57% Alpha 50% Beta 63% Gamma 25% Delta 0% Epsilon

On this page

  1. Formal statement of the problem
  2. The vertical label placement algorithm
    1. Clusters
    2. Transforming clusters
    3. Merging clusters
    4. The cluster list
    5. Popping from the cluster list
    6. Transforming the cluster list into positions
    7. Completing the algorithm
  3. Asymptotic running time
  4. Rust implementation

Formal statement of the problem

Given:

Such that:

Find a set of permitted positions Q = { q1, q2, … , qn } such that:

All pi, s, pmin, pmax, and all qi 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:

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 pstart = 8, pend = 24, omin = −4, and omax = 4.

The number of labels in a cluster does not need to be recorded as the permitted positions are just the set { pstart, pstart + s, pstart + 2s, … , pend }.

In pseudocode, we will assume the existence of a function CREATE-CLUSTER(pstart, pend, omin, omax) 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[pstart] = cluster[pstart] + offset
cluster[pend] = cluster[pend] + offset
cluster[omin] = cluster[omin] + offset
cluster[omax] = cluster[omax] + offset

BALANCE shifts a cluster to minimise the sum of omin and omax, which is equivalent to minimising the maximum absolute offset within the cluster:

BALANCE(cluster)
imbalance = ROUND-TOWARDS-ZERO((cluster[omin] + cluster[omax]) ÷ 2)

SHIFT(cluster, −imbalance)

Note that rounding towards zero, rather than rounding down, ensures that a cluster with omin = −m and omax = m − 1 isn't needlessly shifted so that omin = 1 − m and omax = m, which would not reduce the maximum absolute offset.

LIMIT shifts a cluster to respect the limits:

LIMIT(cluster, pmin, pmax)
if cluster[pstart] < pmin
        SHIFT(cluster, pmincluster[pstart])

if cluster[pend] > pmax
        SHIFT(cluster, pmaxcluster[pend])

Merging clusters

Using the functions for transforming clusters, we can now define MERGE, which creates a new cluster by merging two neighbouring clusters:

MERGE(cluster1, cluster2, s)
SHIFT(cluster1, cluster2[pstart] − cluster1[pend] − s)

cluster = CREATE-CLUSTER(
        cluster1[pstart],
        cluster2[pend],
        MIN(cluster1[omin], cluster2[omin]),
        MAX(cluster1[omax], cluster2[omax])
)

BALANCE(cluster)

return cluster

MERGE works by shifting cluster1 so that its end position is separated from the start position of cluster2 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)[pend] + s > cluster[pstart]
        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 clusteri in list
        position = clusteri[pstart]
        while positionclusteri[pend]
                PUSH(positions, position)
                position = position + s

return positions

Completing the algorithm

We can now complete the algorithm by defining PLACE:

PLACE(P, s, pmin, pmax)
list = CREATE-LIST()

for each pi in P
        cluster = CREATE-CLUSTER(pi, pi, 0, 0)
        LIMIT(cluster, pmin, pmax)

        while previous = POP-IF-NOT-SEPARATE(list, cluster, s)
                cluster = MERGE(previous, cluster, s)
                LIMIT(cluster, pmin, pmax)

        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 pmin and pmax arguments and the two calls to LIMIT.

Asymptotic running time

As the cluster for each pi may be merged with up to i − 1 previous clusters, it may appear the algorithm has quadratic asymptotic running time — O(n2). 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.