bmershon · February 15, 2025 11:30
diff --git a/.block b/.block
 license: gpl-3.0
 height: 960
 border: no
diff --git a/apollonius-circle.js b/apollonius-circle.js
 // See http://bl.ocks.org/mbostock/7115f7a0393de96f2fdc
 // Implementation of the solutions for appolonius circles from Mike Bostock.
 function apolloniusCircle(x1, y1, r1, x2, y2, r2, x3, y3, r3) {

  // The quadratic equation (1):
  //
  //          0 = (x - x1)² + (y - y1)² - (r ± r1)²
  //          0 = (x - x2)² + (y - y2)² - (r ± r2)²
  //          0 = (x - x3)² + (y - y3)² - (r ± r3)²
  //
  // Use a negative radius to choose a different circle.
  // We must rewrite this in standard form Ar² + Br + C = 0 to solve for r.
  // Per http://mathworld.wolfram.com/ApolloniusProblem.html

  var a2 = 2 * (x1 - x2),
      b2 = 2 * (y1 - y2),
      c2 = 2 * (r2 - r1),
      d2 = x1 * x1 + y1 * y1 - r1 * r1 - x2 * x2 - y2 * y2 + r2 * r2,
      a3 = 2 * (x1 - x3),
      b3 = 2 * (y1 - y3),
      c3 = 2 * (r3 - r1),
      d3 = x1 * x1 + y1 * y1 - r1 * r1 - x3 * x3 - y3 * y3 + r3 * r3;

  // Giving:
  //
  //          x = (b2 * d3 - b3 * d2 + (b3 * c2 - b2 * c3) * r) / (a3 * b2 - a2 * b3)
  //          y = (a3 * d2 - a2 * d3 + (a2 * c3 - a3 * c2) * r) / (a3 * b2 - a2 * b3)
  //
  // Expand x - x1, substituting definition of x in terms of r.
  //
  //     x - x1 = (b2 * d3 - b3 * d2 + (b3 * c2 - b2 * c3) * r) / (a3 * b2 - a2 * b3) - x1
  //            = (b2 * d3 - b3 * d2) / (a3 * b2 - a2 * b3) + (b3 * c2 - b2 * c3) / (a3 * b2 - a2 * b3) * r - x1
  //            = bd / ab + bc / ab * r - x1
  //            = xa + xb * r
  //
  // Where:

  var ab = a3 * b2 - a2 * b3,
      xa = (b2 * d3 - b3 * d2) / ab - x1,
      xb = (b3 * c2 - b2 * c3) / ab;

  // Likewise expand y - y1, substituting definition of y in terms of r.
  //
  //     y - y1 = (a3 * d2 - a2 * d3 + (a2 * c3 - a3 * c2) * r) / (a3 * b2 - a2 * b3) - y1
  //            = (a3 * d2 - a2 * d3) / (a3 * b2 - a2 * b3) + (a2 * c3 - a3 * c2) / (a3 * b2 - a2 * b3) * r - y1
  //            = ad / ab + ac / ab * r - y1
  //            = ya + yb * r
  //
  // Where:

  var ya = (a3 * d2 - a2 * d3) / ab - y1,
      yb = (a2 * c3 - a3 * c2) / ab;

  // Expand (x - x1)², (y - y1)² and (r - r1)²:
  //
  //  (x - x1)² = xb * xb * r² + 2 * xa * xb * r + xa * xa
  //  (y - y1)² = yb * yb * r² + 2 * ya * yb * r + ya * ya
  //  (r - r1)² = r² - 2 * r1 * r + r1 * r1.
  //
  // Substitute back into quadratic equation (1):
  //
  //          0 = xb * xb * r² + yb * yb * r² - r²
  //              + 2 * xa * xb * r + 2 * ya * yb * r + 2 * r1 * r
  //              + xa * xa + ya * ya - r1 * r1
  //
  // Rewrite in standard form Ar² + Br + C = 0,
  // then plug into the quadratic formula to solve for r, x and y.

  var A = xb * xb + yb * yb - 1,
      B = 2 * (xa * xb + ya * yb + r1),
      C = xa * xa + ya * ya - r1 * r1,
      r = A ? (-B - Math.sqrt(B * B - 4 * A * C)) / (2 * A) : (-C / B);
  return isNaN(r) ? null : {x: xa + xb * r + x1, y: ya + yb * r + y1, r: r < 0 ? -r : r};
 }
diff --git a/index.html b/index.html
 <!DOCTYPE html>
 <meta charset="utf-8">
 <svg width="960" height="960"></svg>
 <script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script>
 <script src="https://d3js.org/d3-scale-chromatic.v1.min.js"></script>
 <script src="apollonius-circle.js" charset="utf-8"></script>
 <script src="subsets.js" charset="utf-8"></script>
 <script>

 var svg = d3.select("svg"),
    width = +svg.attr("width"),
    height = +svg.attr("height");

 var N = 8;

 var generations = [];

 var threeCircles = d3.range(3).map((d, i) => {
  return {
    x: width / 2 + width / 4 * Math.sin((i + 1) * 2 * Math.PI / 3 + Math.PI),
    y: height / 2 + height / 4 * Math.cos((i + 1) * 2 * Math.PI / 3 + Math.PI),
    r: 0,
    generation: 0,
  }
 });

 var initialRadius = distance(threeCircles[0].x, threeCircles[0].y,
                             threeCircles[1].x, threeCircles[1].y) / 2;

 threeCircles.forEach((d, i) => {
  d.r = initialRadius;
 });

 var bigCircle = enclosingCircle.apply(null, threeCircles);
 bigCircle.generation = -1;
 generations.push(bigCircle);
 Array.prototype.push.apply(generations, threeCircles);

 var color = d3.scaleSequential(d3.interpolateInferno)
    .domain([1, N]);

 iterate(N);

 function iterate(n) {
  let i = 0,
      triplets = [threeCircles];
      newTriplets = [];
      triplets = triplets.concat(subsets(threeCircles, 2).map((subset) => {
        return [bigCircle].concat(subset);
      }));

  while (++i <= n) {
    triplets.forEach((t) => {
      let solution;

      // Ensure the circle with the largest radius is the first of the triplet.
      // The largest radius circle may be the enclosing circle; the solutions
      // for the Apollonius circles (up to 8 of them) depends on orientation.
      t.sort((a, b) => -(a.r - b.r));

      // Choose which of the 8 possible Apollonius circles to solve for.
      if (t.indexOf(bigCircle) === -1) {
        solution = inscribedCircle.apply(null, t);
      } else {
        solution = borderCircle.apply(null, t);
      }

      solution.generation = i;
      generations.push(solution);

      // Each enclosing circle generates 3 more triplets which will each produce
      // a circle in the next generation.
      subsets(t, 2).forEach((subset) => {
        newTriplets.push([solution].concat(subset));
      });
    });

    triplets = newTriplets;
    newTriplets = [];
  }

 var circle = svg.selectAll(".circle")
    .data(generations)
  .enter().append("g")
    .attr("class", "circle")
    .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; });

 circle.append("circle")
    .attr("r", function(d) { return d.r; })
    .style("fill", function(d, i) { return d.generation < 1 ? 'none' : color(d.generation); });
 }

 function distance(x0, y0, x1, y1) {
  return Math.sqrt(Math.pow(x0 - x1, 2) + Math.pow(y0 - y1, 2));
 }

 function circleArea(c) {
  return Math.PI * c.r * c.r;
 }

 function enclosingCircle(c1, c2, c3) {
  return apolloniusCircle(c1.x, c1.y, +c1.r, c2.x, c2.y, +c2.r, c3.x, c3.y, +c3.r);
 }

 function borderCircle(c1, c2, c3) {
  return apolloniusCircle(c1.x, c1.y, +c1.r, c2.x, c2.y, -c2.r, c3.x, c3.y, -c3.r);
 }

 function inscribedCircle(c1, c2, c3) {
  return apolloniusCircle(c1.x, c1.y, -c1.r, c2.x, c2.y, -c2.r, c3.x, c3.y, -c3.r);
 }

 </script>
diff --git a/subsets.js b/subsets.js
 // Returns a list of all subsets of the given set A that contain k elements.
 function subsets(A, k) {
  let combinations = [];

  function _subsets(set, length) {
    if (length === set.length) {
      combinations.push(set);
      return;
    }

    for (let i = 0; i < set.length; i++) {
      let copy = set.slice(0);
      copy.splice(i, 1);
      _subsets(copy, length);
    }
  }

  _subsets(A, k);

  return combinations;
 }
diff --git a/thumbnail.png b/thumbnail.png
	// See http://bl.ocks.org/mbostock/7115f7a0393de96f2fdc
	// Implementation of the solutions for appolonius circles from Mike Bostock.
	function apolloniusCircle(x1, y1, r1, x2, y2, r2, x3, y3, r3) {

	// The quadratic equation (1):
	//
	// 0 = (x - x1)² + (y - y1)² - (r ± r1)²
	// 0 = (x - x2)² + (y - y2)² - (r ± r2)²
	// 0 = (x - x3)² + (y - y3)² - (r ± r3)²
	//
	// Use a negative radius to choose a different circle.
	// We must rewrite this in standard form Ar² + Br + C = 0 to solve for r.
	// Per http://mathworld.wolfram.com/ApolloniusProblem.html

	var a2 = 2 * (x1 - x2),
	b2 = 2 * (y1 - y2),
	c2 = 2 * (r2 - r1),
	d2 = x1 * x1 + y1 * y1 - r1 * r1 - x2 * x2 - y2 * y2 + r2 * r2,
	a3 = 2 * (x1 - x3),
	b3 = 2 * (y1 - y3),
	c3 = 2 * (r3 - r1),
	d3 = x1 * x1 + y1 * y1 - r1 * r1 - x3 * x3 - y3 * y3 + r3 * r3;

	// Giving:
	//
	// x = (b2 * d3 - b3 * d2 + (b3 * c2 - b2 * c3) * r) / (a3 * b2 - a2 * b3)
	// y = (a3 * d2 - a2 * d3 + (a2 * c3 - a3 * c2) * r) / (a3 * b2 - a2 * b3)
	//
	// Expand x - x1, substituting definition of x in terms of r.
	//
	// x - x1 = (b2 * d3 - b3 * d2 + (b3 * c2 - b2 * c3) * r) / (a3 * b2 - a2 * b3) - x1
	// = (b2 * d3 - b3 * d2) / (a3 * b2 - a2 * b3) + (b3 * c2 - b2 * c3) / (a3 * b2 - a2 * b3) * r - x1
	// = bd / ab + bc / ab * r - x1
	// = xa + xb * r
	//
	// Where:

	var ab = a3 * b2 - a2 * b3,
	xa = (b2 * d3 - b3 * d2) / ab - x1,
	xb = (b3 * c2 - b2 * c3) / ab;

	// Likewise expand y - y1, substituting definition of y in terms of r.
	//
	// y - y1 = (a3 * d2 - a2 * d3 + (a2 * c3 - a3 * c2) * r) / (a3 * b2 - a2 * b3) - y1
	// = (a3 * d2 - a2 * d3) / (a3 * b2 - a2 * b3) + (a2 * c3 - a3 * c2) / (a3 * b2 - a2 * b3) * r - y1
	// = ad / ab + ac / ab * r - y1
	// = ya + yb * r
	//
	// Where:

	var ya = (a3 * d2 - a2 * d3) / ab - y1,
	yb = (a2 * c3 - a3 * c2) / ab;

	// Expand (x - x1)², (y - y1)² and (r - r1)²:
	//
	// (x - x1)² = xb * xb * r² + 2 * xa * xb * r + xa * xa
	// (y - y1)² = yb * yb * r² + 2 * ya * yb * r + ya * ya
	// (r - r1)² = r² - 2 * r1 * r + r1 * r1.
	//
	// Substitute back into quadratic equation (1):
	//
	// 0 = xb * xb * r² + yb * yb * r² - r²
	// + 2 * xa * xb * r + 2 * ya * yb * r + 2 * r1 * r
	// + xa * xa + ya * ya - r1 * r1
	//
	// Rewrite in standard form Ar² + Br + C = 0,
	// then plug into the quadratic formula to solve for r, x and y.

	var A = xb * xb + yb * yb - 1,
	B = 2 * (xa * xb + ya * yb + r1),
	C = xa * xa + ya * ya - r1 * r1,
	r = A ? (-B - Math.sqrt(B * B - 4 * A * C)) / (2 * A) : (-C / B);
	return isNaN(r) ? null : {x: xa + xb * r + x1, y: ya + yb * r + y1, r: r < 0 ? -r : r};
	}
	<!DOCTYPE html>
	<meta charset="utf-8">
	<svg width="960" height="960"></svg>
	<script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script>
	<script src="https://d3js.org/d3-scale-chromatic.v1.min.js"></script>
	<script src="apollonius-circle.js" charset="utf-8"></script>
	<script src="subsets.js" charset="utf-8"></script>
	<script>

	var svg = d3.select("svg"),
	width = +svg.attr("width"),
	height = +svg.attr("height");

	var N = 8;

	var generations = [];

	var threeCircles = d3.range(3).map((d, i) => {
	return {
	x: width / 2 + width / 4 * Math.sin((i + 1) * 2 * Math.PI / 3 + Math.PI),
	y: height / 2 + height / 4 * Math.cos((i + 1) * 2 * Math.PI / 3 + Math.PI),
	r: 0,
	generation: 0,
	}
	});

	var initialRadius = distance(threeCircles[0].x, threeCircles[0].y,
	threeCircles[1].x, threeCircles[1].y) / 2;

	threeCircles.forEach((d, i) => {
	d.r = initialRadius;
	});

	var bigCircle = enclosingCircle.apply(null, threeCircles);
	bigCircle.generation = -1;
	generations.push(bigCircle);
	Array.prototype.push.apply(generations, threeCircles);

	var color = d3.scaleSequential(d3.interpolateInferno)
	.domain([1, N]);

	iterate(N);

	function iterate(n) {
	let i = 0,
	triplets = [threeCircles];
	newTriplets = [];
	triplets = triplets.concat(subsets(threeCircles, 2).map((subset) => {
	return [bigCircle].concat(subset);
	}));

	while (++i <= n) {
	triplets.forEach((t) => {
	let solution;

	// Ensure the circle with the largest radius is the first of the triplet.
	// The largest radius circle may be the enclosing circle; the solutions
	// for the Apollonius circles (up to 8 of them) depends on orientation.
	t.sort((a, b) => -(a.r - b.r));

	// Choose which of the 8 possible Apollonius circles to solve for.
	if (t.indexOf(bigCircle) === -1) {
	solution = inscribedCircle.apply(null, t);
	} else {
	solution = borderCircle.apply(null, t);
	}

	solution.generation = i;
	generations.push(solution);

	// Each enclosing circle generates 3 more triplets which will each produce
	// a circle in the next generation.
	subsets(t, 2).forEach((subset) => {
	newTriplets.push([solution].concat(subset));
	});
	});

	triplets = newTriplets;
	newTriplets = [];
	}

	var circle = svg.selectAll(".circle")
	.data(generations)
	.enter().append("g")
	.attr("class", "circle")
	.attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; });

	circle.append("circle")
	.attr("r", function(d) { return d.r; })
	.style("fill", function(d, i) { return d.generation < 1 ? 'none' : color(d.generation); });
	}

	function distance(x0, y0, x1, y1) {
	return Math.sqrt(Math.pow(x0 - x1, 2) + Math.pow(y0 - y1, 2));
	}

	function circleArea(c) {
	return Math.PI * c.r * c.r;
	}

	function enclosingCircle(c1, c2, c3) {
	return apolloniusCircle(c1.x, c1.y, +c1.r, c2.x, c2.y, +c2.r, c3.x, c3.y, +c3.r);
	}

	function borderCircle(c1, c2, c3) {
	return apolloniusCircle(c1.x, c1.y, +c1.r, c2.x, c2.y, -c2.r, c3.x, c3.y, -c3.r);
	}

	function inscribedCircle(c1, c2, c3) {
	return apolloniusCircle(c1.x, c1.y, -c1.r, c2.x, c2.y, -c2.r, c3.x, c3.y, -c3.r);
	}

	</script>
	// Returns a list of all subsets of the given set A that contain k elements.
	function subsets(A, k) {
	let combinations = [];

	function _subsets(set, length) {
	if (length === set.length) {
	combinations.push(set);
	return;
	}

	for (let i = 0; i < set.length; i++) {
	let copy = set.slice(0);
	copy.splice(i, 1);
	_subsets(copy, length);
	}
	}

	_subsets(A, k);

	return combinations;
	}