Skip to content

Instantly share code, notes, and snippets.

@w8r

w8r/Readme.md

Last active June 1, 2017 08:08
Show Gist options
  • Save w8r/db35a26c854ab6e93fa7716bb7f8a9fe to your computer and use it in GitHub Desktop.
Save w8r/db35a26c854ab6e93fa7716bb7f8a9fe to your computer and use it in GitHub Desktop.
Download ZIP
Circle packing!
Raw
Readme.md

Circle packing

Simple directed layout to pack different-sized circles as close as possible

Raw
index.html
<!doctype html>
<html>
<head>
<title>Simple circle packing</title>
<script src="https://unpkg.com/[email protected]"></script>
<style>
html, body {
margin: 0;
padding: 0;
width: 100%;
height: 100%;
}
.control {
position: absolute;
top: 20px;
right: 20px;
padding: 10px 20px;
font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;
font-weight: 300;
background: #fff;
border-radius: 4px;
box-shadow: 0 0 5px rgba(0,0,0,0.5);
}
.control h4 {
font-weight: 300;
}
.control input[type=number] {
width: 50px;
}
.circle {
fill: black;
fill-opacity: 0.5;
}
.focus {
fill: red;
}
text {
fill: white;
font-family: Monaco, 'Courier New', Courier, monospace;
}
</style>
</head>
<body>
<form class="control" id="form">
<p><label><input type="number" min="0" name="numCircles" value="50"> circles</label></p>
<p><label><input type="number" min="1" value="10" name="minR"> min R</label></p>
<p><label><input type="number" min="1" value="100" name="maxR"> max R</label></p>
<p><label><input type="number" min="0" value="5" step="1" name="padding"> padding</label></p>
<p><label><input type="number" min="-1" value="-1" name="pinned"> pinned node</label></p>
<p><label><input type="checkbox" name="weightedAttraction" checked> Push smaller nodes out</label>
<p><label><input type="checkbox" name="animate" checked> Animate</label>
<p>
<button name="generate" type="reset">Generate</button>
<button name="pack" type="submit">Pack</button>
</p>
</form>
<script src="index.js"></script>
</body>
</html>
Raw
index.js
const h = document.documentElement.clientHeight;
const w = document.documentElement.clientWidth;
// canvas
const svg = d3.select('body')
.append('svg')
.attr('width', w)
.attr('height', h)
.attr('viewBox', [-w/2, -h/2, w, h].join(' '))
.append('g');
var N, minR, maxR, animate;
var X = [];
var Y = [];
var R = [];
var C = [];
var padding = 100;
var pinned = -1;
var stepSize = 0.1;
var weightedAttraction = true;
var layout;
function magnitude (x, y) {
var dx = x - C[0];
var dy = y - C[1];
return (dx * dx + dy * dy);
}
function compare (u, v) {
var d1 = magnitude(X[u], Y[u]);
var d2 = magnitude(X[v], Y[v]);
return R[v] * d2 - R[u] * d1;
}
function pack ({maxIterations = 1000, animate = false, epsilon = stepSize / 10000 }) {
console.time('pack');
var indexes = R.map((r, i) => i).sort(compare);
var conv = 0, prevconv = 0;
var i = 0;
var renderTimeout = 16, renderTimer;
var stp = cubicIn(1 / N);
//epsilon = stp / (N * N);
console.log('step %f eps %f', stp, epsilon);
if (animate) {
layout = d3.timer((elapsed) => {
conv = run(indexes, pinned, C, padding, i / maxIterations, stp);
render();
if (Math.abs(prevconv - conv) < epsilon || i >= maxIterations) {
layout.stop();
console.timeEnd('pack');
console.log('done in %i interations', i);
}
prevconv = conv;
// debounce rendering
clearTimeout(renderTimer);
renderTimer = setTimeout(render, renderTimeout);
i++;
});
} else {
layout = { stop: () => { i = maxIterations; } };
for (i = 0; i < maxIterations; i++) {
conv = step(indexes, pinned, C, padding, i / maxIterations, stp);
//render();
if (Math.abs(prevconv - conv) < epsilon) break;
prevconv = conv;
}
console.timeEnd('pack');
console.log('done in %i interations', i);
}
render();
}
function run(indexes, pinned = -1, C, padding, elapsed, step, damping = 2) {
var res = 0; // global movement
var i, j, u, v, k, dist;
elapsed = cubicIn(elapsed);
// repulsion force
for (i = 0; i < N - 1; i++) {
for (j = i + 1; j < N; j++) {
if (i === j) continue;
u = indexes[i];
v = indexes[j];
var xu = X[u], yu = Y[u], ru = R[u];
var xv = X[v], yv = Y[v], rv = R[v];
var dx = xv - xu;
var dy = yv - yu;
var r = ru + rv + padding;
// squared distance
var d = (dx * dx + dy * dy);
if (d < (r * r - step)) {
// normalize velocity & ammortize
var vr = (r - Math.sqrt(d)) * elapsed;
var norm = 1 / d;
var vx = dx * norm * vr;
var vy = dy * norm * vr;
// record summary movement
dist = (vx * vx + vy * vy);
// apply repulsion if the nodes are not pinned
// k is to make shifts proportional to the counterpart's size
if (v !== pinned) {
k = (ru / minR); // how big is the impact of node u
res += dist * k;
X[v] += vx * k; Y[v] += vy * k;
}
if (u !== pinned) {
k = (rv / minR); // how big is the impact of node v
res += dist * k;
X[u] -= vx * k; Y[u] -= vy * k;
}
}
}
}
// attraction to center & amortization
var attraction = step * damping * (1 - elapsed);
var cx = C[0], cy = C[1];
for (i = 0; i < N; i++) {
u = indexes[i];
if (u !== pinned) {
x = X[u]; y = Y[u]; r = R[u];
k = r / maxR; // (maxR / r) if you want to push smaller nodes inside
var weight = weightedAttraction ?
attraction * k :
attraction;
vx = (x - cx) * weight;
vy = (y - cy) * weight;
dist = (vx * vx + vy * vy);
res += dist;
X[u] -= vx; Y[u] -= vy;
}
}
return res;
}
function render () {
svg.selectAll('circle').remove();
svg.selectAll('text').remove();
R.forEach((r, i) => {
var className = 'circle';
if (i === pinned) className += ' focus';
svg.append('circle')
.attr('cx', X[i])
.attr('cy', Y[i])
.attr('r', r)
.attr('id', 'circle-' + i)
.attr('class', className);
svg.append('text')
.attr('dx', (X[i] - (i < 10 ? 5 : 8)))
.attr('dy', (Y[i] + 8))
.text(i);
});
}
function quadOut (k) {
return k * k * k;
}
function quadIn (k) {
return k * (2 - k);
}
function cubicIn (k) {
return --k * k * k + 1;
}
var form = document.querySelector('.control');
function generate () {
if (layout) layout.stop();
N = parseInt(form['numCircles'].value);
minR = parseInt(form['minR'].value);
maxR = parseInt(form['maxR'].value);
X = new Array(N);
Y = new Array(N);
R = new Array(N);
for (var i = 0; i < N; i++) {
var r = minR + quadOut(i / N) * (maxR - minR);
R[i] = r;
X[i] = (w - 2 * r) * Math.random() - w / 2 + r;
Y[i] = (h - 2 * r) * Math.random() - h / 2 + r;
}
render();
}
form.addEventListener('submit', (evt) => {
evt.preventDefault();
padding = parseInt(form['padding'].value);
pinned = parseInt(form['pinned'].value);
animate = form['animate'].checked;
weightedAttraction = form['weightedAttraction'].checked;
C = (pinned !== -1) ? [X[pinned], Y[pinned]] : [0, 0];
if (layout) layout.stop();
pack({ animate });
});
form.addEventListener('reset', (evt) => {
evt.preventDefault();
generate();
render();
});
generate();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment