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;
}