w8r/Readme.md

## Readme.md

      
    Raw
  

              Readme.md
            
          
    Largest empty circle


## index.html
<!doctype html>
<html>
  <head>
    <title>Largest empty circle</title>
    <script src="https://unpkg.com/d3@4.4.1"></script>
    <script src="https://unpkg.com/faster-delaunay@1.0.0"></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;
      font-size: 13px;
      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;
      }

      .control div {
        margin-top: 5px;
      }

    </style>
  </head>
  <body>
    <canvas id="canvas"></canvas>
    <form class="control" id="params">
      <div>
        <label>
          <input type="number" id="candidates" value="15"> Candidates</label>
      </div>
      <div>
        <label>
          <input type="number" id="minRadius" value="0"> R<sub>min</sub></label>
      </div>
    </form>
    <script src="index.js"></script>
  </body>
</html>

## index.js
const h = document.documentElement.clientHeight;
const w = document.documentElement.clientWidth;

var canvas = d3.select('canvas').on('mousemove', moved).node();
var context = canvas.getContext('2d');

var candidatesInput = document.getElementById('candidates');
var minRadiusInput  = document.getElementById('minRadius');

var pxRatio = window.devicePixelRatio;

var width = w * pxRatio;
var height = h * pxRatio;
var nodeSize = 7.5;
var counter = 0;

canvas.width = width; canvas.height = height;
canvas.style.width = w + 'px';
canvas.style.height = h + 'px';

function generateDenseTree(N = 150) {
  return {
    nodes: new Array(N).fill(0).map(function(_, i) {
      counter++;
      return {
        id: i,
        text: 'Node #' + i,
        x: Math.random() * width,
        y: Math.random() * height
      };
    }),
    edges: new Array(N - 1).fill(0).map(function(_, i) {
      counter++;
      return {
        id: i,
        source: Math.floor(Math.sqrt(i)),
        target: i + 1
      };
    })
  };
}

var { nodes, edges } = generateDenseTree();
var circles;
var idMap = nodes.reduce((map, node) => {
  map[node.id] = node;
  return map;
}, {});

var adjacencyTable = edges.reduce((acc, edge) => {
  var { source, target } = edge;
  acc[source] = acc[source] || [];
  if (acc[source].indexOf(target) === -1)acc[source].push(target);

  acc[target] = acc[target] || [];
  if (acc[target].indexOf(source) === -1) acc[target].push(source);
  return acc;
}, {});

var mouseX = 0, mouseY = 0;

collapseFlowerNodes(false)

redraw();

var simulation = d3.forceSimulation(nodes)
    .force('charge', d3.forceManyBody())
    .force('link', d3.forceLink(edges.map((e) => ({
        id: e.id,
        target: e.target,
        source: e.source
      }))
    )
      .id((d) => d.id)
      .distance(50))
    .force('collision', d3.forceCollide(10))
    .force('center', d3.forceCenter(width / 2, height / 2));

d3.timer(redraw);


function moved() {
  var pos = d3.mouse(this);
  mouseX = pos[0]; mouseY = pos[1];
}

function redraw() {
  var candidates = parseInt(candidatesInput.value);
  var minRadius  = parseInt(minRadiusInput.value);

  var coords = nodes.map(n => [n.x, n.y]);
  var hull = convexHull(coords);
  var triangles = new Delaunay(coords).triangulate()

  context.clearRect(0, 0, width, height);

  // convex hull
  context.beginPath();
  context.moveTo(hull[0][0], hull[0][1]);
  for (var i = 1, n = hull.length; i < n; i++) {
    context.lineTo(hull[i][0], hull[i][1]);
  }
  context.closePath();
  context.fillStyle = 'rgba(0,0,0,0.1)';
  context.fill();
  context.stroke();

  // triangulation
  for (var i = 0, n = triangles.length; i < n; i += 3) {
    drawTraingle(triangles[i], triangles[i + 1], triangles[i + 2]);
  }
  context.lineWidth = 1;
  context.strokeStyle = 'rgba(100,0,0,0.1)';
  context.stroke();

  // edges
  context.beginPath();
  for (var i = 0, n = edges.length; i < n; i++) drawEdge(edges[i]);
  context.strokeStyle = 'rgba(0,0,0,0.8)';
  context.lineWidth = 2;
  context.stroke();

  // nodes
  context.beginPath();
  for (var i = 0, n = nodes.length; i < n; i++) drawNode(nodes[i]);
  context.fillStyle = '#000';
  context.fill();
  context.strokeStyle = '#fff';
  context.stroke();

  circles = getLargestEmptyCircle(coords, triangles, candidates, minRadius);
  if (circles) {
    var closest = null, minDist = Infinity;
    for (var i = 0, len = circles.length; i < len; i++) {
      var circle = circles[i];
      var dx = mouseX - circle.center[0];
      var dy = mouseY - circle.center[1];
      var dist = dx * dx + dy * dy;
      if (dist < minDist) {
        minDist = dist;
        closest = circle;
      }
    }
    closest.closest = true;
  }
  circles.forEach(drawCircle);
}

function drawNode(site) {
  context.moveTo(site.x + nodeSize, site.y);
  context.arc(site.x, site.y, nodeSize, 0, 2 * Math.PI, false);
}

function drawCircle({ radius, center, closest }) {
  var [cx, cy] = center;
  context.fillStyle = closest ? 'rgba(100,0,0,0.1)' : 'rgba(0,100,0,0.1)';
  context.moveTo(cx, cy);
  context.beginPath();
  context.arc(cx, cy, radius, 0, 2 * Math.PI, false);
  context.fill();
  context.stroke();
}

function drawEdge(edge) {
  var source = nodes[edge.source], target = nodes[edge.target];
  context.moveTo(source.x, source.y);
  context.lineTo(target.x, target.y);
}

function drawLink(link) {
  context.moveTo(link.source.x, link.source.y);
  context.lineTo(link.target.x, link.target.y);
}

function drawTraingle(a, b, c) {
  context.moveTo(a[0], a[1]);
  context.lineTo(b[0], b[1]);
  context.lineTo(c[0], c[1]);
}

function drawCell(cell) {
  if (!cell) return false;
  context.moveTo(cell[0][0], cell[0][1]);
  for (var j = 1, m = cell.length; j < m; ++j) {
    context.lineTo(cell[j][0], cell[j][1]);
  }
  context.closePath();
  return true;
}

function getAdjacentNodes(node) {
  return adjacencyTable[node.id].map(id => idMap[id]);
}


function collapseFlowerNodes(interConnectGroups = false) {
  var node, result = [];
  var visited = {}, stored = {}, isLeaf = {}; // lookup

  // BFS to find flower-nodes
  var queue = [nodes[0]];
  while (node = queue.shift()) {
    if (!visited[node.id]) {
      var adjacent = getAdjacentNodes(node);
      if (adjacent.length === 1 && node.id !== 0) { // leaf node found
        isLeaf[node.id] = true;

        // store its parent
        var parent = adjacent[0];
        if (!stored[parent.id]) {
          result.push(parent);
          stored[parent.id] = true;
        }
      } else queue.push.apply(queue, adjacent);
      visited[node.id] = true;
    }
  }


  if (interConnectGroups) {
    result.forEach((r, i) => {
      if (i > 0 && i < result.length - 1) {
        edges.push({
          id: counter++,
          source: r.id,
          target: result[i - 1].id
        }, {
          id: counter++,
          source: r.id,
          target: result[i + 1].id
        });
      }
    });
  }

  // collapse flower-nodes
  result.forEach(function (n) {
    var leafs = getAdjacentNodes(n)
      .filter(function(a) { return isLeaf[a.id]; });

    leafs.forEach(l => {
      l.hidden = true;
      l.parent = n;
    });

    n.children = leafs;
  });
}


function triangulate(nodes) {
  var triangulation = new Delaunay(nodes).triangulate();
  var triangles = new Array(triangulation.length / 3);
  var count = 0;
  for (var i = 0, len = triangulation.length; i < len; i += 3) {
    triangles[count++] = [
      triangulation[i],
      triangulation[i + 1],
      triangulation[i + 2]
    ];
  }
  return triangles;
}


function getLargestEmptyCircle(nodes, triangles, n = 1, minRadius = 0) {
  //var triangles = new Delaunay(nodes).triangulate();
  var convexhull = convexHull(nodes);
  var candidates = [], radii = {}, t, c;
  for (var i = 0, len = triangles.length; i < len; i += 3) {
    c = getCircumcenter(triangles[i], triangles[i + 1], triangles[i + 2]);
    if (inside(convexhull, c)) {
      candidates.push(i);
      radii[i] = circumcircleRadiusSquared(triangles[i], triangles[i + 1], triangles[i + 2]);
    }
  }
  candidates.sort((a, b) => radii[a] - radii[b]);

  var max = candidates[0], r;
  var maxR = circumcircleRadiusSquared(triangles[max], triangles[max + 1], triangles[max + 2]);
  var circles = [];
  var minRadiusSquared = minRadius * minRadius;

  for (var i = 0, len = candidates.length; i < len; i++) {
    t = candidates[i];
    r = circumcircleRadiusSquared(triangles[t], triangles[t + 1], triangles[t + 2]);
    if (r > maxR && r > minRadiusSquared) {
      max = t;
      maxR = r;
      circles.push(max);
      if (circles.length > n) circles.shift();
    }
  }
  return circles.map((c) => makeCircle(triangles[c], triangles[c + 1], triangles[c + 2]));
}


function makeCircle(a, b, c) {
  var center = getCircumcenter(a, b, c);
  var radius = [a, b, c].reduce((rmax, pt) => {
    var dx = pt[0] - center[0];
    var dy = pt[1] - center[1];
    var r = Math.sqrt(dx * dx + dy * dy) - nodeSize;
    return r > rmax ? r : rmax;
  }, 0);
  return { center, radius };
}


function circumcircleRadiusSquared(a, b, c) {
  var [cx, cy] = getCircumcenter(a, b, c);
  var [vx, vy] = a;
  var dx = cx - vx - nodeSize;
  var dy = cy - vy - nodeSize;
  return dx * dx + dy * dy - nodeSize * nodeSize;
}


function getCircumcenter(a, b, c) {
  // determine midpoints (average of x & y coordinates)
  var midAB = [(a[0] + b[0]) / 2, (a[1] + b[1]) / 2];
  var midBC = [(b[0] + c[0]) / 2, (b[1] + c[1]) / 2];

  // determine slope
  // we need the negative reciprocal of the slope to get
  // the slope of the perpendicular bisector
  var slopeAB = -1 / ((b[1] - a[1]) / (b[0] - a[0]));
  var slopeBC = -1 / ((c[1] - b[1]) / (c[0] - b[0]));

    // y = mx + b
    // solve for b
  var bAB = midAB[1] - slopeAB * midAB[0];
  var bBC = midBC[1] - slopeBC * midBC[0];

    // solve for x & y
    // x = (b1 - b2) / (m2 - m1)
  var x = (bAB - bBC) / (slopeBC - slopeAB);
  return [x, (slopeAB * x) + bAB];
}


/* convex hull code from d3 ***************************************************/
function crossProduct (a, b, c) {
  return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
}


function lexicographicOrder(a, b) {
  return a[0] - b[0] || a[1] - b[1];
}

// Computes the upper convex hull per the monotone chain algorithm.
// Assumes points.length >= 3, is sorted by x, unique in y.
// Returns an array of indices into points in left-to-right order.
function computeUpperHullIndexes(points) {
  var n = points.length,
      indexes = [0, 1],
      size = 2, cp;

  for (var i = 2; i < n; i++) {
    while (size > 1 && crossProduct(
        points[indexes[size - 2]],
        points[indexes[size - 1]],
        points[i]
      ) <= 0) --size;
    indexes[size++] = i;
  }

  return indexes.slice(0, size); // remove popped points
}

function convexHull(points) {
  var n = points.length;
  if (n < 3) return null;

  var sortedPoints  = new Array(n);
  var flippedPoints = new Array(n);

  for (i = 0; i < n; i++) sortedPoints[i] = [+points[i][0], +points[i][1], i];
  sortedPoints.sort(lexicographicOrder);
  for (i = 0; i < n; i++) flippedPoints[i] = [sortedPoints[i][0], -sortedPoints[i][1]];

  var upperIndexes = computeUpperHullIndexes(sortedPoints),
      lowerIndexes = computeUpperHullIndexes(flippedPoints);

  // Construct the hull polygon, removing possible duplicate endpoints.
  var skipLeft = lowerIndexes[0] === upperIndexes[0],
      skipRight = lowerIndexes[lowerIndexes.length - 1] === upperIndexes[upperIndexes.length - 1],
      hull = [];

  // Add upper hull in right-to-l order.
  // Then add lower hull in left-to-right order.
  for (i = upperIndexes.length - 1; i >= 0; --i) hull.push(points[sortedPoints[upperIndexes[i]][2]]);
  for (i = +skipLeft; i < lowerIndexes.length - skipRight; i++) hull.push(points[sortedPoints[lowerIndexes[i]][2]]);

  return hull;
}


function inside(polygon, point) {
  var n = polygon.length;
  var p = polygon[n - 1];
  var [x, y] = point;
  var [x0, y0] = p;
  var x1, y1;
  var inside = false;

  for (var i = 0; i < n; i++) {
    p = polygon[i], x1 = p[0], y1 = p[1];
    if (((y1 > y) !== (y0 > y)) && (x < (x0 - x1) * (y - y1) / (y0 - y1) + x1)) inside = !inside;
    x0 = x1, y0 = y1;
  }

  return inside;
}

function lineIntersectsCircle([ax, ay], [bx, by], [cx, cy], r) {
  ax -= cx; bx -= cx;
  ay -= cy; by -= cy;

  var dx = bx - ax;
  var dy = by - ay;
  var drSquared = dx * dx + dy * dy;
  var D = ax * by - bx * ay;

  return r * r * drSquared > D * D;
}

## preview.png

      
    Raw
  

              preview.png
            
          
## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!doctype html>
	<html>
	<head>
	<title>Largest empty circle</title>
	<script src="https://unpkg.com/d3@4.4.1"></script>
	<script src="https://unpkg.com/faster-delaunay@1.0.0"></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;
	font-size: 13px;
	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;
	}

	.control div {
	margin-top: 5px;
	}

	</style>
	</head>
	<body>
	<canvas id="canvas"></canvas>
	<form class="control" id="params">
	<div>
	<label>
	<input type="number" id="candidates" value="15"> Candidates</label>
	</div>
	<div>
	<label>
	<input type="number" id="minRadius" value="0"> R<sub>min</sub></label>
	</div>
	</form>
	<script src="index.js"></script>
	</body>
	</html>
	const h = document.documentElement.clientHeight;
	const w = document.documentElement.clientWidth;

	var canvas = d3.select('canvas').on('mousemove', moved).node();
	var context = canvas.getContext('2d');

	var candidatesInput = document.getElementById('candidates');
	var minRadiusInput = document.getElementById('minRadius');

	var pxRatio = window.devicePixelRatio;

	var width = w * pxRatio;
	var height = h * pxRatio;
	var nodeSize = 7.5;
	var counter = 0;

	canvas.width = width; canvas.height = height;
	canvas.style.width = w + 'px';
	canvas.style.height = h + 'px';

	function generateDenseTree(N = 150) {
	return {
	nodes: new Array(N).fill(0).map(function(_, i) {
	counter++;
	return {
	id: i,
	text: 'Node #' + i,
	x: Math.random() * width,
	y: Math.random() * height
	};
	}),
	edges: new Array(N - 1).fill(0).map(function(_, i) {
	counter++;
	return {
	id: i,
	source: Math.floor(Math.sqrt(i)),
	target: i + 1
	};
	})
	};
	}

	var { nodes, edges } = generateDenseTree();
	var circles;
	var idMap = nodes.reduce((map, node) => {
	map[node.id] = node;
	return map;
	}, {});

	var adjacencyTable = edges.reduce((acc, edge) => {
	var { source, target } = edge;
	acc[source] = acc[source] \|\| [];
	if (acc[source].indexOf(target) === -1)acc[source].push(target);

	acc[target] = acc[target] \|\| [];
	if (acc[target].indexOf(source) === -1) acc[target].push(source);
	return acc;
	}, {});

	var mouseX = 0, mouseY = 0;

	collapseFlowerNodes(false)

	redraw();

	var simulation = d3.forceSimulation(nodes)
	.force('charge', d3.forceManyBody())
	.force('link', d3.forceLink(edges.map((e) => ({
	id: e.id,
	target: e.target,
	source: e.source
	}))
	)
	.id((d) => d.id)
	.distance(50))
	.force('collision', d3.forceCollide(10))
	.force('center', d3.forceCenter(width / 2, height / 2));

	d3.timer(redraw);


	function moved() {
	var pos = d3.mouse(this);
	mouseX = pos[0]; mouseY = pos[1];
	}

	function redraw() {
	var candidates = parseInt(candidatesInput.value);
	var minRadius = parseInt(minRadiusInput.value);

	var coords = nodes.map(n => [n.x, n.y]);
	var hull = convexHull(coords);
	var triangles = new Delaunay(coords).triangulate()

	context.clearRect(0, 0, width, height);

	// convex hull
	context.beginPath();
	context.moveTo(hull[0][0], hull[0][1]);
	for (var i = 1, n = hull.length; i < n; i++) {
	context.lineTo(hull[i][0], hull[i][1]);
	}
	context.closePath();
	context.fillStyle = 'rgba(0,0,0,0.1)';
	context.fill();
	context.stroke();

	// triangulation
	for (var i = 0, n = triangles.length; i < n; i += 3) {
	drawTraingle(triangles[i], triangles[i + 1], triangles[i + 2]);
	}
	context.lineWidth = 1;
	context.strokeStyle = 'rgba(100,0,0,0.1)';
	context.stroke();

	// edges
	context.beginPath();
	for (var i = 0, n = edges.length; i < n; i++) drawEdge(edges[i]);
	context.strokeStyle = 'rgba(0,0,0,0.8)';
	context.lineWidth = 2;
	context.stroke();

	// nodes
	context.beginPath();
	for (var i = 0, n = nodes.length; i < n; i++) drawNode(nodes[i]);
	context.fillStyle = '#000';
	context.fill();
	context.strokeStyle = '#fff';
	context.stroke();

	circles = getLargestEmptyCircle(coords, triangles, candidates, minRadius);
	if (circles) {
	var closest = null, minDist = Infinity;
	for (var i = 0, len = circles.length; i < len; i++) {
	var circle = circles[i];
	var dx = mouseX - circle.center[0];
	var dy = mouseY - circle.center[1];
	var dist = dx * dx + dy * dy;
	if (dist < minDist) {
	minDist = dist;
	closest = circle;
	}
	}
	closest.closest = true;
	}
	circles.forEach(drawCircle);
	}

	function drawNode(site) {
	context.moveTo(site.x + nodeSize, site.y);
	context.arc(site.x, site.y, nodeSize, 0, 2 * Math.PI, false);
	}

	function drawCircle({ radius, center, closest }) {
	var [cx, cy] = center;
	context.fillStyle = closest ? 'rgba(100,0,0,0.1)' : 'rgba(0,100,0,0.1)';
	context.moveTo(cx, cy);
	context.beginPath();
	context.arc(cx, cy, radius, 0, 2 * Math.PI, false);
	context.fill();
	context.stroke();
	}

	function drawEdge(edge) {
	var source = nodes[edge.source], target = nodes[edge.target];
	context.moveTo(source.x, source.y);
	context.lineTo(target.x, target.y);
	}

	function drawLink(link) {
	context.moveTo(link.source.x, link.source.y);
	context.lineTo(link.target.x, link.target.y);
	}

	function drawTraingle(a, b, c) {
	context.moveTo(a[0], a[1]);
	context.lineTo(b[0], b[1]);
	context.lineTo(c[0], c[1]);
	}

	function drawCell(cell) {
	if (!cell) return false;
	context.moveTo(cell[0][0], cell[0][1]);
	for (var j = 1, m = cell.length; j < m; ++j) {
	context.lineTo(cell[j][0], cell[j][1]);
	}
	context.closePath();
	return true;
	}

	function getAdjacentNodes(node) {
	return adjacencyTable[node.id].map(id => idMap[id]);
	}


	function collapseFlowerNodes(interConnectGroups = false) {
	var node, result = [];
	var visited = {}, stored = {}, isLeaf = {}; // lookup

	// BFS to find flower-nodes
	var queue = [nodes[0]];
	while (node = queue.shift()) {
	if (!visited[node.id]) {
	var adjacent = getAdjacentNodes(node);
	if (adjacent.length === 1 && node.id !== 0) { // leaf node found
	isLeaf[node.id] = true;

	// store its parent
	var parent = adjacent[0];
	if (!stored[parent.id]) {
	result.push(parent);
	stored[parent.id] = true;
	}
	} else queue.push.apply(queue, adjacent);
	visited[node.id] = true;
	}
	}


	if (interConnectGroups) {
	result.forEach((r, i) => {
	if (i > 0 && i < result.length - 1) {
	edges.push({
	id: counter++,
	source: r.id,
	target: result[i - 1].id
	}, {
	id: counter++,
	source: r.id,
	target: result[i + 1].id
	});
	}
	});
	}

	// collapse flower-nodes
	result.forEach(function (n) {
	var leafs = getAdjacentNodes(n)
	.filter(function(a) { return isLeaf[a.id]; });

	leafs.forEach(l => {
	l.hidden = true;
	l.parent = n;
	});

	n.children = leafs;
	});
	}


	function triangulate(nodes) {
	var triangulation = new Delaunay(nodes).triangulate();
	var triangles = new Array(triangulation.length / 3);
	var count = 0;
	for (var i = 0, len = triangulation.length; i < len; i += 3) {
	triangles[count++] = [
	triangulation[i],
	triangulation[i + 1],
	triangulation[i + 2]
	];
	}
	return triangles;
	}


	function getLargestEmptyCircle(nodes, triangles, n = 1, minRadius = 0) {
	//var triangles = new Delaunay(nodes).triangulate();
	var convexhull = convexHull(nodes);
	var candidates = [], radii = {}, t, c;
	for (var i = 0, len = triangles.length; i < len; i += 3) {
	c = getCircumcenter(triangles[i], triangles[i + 1], triangles[i + 2]);
	if (inside(convexhull, c)) {
	candidates.push(i);
	radii[i] = circumcircleRadiusSquared(triangles[i], triangles[i + 1], triangles[i + 2]);
	}
	}
	candidates.sort((a, b) => radii[a] - radii[b]);

	var max = candidates[0], r;
	var maxR = circumcircleRadiusSquared(triangles[max], triangles[max + 1], triangles[max + 2]);
	var circles = [];
	var minRadiusSquared = minRadius * minRadius;

	for (var i = 0, len = candidates.length; i < len; i++) {
	t = candidates[i];
	r = circumcircleRadiusSquared(triangles[t], triangles[t + 1], triangles[t + 2]);
	if (r > maxR && r > minRadiusSquared) {
	max = t;
	maxR = r;
	circles.push(max);
	if (circles.length > n) circles.shift();
	}
	}
	return circles.map((c) => makeCircle(triangles[c], triangles[c + 1], triangles[c + 2]));
	}


	function makeCircle(a, b, c) {
	var center = getCircumcenter(a, b, c);
	var radius = [a, b, c].reduce((rmax, pt) => {
	var dx = pt[0] - center[0];
	var dy = pt[1] - center[1];
	var r = Math.sqrt(dx * dx + dy * dy) - nodeSize;
	return r > rmax ? r : rmax;
	}, 0);
	return { center, radius };
	}


	function circumcircleRadiusSquared(a, b, c) {
	var [cx, cy] = getCircumcenter(a, b, c);
	var [vx, vy] = a;
	var dx = cx - vx - nodeSize;
	var dy = cy - vy - nodeSize;
	return dx * dx + dy * dy - nodeSize * nodeSize;
	}


	function getCircumcenter(a, b, c) {
	// determine midpoints (average of x & y coordinates)
	var midAB = [(a[0] + b[0]) / 2, (a[1] + b[1]) / 2];
	var midBC = [(b[0] + c[0]) / 2, (b[1] + c[1]) / 2];

	// determine slope
	// we need the negative reciprocal of the slope to get
	// the slope of the perpendicular bisector
	var slopeAB = -1 / ((b[1] - a[1]) / (b[0] - a[0]));
	var slopeBC = -1 / ((c[1] - b[1]) / (c[0] - b[0]));

	// y = mx + b
	// solve for b
	var bAB = midAB[1] - slopeAB * midAB[0];
	var bBC = midBC[1] - slopeBC * midBC[0];

	// solve for x & y
	// x = (b1 - b2) / (m2 - m1)
	var x = (bAB - bBC) / (slopeBC - slopeAB);
	return [x, (slopeAB * x) + bAB];
	}


	/* convex hull code from d3 ***************************************************/
	function crossProduct (a, b, c) {
	return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
	}


	function lexicographicOrder(a, b) {
	return a[0] - b[0] \|\| a[1] - b[1];
	}

	// Computes the upper convex hull per the monotone chain algorithm.
	// Assumes points.length >= 3, is sorted by x, unique in y.
	// Returns an array of indices into points in left-to-right order.
	function computeUpperHullIndexes(points) {
	var n = points.length,
	indexes = [0, 1],
	size = 2, cp;

	for (var i = 2; i < n; i++) {
	while (size > 1 && crossProduct(
	points[indexes[size - 2]],
	points[indexes[size - 1]],
	points[i]
	) <= 0) --size;
	indexes[size++] = i;
	}

	return indexes.slice(0, size); // remove popped points
	}

	function convexHull(points) {
	var n = points.length;
	if (n < 3) return null;

	var sortedPoints = new Array(n);
	var flippedPoints = new Array(n);

	for (i = 0; i < n; i++) sortedPoints[i] = [+points[i][0], +points[i][1], i];
	sortedPoints.sort(lexicographicOrder);
	for (i = 0; i < n; i++) flippedPoints[i] = [sortedPoints[i][0], -sortedPoints[i][1]];

	var upperIndexes = computeUpperHullIndexes(sortedPoints),
	lowerIndexes = computeUpperHullIndexes(flippedPoints);

	// Construct the hull polygon, removing possible duplicate endpoints.
	var skipLeft = lowerIndexes[0] === upperIndexes[0],
	skipRight = lowerIndexes[lowerIndexes.length - 1] === upperIndexes[upperIndexes.length - 1],
	hull = [];

	// Add upper hull in right-to-l order.
	// Then add lower hull in left-to-right order.
	for (i = upperIndexes.length - 1; i >= 0; --i) hull.push(points[sortedPoints[upperIndexes[i]][2]]);
	for (i = +skipLeft; i < lowerIndexes.length - skipRight; i++) hull.push(points[sortedPoints[lowerIndexes[i]][2]]);

	return hull;
	}


	function inside(polygon, point) {
	var n = polygon.length;
	var p = polygon[n - 1];
	var [x, y] = point;
	var [x0, y0] = p;
	var x1, y1;
	var inside = false;

	for (var i = 0; i < n; i++) {
	p = polygon[i], x1 = p[0], y1 = p[1];
	if (((y1 > y) !== (y0 > y)) && (x < (x0 - x1) * (y - y1) / (y0 - y1) + x1)) inside = !inside;
	x0 = x1, y0 = y1;
	}

	return inside;
	}

	function lineIntersectsCircle([ax, ay], [bx, by], [cx, cy], r) {
	ax -= cx; bx -= cx;
	ay -= cy; by -= cy;

	var dx = bx - ax;
	var dy = by - ay;
	var drSquared = dx * dx + dy * dy;
	var D = ax * by - bx * ay;

	return r * r * drSquared > D * D;
	}