robinhouston · May 26, 2017 23:51
diff --git a/index.html b/index.html
 <!doctype html>
 <html>
 <head>
 <meta charset="utf-8">
 <title>MSW algorithm demo</title>
 <script src="https://d3js.org/d3.v4.min.js"></script>
 <style>
 body { margin: 0; height: 500px; position: relative; }
 #info { position: absolute; width: 100%; height: 100px; bottom: 0; padding: 35px; box-sizing: border-box; }
 #info.step-0 span.step-0,
 #info.step-1 span.step-1,
 #info.step-2 span.step-2,
 #info.step-3 span.step-3,
 #info.step-4 span.step-4 { color: red; }
 #input-circles text {
  font-family: sans-serif; font-weight: bold; font-size: 18px;
  alignment-baseline: middle; text-anchor: middle;
  fill: white;
 }
 #input-circles circle { fill: rgba(80,90,100,0.5); }
 #input-circles .basis circle { fill: rgba(20,20,20,1); }
 #enclosing-circles circle { fill: none; stroke: red; }
 </style>
 </head>
 <body>
 <svg width="960" height="500">
 	<g id="input-circles"></g>
  <g id="enclosing-circles"></g>
 </svg>
 <div id="info">
  <code>findBasis([<span class="step-4"><span class="step-3"><span class="step-2"><span class="step-1">a</span>,b</span>,c</span>,d</span>], 4, [a,b,e])</code> does not enclose <code>e</code><br>
  <button id="prev">←</button><button id="next">→</button>
 </div>
 <script>
 function encloseBasis(B) {
  switch (B.length) {
    case 1: return enclose1(B[0]);
    case 2: return enclose2(B[0], B[1]);
    case 3: return enclose3(B[0], B[1], B[2]);
  }
 }

 function enclose1(a) {
  return {
    x: a.x,
    y: a.y,
    r: a.r
  };
 }

 function enclose2(a, b) {
  var x1 = a.x, y1 = a.y, r1 = a.r,
      x2 = b.x, y2 = b.y, r2 = b.r,
      x21 = x2 - x1, y21 = y2 - y1, r21 = r2 - r1,
      l = Math.sqrt(x21 * x21 + y21 * y21);
  return {
    x: (x1 + x2 + x21 / l * r21) / 2,
    y: (y1 + y2 + y21 / l * r21) / 2,
    r: (l + r1 + r2) / 2
  };
 }

 function enclose3(a, b, c) {
  var x1 = a.x, y1 = a.y, r1 = a.r,
      x2 = b.x, y2 = b.y, r2 = b.r,
      x3 = c.x, y3 = c.y, r3 = c.r,
      a2 = x1 - x2,
      a3 = x1 - x3,
      b2 = y1 - y2,
      b3 = y1 - y3,
      c2 = r2 - r1,
      c3 = r3 - r1,
      d1 = x1 * x1 + y1 * y1 - r1 * r1,
      d2 = d1 - x2 * x2 - y2 * y2 + r2 * r2,
      d3 = d1 - x3 * x3 - y3 * y3 + r3 * r3,
      ab = a3 * b2 - a2 * b3,
      xa = (b2 * d3 - b3 * d2) / (ab * 2) - x1,
      xb = (b3 * c2 - b2 * c3) / ab,
      ya = (a3 * d2 - a2 * d3) / (ab * 2) - y1,
      yb = (a2 * c3 - a3 * c2) / ab,
      A = xb * xb + yb * yb - 1,
      B = 2 * (r1 + xa * xb + ya * yb),
      C = xa * xa + ya * ya - r1 * r1,
      r = A ? (B + Math.sqrt(B * B - 4 * A * C)) / (2 * A) : C / B,
      x = x1 + xa - xb * r,
      y = y1 + ya - yb * r;
  return {
    x: x,
    y: y,
    r: Math.max(
      Math.sqrt((x1 -= x) * x1 + (y1 -= y) * y1) + r1,
      Math.sqrt((x2 -= x) * x2 + (y2 -= y) * y2) + r2,
      Math.sqrt((x3 -= x) * x3 + (y3 -= y) * y3) + r3
    )
  };
 }

 var a = {name: "a", x: 300, y: 50, r: 20},
    b = {name: "b", x: 300, y: 350, r: 20},
    c = {name: "c", x: 100, y: 50, r: 20},
    d = {name: "d", x: 600, y: 260, r: 20},
    e = {name: "e", x: 50,  y: 260, r: 20};
 var circles = [a,b,c,d,e];

 var input_circles = d3.select("#input-circles").selectAll("g").data(circles);
 var input_circles_enter = input_circles.enter().append("g");
 input_circles_enter.append("circle");
 input_circles_enter.append("text");
 input_circles = input_circles_enter.merge(input_circles)
  .attr("id", d => d.name)
  .attr("transform", d => `translate(${d.x}, ${d.y})`);
 input_circles.select("text").text(d => d.name);
 input_circles.select("circle").attr("r", d => d.r)
 input_circles.exit().remove();

 var steps = [
  [a,b,e],
  [a,b,e],
  [a,b,e],
  [b,c],
  [c,d],
 ];

 var step;
 function setStep(s) {
  if (s < 0 || s >= steps.length) return;

  step = s;
  d3.select("#info").attr("class", "step-" + step);

  var basis = steps[step];
  var enclosing_circles = d3.select("#enclosing-circles").selectAll("circle")
    .data([encloseBasis(basis)]);
  enclosing_circles.enter().append("circle")
    .merge(enclosing_circles)
    .attr("cx", d => d.x)
    .attr("cy", d => d.y)
    .attr("r", d => d.r)
  enclosing_circles.exit().remove();

  input_circles.classed("basis", d => basis.indexOf(d) > -1);
 }

 setStep(0);
 d3.select("#prev").on("click", () => setStep(step - 1));
 d3.select("#next").on("click", () => setStep(step + 1));
 </script>
 </body>
 </html>
	<!doctype html>
	<html>
	<head>
	<meta charset="utf-8">
	<title>MSW algorithm demo</title>
	<script src="https://d3js.org/d3.v4.min.js"></script>
	<style>
	body { margin: 0; height: 500px; position: relative; }
	#info { position: absolute; width: 100%; height: 100px; bottom: 0; padding: 35px; box-sizing: border-box; }
	#info.step-0 span.step-0,
	#info.step-1 span.step-1,
	#info.step-2 span.step-2,
	#info.step-3 span.step-3,
	#info.step-4 span.step-4 { color: red; }
	#input-circles text {
	font-family: sans-serif; font-weight: bold; font-size: 18px;
	alignment-baseline: middle; text-anchor: middle;
	fill: white;
	}
	#input-circles circle { fill: rgba(80,90,100,0.5); }
	#input-circles .basis circle { fill: rgba(20,20,20,1); }
	#enclosing-circles circle { fill: none; stroke: red; }
	</style>
	</head>
	<body>
	<svg width="960" height="500">
	<g id="input-circles"></g>
	<g id="enclosing-circles"></g>
	</svg>
	<div id="info">
	<code>findBasis([<span class="step-4"><span class="step-3"><span class="step-2"><span class="step-1">a</span>,b</span>,c</span>,d</span>], 4, [a,b,e])</code> does not enclose <code>e</code><br>
	<button id="prev">←</button><button id="next">→</button>
	</div>
	<script>
	function encloseBasis(B) {
	switch (B.length) {
	case 1: return enclose1(B[0]);
	case 2: return enclose2(B[0], B[1]);
	case 3: return enclose3(B[0], B[1], B[2]);
	}
	}

	function enclose1(a) {
	return {
	x: a.x,
	y: a.y,
	r: a.r
	};
	}

	function enclose2(a, b) {
	var x1 = a.x, y1 = a.y, r1 = a.r,
	x2 = b.x, y2 = b.y, r2 = b.r,
	x21 = x2 - x1, y21 = y2 - y1, r21 = r2 - r1,
	l = Math.sqrt(x21 * x21 + y21 * y21);
	return {
	x: (x1 + x2 + x21 / l * r21) / 2,
	y: (y1 + y2 + y21 / l * r21) / 2,
	r: (l + r1 + r2) / 2
	};
	}

	function enclose3(a, b, c) {
	var x1 = a.x, y1 = a.y, r1 = a.r,
	x2 = b.x, y2 = b.y, r2 = b.r,
	x3 = c.x, y3 = c.y, r3 = c.r,
	a2 = x1 - x2,
	a3 = x1 - x3,
	b2 = y1 - y2,
	b3 = y1 - y3,
	c2 = r2 - r1,
	c3 = r3 - r1,
	d1 = x1 * x1 + y1 * y1 - r1 * r1,
	d2 = d1 - x2 * x2 - y2 * y2 + r2 * r2,
	d3 = d1 - x3 * x3 - y3 * y3 + r3 * r3,
	ab = a3 * b2 - a2 * b3,
	xa = (b2 * d3 - b3 * d2) / (ab * 2) - x1,
	xb = (b3 * c2 - b2 * c3) / ab,
	ya = (a3 * d2 - a2 * d3) / (ab * 2) - y1,
	yb = (a2 * c3 - a3 * c2) / ab,
	A = xb * xb + yb * yb - 1,
	B = 2 * (r1 + xa * xb + ya * yb),
	C = xa * xa + ya * ya - r1 * r1,
	r = A ? (B + Math.sqrt(B * B - 4 * A * C)) / (2 * A) : C / B,
	x = x1 + xa - xb * r,
	y = y1 + ya - yb * r;
	return {
	x: x,
	y: y,
	r: Math.max(
	Math.sqrt((x1 -= x) * x1 + (y1 -= y) * y1) + r1,
	Math.sqrt((x2 -= x) * x2 + (y2 -= y) * y2) + r2,
	Math.sqrt((x3 -= x) * x3 + (y3 -= y) * y3) + r3
	)
	};
	}

	var a = {name: "a", x: 300, y: 50, r: 20},
	b = {name: "b", x: 300, y: 350, r: 20},
	c = {name: "c", x: 100, y: 50, r: 20},
	d = {name: "d", x: 600, y: 260, r: 20},
	e = {name: "e", x: 50, y: 260, r: 20};
	var circles = [a,b,c,d,e];

	var input_circles = d3.select("#input-circles").selectAll("g").data(circles);
	var input_circles_enter = input_circles.enter().append("g");
	input_circles_enter.append("circle");
	input_circles_enter.append("text");
	input_circles = input_circles_enter.merge(input_circles)
	.attr("id", d => d.name)
	.attr("transform", d => `translate(${d.x}, ${d.y})`);
	input_circles.select("text").text(d => d.name);
	input_circles.select("circle").attr("r", d => d.r)
	input_circles.exit().remove();

	var steps = [
	[a,b,e],
	[a,b,e],
	[a,b,e],
	[b,c],
	[c,d],
	];

	var step;
	function setStep(s) {
	if (s < 0 \|\| s >= steps.length) return;

	step = s;
	d3.select("#info").attr("class", "step-" + step);

	var basis = steps[step];
	var enclosing_circles = d3.select("#enclosing-circles").selectAll("circle")
	.data([encloseBasis(basis)]);
	enclosing_circles.enter().append("circle")
	.merge(enclosing_circles)
	.attr("cx", d => d.x)
	.attr("cy", d => d.y)
	.attr("r", d => d.r)
	enclosing_circles.exit().remove();

	input_circles.classed("basis", d => basis.indexOf(d) > -1);
	}

	setStep(0);
	d3.select("#prev").on("click", () => setStep(step - 1));
	d3.select("#next").on("click", () => setStep(step + 1));
	</script>
	</body>
	</html>