Skip to content

Instantly share code, notes, and snippets.

@emeeks

emeeks/README.md

Last active January 16, 2020 13:25
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save emeeks/7669aa65a172bf69688ace5f6041223d to your computer and use it in GitHub Desktop.
Save emeeks/7669aa65a172bf69688ace5f6041223d to your computer and use it in GitHub Desktop.
Download ZIP
d3-bboxCollide
Raw
README.md

d3-bboxCollide provides bounding box collision detection for d3.forceSimulation. This is useful for label adjustment or rectangular nodes. Each node receives a bounding box array of a top right and bottom left corner of that node relative to its x position. In the case of this dataset, that size is based on the length of the word in the source dataset.

A function for calculating this array based off the data is passed into the d3.bboxCollide function, which is later passed as a "collide" constraint in your force settings.

var collide = d3.bboxCollide(function (d,i) {
    return [[-d.value * 10, -d.value * 5],[d.value * 10, d.value * 5]]
  })

The code above creates a rectangle scaled to the size of the randomized data. The data determines the y position creating a sort of rectilinear beeswarm plot.

Raw
collide.js
(function (global, factory) {
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-quadtree')) :
typeof define === 'function' && define.amd ? define(['exports', 'd3-quadtree'], factory) :
(factory((global.d3 = global.d3 || {}),global.d3));
}(this, function (exports,d3Quadtree) { 'use strict';
function bboxCollide (bbox) {
function x (d) {
return d.x + d.vx;
}
function y (d) {
return d.y + d.vy;
}
function constant (x) {
return function () {
return x;
};
}
var nodes,
boundingBoxes,
strength = 1,
iterations = 1;
if (typeof bbox !== "function") {
bbox = constant(bbox === null ? [[0,0][1,1]] : bbox)
}
function force () {
var i,
tree,
node,
xi,
yi,
bbi,
nx1,
ny1,
nx2,
ny2
var cornerNodes = []
nodes.forEach(function (d, i) {
cornerNodes.push({node: d, vx: d.vx, vy: d.vy, x: d.x + (boundingBoxes[i][1][0] + boundingBoxes[i][0][0]) / 2, y: d.y + (boundingBoxes[i][0][1] + boundingBoxes[i][1][1]) / 2})
cornerNodes.push({node: d, vx: d.vx, vy: d.vy, x: d.x + boundingBoxes[i][0][0], y: d.y + boundingBoxes[i][0][1]})
cornerNodes.push({node: d, vx: d.vx, vy: d.vy, x: d.x + boundingBoxes[i][0][0], y: d.y + boundingBoxes[i][1][1]})
cornerNodes.push({node: d, vx: d.vx, vy: d.vy, x: d.x + boundingBoxes[i][1][0], y: d.y + boundingBoxes[i][0][1]})
cornerNodes.push({node: d, vx: d.vx, vy: d.vy, x: d.x + boundingBoxes[i][1][0], y: d.y + boundingBoxes[i][1][1]})
})
var cn = cornerNodes.length
for (var k = 0; k < iterations; ++k) {
tree = d3Quadtree.quadtree(cornerNodes, x, y).visitAfter(prepareCorners);
for (i = 0; i < cn; ++i) {
var nodeI = ~~(i / 5);
node = nodes[nodeI]
bbi = boundingBoxes[nodeI]
xi = node.x + node.vx
yi = node.y + node.vy
nx1 = xi + bbi[0][0]
ny1 = yi + bbi[0][1]
nx2 = xi + bbi[1][0]
ny2 = yi + bbi[1][1]
tree.visit(apply);
}
}
function apply (quad, x0, y0, x1, y1) {
var data = quad.data
if (data) {
var bWidth = bbLength(bbi, 0),
bHeight = bbLength(bbi, 1);
if (data.node.index !== nodeI) {
var dataNode = data.node
var bbj = boundingBoxes[dataNode.index],
dnx1 = dataNode.x + dataNode.vx + bbj[0][0],
dny1 = dataNode.y + dataNode.vy + bbj[0][1],
dnx2 = dataNode.x + dataNode.vx + bbj[1][0],
dny2 = dataNode.y + dataNode.vy + bbj[1][1],
dWidth = bbLength(bbj, 0),
dHeight = bbLength(bbj, 1)
if (nx1 <= dnx2 && dnx1 <= nx2 && ny1 <= dny2 && dny1 <= ny2) {
var xSize = [Math.min.apply(null, [dnx1, dnx2, nx1, nx2]), Math.max.apply(null, [dnx1, dnx2, nx1, nx2])]
var ySize = [Math.min.apply(null, [dny1, dny2, ny1, ny2]), Math.max.apply(null, [dny1, dny2, ny1, ny2])]
var xOverlap = bWidth + dWidth - (xSize[1] - xSize[0])
var yOverlap = bHeight + dHeight - (ySize[1] - ySize[0])
var xBPush = xOverlap * strength * (yOverlap / bHeight)
var yBPush = yOverlap * strength * (xOverlap / bWidth)
var xDPush = xOverlap * strength * (yOverlap / dHeight)
var yDPush = yOverlap * strength * (xOverlap / dWidth)
if ((nx1 + nx2) / 2 < (dnx1 + dnx2) / 2) {
node.vx -= xBPush
dataNode.vx += xDPush
}
else {
node.vx += xBPush
dataNode.vx -= xDPush
}
if ((ny1 + ny2) / 2 < (dny1 + dny2) / 2) {
node.vy -= yBPush
dataNode.vy += yDPush
}
else {
node.vy += yBPush
dataNode.vy -= yDPush
}
}
}
return;
}
return x0 > nx2 || x1 < nx1 || y0 > ny2 || y1 < ny1;
}
}
function prepareCorners (quad) {
if (quad.data) {
return quad.bb = boundingBoxes[quad.data.node.index]
}
quad.bb = [[0,0],[0,0]]
for (var i = 0; i < 4; ++i) {
if (quad[i] && quad[i].bb[0][0] < quad.bb[0][0]) {
quad.bb[0][0] = quad[i].bb[0][0]
}
if (quad[i] && quad[i].bb[0][1] < quad.bb[0][1]) {
quad.bb[0][1] = quad[i].bb[0][1]
}
if (quad[i] && quad[i].bb[1][0] > quad.bb[1][0]) {
quad.bb[1][0] = quad[i].bb[1][0]
}
if (quad[i] && quad[i].bb[1][1] > quad.bb[1][1]) {
quad.bb[1][1] = quad[i].bb[1][1]
}
}
}
function bbLength (bbox, heightWidth) {
return bbox[1][heightWidth] - bbox[0][heightWidth]
}
force.initialize = function (_) {
var i, n = (nodes = _).length; boundingBoxes = new Array(n);
for (i = 0; i < n; ++i) boundingBoxes[i] = bbox(nodes[i], i, nodes);
};
force.iterations = function (_) {
return arguments.length ? (iterations = +_, force) : iterations;
};
force.strength = function (_) {
return arguments.length ? (strength = +_, force) : strength;
};
force.bbox = function (_) {
return arguments.length ? (bbox = typeof _ === "function" ? _ : constant(+_), force) : bbox;
};
return force;
}
exports.bboxCollide = bboxCollide;
Object.defineProperty(exports, '__esModule', { value: true });
}));
Raw
index.html
<html>
<head>
<title>Bounding Box Collision</title>
<meta charset="utf-8" />
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="collide.js"></script>
</head>
<style>
svg {
height: 500px;
width: 500px;
border: 1px solid lightgray;
}
</style>
<body>
<div id="viz">
<svg class="main">
</svg>
</div>
</body>
<footer>
<script>
var randomPoints = d3.range(500).map(function () {
return {value: Math.random()}
})
var networkCenter = d3.forceCenter().x(250).y(250);
var forceX = d3.forceX(function (d) {return 100})
.strength(0.1)
var forceY = d3.forceY(function (d) {return d.value * 500})
.strength(1)
var collide = d3.bboxCollide(function (d,i) {
return [[-d.value * 10, -d.value * 5],[d.value * 10, d.value * 5]]
})
.strength(1)
.iterations(2)
var color = d3.scaleOrdinal(d3.schemeCategory20b)
var force = d3.forceSimulation(randomPoints)
.velocityDecay(0.6)
.force("center", networkCenter)
.force("x", forceX)
.force("y", forceY)
.force("collide", collide)
.on("tick", updateNetwork);
var nodeEnter = d3.select("svg.main")
.append("g")
.selectAll("g.node")
.data(randomPoints)
.enter()
.append("g")
.attr("class", "node")
nodeEnter.append("rect")
.attr("class", "base")
.style("fill-opacity", 0.75)
.style("stroke-width", 1)
.style("stroke-opacity", 0.5)
.style("stroke", function (d, i) {return d3.color(color(i)).darker(2)})
.style("fill", function (d, i) {return d3.color(color(i)).brighter(2)})
.style("width", function (d) {return d.value * 20})
.style("height", function (d) {return d.value * 10})
.style("x", function (d) {return -d.value * 10})
.style("y", function (d) {return -d.value * 5})
function updateNetwork() {
d3.select("svg.main").selectAll("g.node")
.attr("transform", function (d) {return "translate(" + d.x + "," + d.y + ")"})
}
</script>
</footer>
</html>
@timelyportfolio
Copy link

timelyportfolio commented Sep 23, 2016 •
edited

Each node receives a bounding box array of a top right and bottom left corner of that node

do you mean top left and bottom right?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment