Digital Humanist. Manhattan-based.
md`## Performance
The particular case here--1,900 points--is probably a little small to be useful. But purely looking at number of comparisons, my quad-tree method appears to perform perhaps slightly better than RBush: those two are followed by normal quadtree visit, with brute force (obviously) bringing up the rear.
I think that in relatively sparse overlap cases RBush seems to work better, but in highly dense situation with relatively small labels, the adjusted quadtree formula may require only half as many searches.
Of course, 'number of bounding box comparisons' is not the ideal metric; purely for performance, we'd rather just look at timing issues. But for understanding optimization possibilities in conjunction with this visualization, I find it useful.
Another option I don't do, that would work in flat 2d visualizations like this, is simply to keep another canvas around and draw the rectangles onto it, and then check pixel values before drawing a new rectangle. I think this would probably be fast! You could even cut out the canvas and write directly to a type Uint8 buffer in javascript treated as two dimensions on insertion. I think this would be fast. But that approach is much less generalizable than the ones here, so I'm not implementing it, especially because for the cases where it's useful (a visualization frame with few enough pixels to fit on a computer screen) it doesn't really matter what you do, honestly.
`
md`## Change number of items
The slider below changes the number of items up to 10,000. Be careful that you don't clobber your device!`
md`
## Explanation
A quadtree searches for points, but labels are rectangles. The big challenge with this method is that labels may extend well away from their center points; or, that a placed label might be large enough to engulf an existing label.
The solution is to not use points and quadtree.find, but instead to detect collisions, we traverse quads using quadtree.visit. Using their bounds, you can see if any points inside them could conceivably overlap with the bounding box of the object; that means you have to add the maximum width and height of known elements to quadtree size, since a label might spill out of its containing quad.
The visualization below shows, on mouseover, the traversal order for each point. Although this requires many fewer word comparisons, it also requires a large number of quadtree comparisons as well. So I show both quad bounding boxes (blue squares) and text element bounding boxes (red rectangles--you can generally tell the word they're anchored to). In general, this seems to take perhaps 1/10 the number of comparisons as the naive method; and there should be some other advantages in the case of a zoom.
`
svg = {
const svg = d3.select("#svg")
return svg
}
canvas = d3.select("canvas").node()
context = canvas.getContext('2d')
drawn = {
set_bboxes()
occlusion(data)
render_canvas()
return data
}
function render_canvas() {
context.clearRect(0, 0, width, height)
context.textAlign = "center";
context.textBaseline = 'middle'
data.forEach( d=> {
context.font = `${d.size}px Times New Roman`;
context.globalAlpha = d._occluded ? 0.15 : 1
context.fillStyle = 'black'
context.fillText(d.text, d._cx, d._cy)
})
}
function hasOverlaps(corners, compCorners) {
// mutable n_checks += 1
// Do the ys first, because they're more likely to be false in landscape-oriented elements and this function is usually false.
// For portrait-oriented, would be better to reverse this. But I don't know if it matters.
return (corners[2] < compCorners[3] &&
corners[3] > compCorners[2] &&
corners[0] < compCorners[1] &&
corners[1] > compCorners[0]);
}
data = {
const words = []
for (let i = 0; i < N; i++) {
words.push(rwg_words[Math.floor(Math.random()*rwg_words.length)])
}
d3.shuffle(words)
return words.map(d => {
return {
text: d, priority: Math.random(), "tx": Math.random() * width, "ty": Math.random()* height,
size: Math.sqrt((Math.random() + .5) * 332)}
}).slice(0, N)
}
Type JavaScript, then Shift-Enter. Ctrl-space for more options. Arrow ↑/↓ to switch modes.
function order(data, sort_key = d => d) {
return Array.from(Array(data.length).keys())
.sort((a, b) => sort_key(data[a]) < sort_key(data[b]) ? -1 : (sort_key(data[b]) < sort_key(data[a])) | 0)
}
search_tree = {
// A quadtree used for lookups on the canvas--different than the label occlusion one, though it doesn't have to be.
const tree = d3.quadtree().x(d => d._cx).y(d => d._cy)
tree.addAll(drawn)
return tree
}
function bbox_to_coords(bbox) {
return [bbox[0], bbox[2], bbox[1] - bbox[0], bbox[3] - bbox[2]]
}
md`A slot to store in-progress animations. There's probably a better way to do this with 'mutable' than hiding it in an array, but this works...`
animation = [d3.interval(function () {}, 1000)]
md`## Canvas rendering code`
text_els = {
let current_word = undefined;
d3.select("#canvas2").on("mousemove", function() {
const [x, y] = d3.mouse(this)
const d = search_tree.find(x, y)
if (d === current_word) {
return
}
current_word = d;
let foo = 0
const context = d3.select("#canvas2").node().getContext("2d")
context.clearRect(0, 0, width, height)
context.textAlign = "center"
context.textBaseline = 'middle'
context.globalAlpha = 1
context.font = `${d.size}px Times New Roman`;
context.fillStyle = 'red'
context.fillText(d.text, d._cx, d._cy)
d.highlit = true;
const bbox = d._bbox
context.beginPath()
context.strokeStyle='hotpink'
context.globalAlpha = .5
context.lineWidth = 5
context.fillStyle = 'none'
context.strokeRect(bbox[0] - 6, bbox[2] - 6, bbox[1] - bbox[0] +6 , bbox[3] - bbox[2] + 6)
context.stroke()
context.closePath()
// Visualize the current element.
animation[0].stop()
let i = -1;
function drawRects() {
if (i >= d.visited.length) {
animation[0].stop()
return
}
const n = d.visited[i++]
if (!n) {return}
context.beginPath()
context.globalAlpha = .66
context.strokeStyle = n.variety == "word" ? "orange": 'black'
context.lineWidth = n.variety == "word" ? 4 : 2
context.fillStyle = (n.variety == "word" && n.overlaps) ? "red" : "none"
context.rect(n.x0, n.y0, n.x1 - n.x0, n.y1 - n.y0)
context.stroke()
context.globalAlpha = (n.variety == "word" && n.overlaps) ? .3: 0
context.fill()
context.globalAlpha = 1
context.closePath()
}
animation[0] = d3.interval(drawRects, 100)
})
return svg
}
drawn_old = {
drawn
text_els
return occlusion(data)
}
html`<style>
svg { cursor: pointer; }
svg text.occluded { opacity: 0.1 }
svg text.focused { opacity: 1; fill: red }
svg text.related { fill: blue }
svg .node {
fill: none;
stroke: #aaa;
shape-rendering: crispEdges;
}
</style>`
formatOcclusion = function(data, sort_key) {
var iter_order = order(data, sort_key)
var labels;
if (which_visit == "brute") {
labels = []
iter_order.forEach((index, i) => {
const datum = data[index]
datum.visited = []
datum._occluded = labels.some((label, i) => {
const [x0, x1, y0, y1] = label._bbox
const overlaps = hasOverlaps(label._bbox, datum._bbox)
datum.visited.push({x0, y0, x1, y1, variety : "word", overlaps})
return overlaps
})
if (!datum._occluded) {labels.push(datum)}
})
} else if (which_visit == "RBush") {
const tree = new MyRBush(R_BUSH_PARAM);
iter_order.forEach((index, i) => {
const datum = data[index]
datum.visited = []
datum._occluded = false
if (tree.collides(datum)) {
datum._occluded = true
} else {
tree.insert(datum)
}
})
data[0].tree = tree
} else {
labels = d3.quadtree()
.x(d => (d._bbox[0] + d._bbox[1])/2)
.y(d => (d._bbox[2] + d._bbox[3])/2);
labels.extent([-80, -35], [width+80, height+35])
iter_order.forEach((index, i) => {
insert_and_check(data[index], labels)
data[index].order = i
})
}
}
function insert_and_check(datum, quadtree) {
const corners = datum._bbox
// Visit every quadtree section that overlaps the bounding box: if it finds an overlap with a particular node, abandon ship.
quadtree._max_width = quadtree._max_width || 0
quadtree._max_height = quadtree._max_height || 0
datum._occluded = false
if (DEBUG) {
datum.visited = []
}
quadtree[which_visit](
(node, x0, y0, x1, y1) => {
// Break in the event that it's the old quadtree visit algorithm.
if (datum._occluded) {return true}
if (DEBUG) {
datum.visited.push({x0, y0, x1: x1, y1: y1, variety : "quad", overlaps: false})
}
if (node.length) {
// true if it's a node, not a leaf.
// Check if we need to check children in this quadtree section. Returning true means halt search.
const box_intersects_quad = hasOverlaps(
corners,
[x0 - quadtree._max_width/2,
x1 + quadtree._max_width/2,
y0 - quadtree._max_height/2,
y1 + quadtree._max_height/2],
);
if (!box_intersects_quad) {
return true
} else {
datum.visited[datum.visited.length - 1].overlaps = true
return undefined
}
} else {
if (DEBUG) {
const [x0, x1, y0, y1] = node.data._bbox
const [x, y] = [(x0 + x1)/2, (y0 + y1)/2]
datum.visited.push({x0, y0, x1, y1, variety: "word", word: node.data.text, overlaps: false})
// datum.visited.push({x0:x - quadtree._max_width/2, y0:y - quadtree._max_height/2, x1:x + quadtree._max_width/2, y1:y + quadtree._max_height/2, variety: "word", word: node.data.text, overlaps: false})
}
if (hasOverlaps(corners, node.data._bbox)) {
if (DEBUG) {
datum.visited[datum.visited.length - 1].overlaps = true
}
datum._occluded = true
return "break";
}
}
}, [quadtree.x()(datum), quadtree.y()(datum)]);
// TODO: in zoom settings, sometimes you may want to add the point even if it isn't displayed to 'hold' the spot for later.
if (!datum._occluded) {
quadtree.add(datum)
if (quadtree._max_width < corners[1] - corners[0]) {
quadtree._max_width = (corners[1] - corners[0])
}
if (quadtree._max_height < (corners[3] - corners[2])) {
quadtree._max_height = corners[3] - corners[2]
}
}
}
md`## Visit algorithm
Here I rewrite the quadtree 'visit' algorithm to allow traversal order to not just be upper-right to lower-right, and to allow the callback to escape further exploration of the function if it returns 'break'.
`
visit2 = function(callback, target) {
// a modified version of quadtree.visit
// target is a set of [x,y] coordinates that determines which quads are visited first.
// The callback returns one of three values.
// If it's false, the search continues.
// If it's truthy, quadrants below the current depth are ignored.
// If it's "break", the quadtree visit sequence is immediately halted. (This is important
// for, e.g., collision detection.)
var quads = [], q, node = this._root, child, x0, y0, x1, y1, i, i_, x, y, response;
if (target) {
[x, y] = target
}
if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1));
while (q = quads.pop()) {
response = callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1)
if (response == "break") {break}
if (!response && node.length) {
var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
// wheres keeps track of which node is in which position... see below. A kludge.
const wheres = []
if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1)) && wheres.unshift(3);
if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1)) && wheres.unshift(2);
if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym)) && wheres.unshift(1);
if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym)) && wheres.unshift(0);
// quadtree.find uses the code below to figure out which quadrant to look in where i is
// the index, directly; but that breaks when using the optimization from quadtree.visit
// where unpopulated nodes are not visited. This could be optimized further.
if (target && (i = (y >= ym) << 1 | (x >= xm))) {
i_ = wheres.indexOf(i)
if (i_ > 0) {
q = quads[quads.length - 1];
quads[quads.length - 1] = quads[quads.length - 1 - i_];
quads[quads.length - 1 - i_] = q;
}
}
}
}
return this;
}
Quad = function(node, x0, y0, x1, y1) {
// From d3-quadtree: need this rewrite visit.
this.node = node;
this.x0 = x0;
this.y0 = y0;
this.x1 = x1;
this.y1 = y1;
}
DEBUG = true
height = 500
set_bboxes = function() {
// This is expensive, but can be done once. If zooming, we can simply store the aspect ratio, too... that's a later task.
// In canvas or webGL, the way this is done will be quite different.
// Even on different canvas providers, the bounding box may not be exactly the same because the better bbox standard isn't universally supported.
context.textAlign = 'center'
context.textBaseline = 'middle'
data.forEach(function(d) {
// if (d._bbox) {return}
context.font = `${d.size}px Times New Roman`
const ms = context.measureText(d.text)
/* From SVG
const bbox = this.getBBox();
// Set the corners, b/c that's what a quadtree needs.
d._bbox = [bbox.x, bbox.x + bbox.width, bbox.y, bbox.y + bbox.height]
*/
// The better way to get a bbox.
d._bbox = [d.tx - ms.actualBoundingBoxLeft,
d.tx + ms.actualBoundingBoxRight,
d.ty - ms.actualBoundingBoxAscent,
d.ty + ms.actualBoundingBoxDescent
]
if (isNaN(d._bbox[0])) {
// Not all browsers support the full standard.
d._bbox =[
d.tx - ms.width/2,
d.tx + ms.width/2,
d.ty - d.size*2/3, // Guess at the pixel ratio for the top and bottom based on the font size.
d.ty + d.size*2/3
]
}
// RBush has its own format.
d.minX = d._bbox[0]
d.maxX = d._bbox[1]
d.maxY = d._bbox[3]
d.minY = d._bbox[2]
// [d.minX, d.maxX, d.minY, d.maxY] = d._bbox
d._cx = d.tx // bbox.x + bbox.width/2
d._cy = d.ty // bbox.y + bbox.height/2
})
}
R_BUSH_PARAM = 2 // A low number maximizes RBush's performance on the metric here at the cost of insertion performance, which is the fair thing to do here. Although the higher numbers aren't much worse, really.
function occlusion(data) {
formatOcclusion(data, d => -d.priority)
return data
}
d3 = require("d3@5").then(d3 => {
// patch with the new visit function
d3.quadtree.prototype.visit2 = visit2
return d3
})
import {radio} from "@jashkenas/inputs"
class MyRBush extends RBush {
collides(new_node) {
let node = this.data;
new_node.visited = []
let cb = node
// Allow search from datapoints
const new_box = new_node._occluded ? this.toBBox(node) : new_node
new_node.visited.push({
x0:cb.minX,
x1: cb.maxX,
y0: cb.minY,
y1: cb.maxY,
variety: node.leaf ? "word": "quad"})
if (!intersects(new_box, cb)) return false;
const nodesToSearch = [];
while (node) {
for (let i = 0; i < node.children.length; i++) {
const child = node.children[i];
const childBBox = node.leaf ? this.toBBox(child) : child;
cb = childBBox
new_node.visited.push({x0:cb.minX, x1: cb.maxX, y0: cb.minY, y1: cb.maxY, variety: node.leaf ? "word": "quad"})
if (intersects(new_box, childBBox)) {
if (node.leaf || contains(new_box, childBBox)) return true;
nodesToSearch.push(child);
}
}
node = nodesToSearch.pop();
}
}
}
function box_to_corners(box) {
const oput = []
for (const x of box.slice(0, 2)) {
for (const y of box.slice(2, 4)) {
oput.push([x,y])
}
}
}
function contains(a, b) {
return a.minX <= b.minX &&
a.minY <= b.minY &&
b.maxX <= a.maxX &&
b.maxY <= a.maxY;
}
function intersects(a, b) {
// from RBush
return b.minX <= a.maxX &&
b.minY <= a.maxY &&
b.maxX >= a.minX &&
b.maxY >= a.minY;
}
RBush = require('rbush')
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
