w8r/Readme.md

## Readme.md

      
    Raw
  

              Readme.md
            
          
    Circle packing

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

  
## index.html
<!doctype html>
<html>
  <head>
    <title>Simple circle packing</title>
    <script src="https://unpkg.com/d3@4.4.1"></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>

## 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();

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!doctype html>
	<html>
	<head>
	<title>Simple circle packing</title>
	<script src="https://unpkg.com/d3@4.4.1"></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>
	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();