JS implementation of https://iamkate.com/code/vertical-label-placement/

clustering.js

class Cluster {
  start = 0;
  end = 0;
  min = 0;
  max = 0;
  items = [];

  constructor(items, start, end, min, max) {
    this.items = items;
    this.start = start;
    this.end = end;
    this.min = min;
    this.max = max;
  }

  shift(offset) {
    this.start += offset;
    this.end += offset;
    this.min += offset;
    this.max += offset;
    return this;
  }

  balance() {
    var imbalance = Math.floor((this.min + this.max) / 2);
    this.shift(-imbalance);
    return this;
  }

  limit(min, max) {
    if (this.start < min) this.shift(min - this.start);
    if (this.end > max) this.shift(max - this.end);
    return this;
  }

  static merge(a, b, separation) {
    a.shift(b.start - a.end - separation);
    var items = a.items.concat(b.items);
    var combined = new Cluster(
      items,
      a.start,
      b.end,
      Math.min(a.min, b.min),
      Math.max(a.max, b.max)
    );
    combined.balance();
    return combined;
  }
}

function popIfNotSeparate(list, cluster, separation) {
  var last = list.at(-1);
  if (!last) return;
  if ((last.end + separation) > cluster.start) {
    return list.pop();
  }
}

function placeItems(items, separation, min, max) {
  var list = [];
  for (var [item, y] of items) {
    var cluster = new Cluster([item], y, y, 0, 0);
    cluster.limit(min, max);
    var previous;
    while (previous = popIfNotSeparate(list, cluster, separation)) {
      cluster = Cluster.merge(previous, cluster, separation).limit(min, max);
      list.push(cluster);
      if (list.length == 1) break;
    }
    list.push(cluster);
  }
  return list;
}

module.exports = { Cluster, placeItems };