class AccurateBeeswarm {
constructor(items, radiusFun, xFun) {
this.items = items;
this.radiusFun = radiusFun;
let radius = 2;
this.diameter = radius * 2;
this.diameterSq = this.diameter * this.diameter;
this.xFun = xFun;
this.tieBreakFn = x => x;
this._oneSided = false;
this.maxR = Math.max(...items.map(d => radiusFun(d)));
this.rng = this._sfc32(1, 2, 3, 4);
}
withTiesBrokenRandomly() {
this.tieBreakFn = this._sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, 1);
return this;
}
oneSided() {
this._oneSided = true;
return this;
}
calculateYPositions() {
let all = this.items
.map((d, i) => ({
datum: d,
originalIndex: i,
x: this.xFun(d),
y: null,
placed: false,
forbiddenY: new UnionOfIntervals(),
score: 0,
bestPosition: 0,
heapPos: -1
}))
.sort((a, b) => a.x - b.x);
all.forEach(function(d, i) {
d.index = i;
});
let tieBreakFn = this.tieBreakFn;
all.forEach(function(d) {
d.tieBreaker = tieBreakFn(d.x);
});
let pq = new AccurateBeeswarmPriorityQueue(this.radiusFun);
pq.push(...all);
while (!pq.isEmpty()) {
let item = pq.pop();
item.placed = true;
// If nothing placed overlaps this circle on the x axis (even if
// they were side by side), choose the y position at random. This
// makes the plot look a bit more natural and less like the Mandelbrot
// set!
item.y =
item.forbiddenY.head.next != item.forbiddenY.tail
? item.bestPosition
: this.radiusFun(item.datum) * (this.rng() - .5) * 3;
this._updateYBounds(item, all, pq);
}
all.sort((a, b) => a.originalIndex - b.originalIndex);
return all.map(d => ({ datum: d.datum, x: d.x, y: d.y }));
}
// Random number generator
// https://stackoverflow.com/a/47593316
_sfc32(a, b, c, d) {
let rng = function() {
a >>>= 0;
b >>>= 0;
c >>>= 0;
d >>>= 0;
var t = (a + b) | 0;
a = b ^ (b >>> 9);
b = (c + (c << 3)) | 0;
c = (c << 21) | (c >>> 11);
d = (d + 1) | 0;
t = (t + d) | 0;
c = (c + t) | 0;
return (t >>> 0) / 4294967296;
};
for (let i = 0; i < 10; i++) {
rng();
}
return rng;
}
_updateYBounds(item, all, pq) {
for (let step of [-1, 1]) {
let xDist;
let r = this.radiusFun(item.datum);
for (
let i = item.index + step;
i >= 0 &&
i < all.length &&
(xDist = Math.abs(item.x - all[i].x)) < r + this.maxR;
i += step
) {
let other = all[i];
if (other.placed) continue;
let sumOfRadii = r + this.radiusFun(other.datum);
if (xDist >= r + this.radiusFun(other.datum)) continue;
let yDist = Math.sqrt(sumOfRadii * sumOfRadii - xDist * xDist);
let forbiddenInterval = [item.y - yDist, item.y + yDist];
other.forbiddenY.addInterval(forbiddenInterval);
other.bestPosition = other.forbiddenY.bestAvailableValue(
this._oneSided
);
let prevScore = other.score;
other.score = Math.abs(other.bestPosition);
if (other.score > prevScore) {
// It is never the case that other.score < prevScore here.
// The if statement is unnecessary, but makes the algorithm
// run a little faster.
pq.deprioritise(other);
}
}
}
}
}