const h = document.documentElement.clientHeight;
const w = h;

const deg2rad = Math.PI / 180;

const color = d3.interpolateRgb('steelblue', 'brown');

// 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');

let circles, texts;

var C   = [ 0, 0];
var N   = 40;
var GAP = 2;
var R;
var sizes, angles;
var X   = [];
var Y   = [];


// render nodes
function render () {
  circles
    .attr('cx', (d, i) => X[i])
    .attr('cy', (d, i) => Y[i])
    .attr('r',  (d) => d)
    .attr('fill', (d, i) => color(i / N));

  texts
    .attr('dx', (d, i) => X[i] - (i < 10 ? 3 : 6))
    .attr('dy', (d, i) => Y[i] + 4)
    .text((d, i) => i);
}


/**
 * Sort points clockwise around a center point
 * @param  {number} ax
 * @param  {number} ay
 * @param  {number} bx
 * @param  {number} by
 * @param  {number} cx
 * @param  {number} cy
 * @return {number}
 */
function compare (ax, ay, bx, by, cx, cy) {
  if (ax - cx >= 0  && bx - cx < 0)  return  1;
  if (ax - cx < 0   && bx - cx >= 0) return -1;
  if (ax - cx === 0 && bx - cx === 0) {
    return (ay - by >= 0 || by - cy >= 0) ? (ay - by) : (by - ay);
  }

  // compute the cross product of vectors (center -> a) x (center -> b)
  var det = (ax - cx) * (by - cy) - (bx - cx) * (ay - cy);
  if (det < 0) return  1;
  if (det > 0) return -1;

  // points a and b are on the same line from the center
  // check which point is closer to the center
  var d1 = (ax - cx) * (ax - cx) + (ay - cy) * (ay - cy);
  var d2 = (bx - cx) * (bx - cx) + (by - cy) * (by - cy);

  return d1 - d2;
}


function crossProduct (ax, ay, bx, by, cx, cy) {
  // compute the cross product of vectors (center -> a) x (center -> b)
  var det = (ax - cx) * (by - cy) - (bx - cx) * (ay - cy);
  if (det < 0) return  1;
  if (det > 0) return -1;
  return 0; // same dir
}

function dotProduct (ax, ay, bx, by, cx, cy) {
  return (ax - cx) * (bx - cx) + (ay - cy) * (by - cy);
}

function distance (ax, ay, bx, by) {
  var dx = ax - bx;
  var dy = ay - by;
  return Math.sqrt(dx * dx + dy * dy);
}

/**
  * Intersection point of 2 circles
  *
  * http://paulbourke.net/geometry/circlesphere/
  *
  * @param  {number} x0
  * @param  {number} y0
  * @param  {number} r0
  * @param  {number} x1
  * @param  {number} y1
  * @param  {number} r1
  * @return {null|Array.<Array.<number>>}
  */
function circleCircleIntersection (x0, y0, r0, x1, y1, r1) {
  let a, dx, dy, d, h, rx, ry;
  let x2, y2;

  // dx and dy are the vertical and horizontal distances between
  // the circle centers.
  dx = x1 - x0;
  dy = y1 - y0;

  // Determine the straight-line distance between the centers. */
  d = Math.sqrt(dx * dx + dy * dy);

  // no solution. circles do not intersect.
  if (d > (r0 + r1))         return null;
  // no solution. one circle is contained in the other
  if (d < Math.abs(r0 - r1)) return null;

  // 'point 2' is the point where the line through the circle
  // intersection points crosses the line between the circle
  // centers.

  // Determine the distance from point 0 to point 2.
  a = ((r0 * r0) - (r1 * r1) + (d * d)) / (2 * d);

  // Determine the coordinates of point 2.
  x2 = x0 + (dx * a / d);
  y2 = y0 + (dy * a / d);

  // Determine the distance from point 2 to either of the
  // intersection points.
  h = Math.sqrt((r0 * r0) - (a * a));

  // Now determine the offsets of the intersection points from point 2.
  rx = -dy * (h / d);
  ry =  dx * (h / d);

  // Determine the absolute intersection points
  return [
    [x2 + rx, y2 + ry],
    [x2 - rx, y2 - ry]
  ];
}


/**
 * Get arch length of a bigger circle, spanned by the radius of a smaller one
 * @param  {number} r
 * @param  {number} R
 * @return {number}
 */
function chordToArcLength(r, R) {
  var halfr = r / 2;
  var h = R - Math.sqrt(R * R - (r * r) / 4); // arc height
  var l = Math.sqrt(h * h + (r * r) / 4);
  var L = r;

  // Huygens formula
  return 2 * l + (1 / 3) * (2 * l - L);
}


function relax ({ X, Y, sizes, indexes, R, N, center, gap = 0 }) {
  N = indexes.length;
  const SWEEP_MAX = 10;

  let I      = N * 2; // ensure 2 sweeps
  let cx     = center[0],
      cy     = center[1];

  // special cases
  if (N === 1) return; // obviously
  if (N === 2) { // just move them apart, if possible
    var a = indexes[0];
    var b = indexes[1];
    var ax = X[a], ay = Y[a], as = sizes[a];
    var bx = X[b], by = Y[b], bs = sizes[b];
    var minDist = chordToArcLength(as,  R) +
                  chordToArcLength(bs,  R) + gap;

    var dist = distance(ax, ay, bx, by);
    var arcLength = chordToArcLength(dist, R);
    if (arcLength < minDist) {
      var angle = minDist / R;
      var dx = ax - cx,
          dy = ay - cy;

      var sin = Math.sin(angle),
          cos = Math.cos(angle);

      dx = dx * cos - dy * sin;
      dy = dx * sin + dy * cos;

      X[b] = cx + dx;
      Y[b] = cy + dy;
    }
    return;
  }

  let sorted = indexes.sort((a, b) => {
    return compare(X[a], Y[a], X[b], Y[b], cx, cy);
  });

  let start = sorted[N - 1];
  let x0 = X[start], y0 = Y[start]; // fix start point

  let hop = false;

  for (var i = -1; i < I - 1; i++) {
    var a = i % N, b  = (i + 1) % N;
    if (i === -1) {
      a = 0;
      b = N - 1;
    }
    a = sorted[a];
    b = sorted[b];

    var ax = X[a],     ay = Y[a];
    var bx = X[b],     by = Y[b];
    var as = sizes[a], bs = sizes[b];

    var minDist = as + bs + gap;
    var shift   = minDist - distance(ax, ay, bx, by);
    var dir     = compare(ax, ay, bx, by, cx, cy);

    if (dir === -1 && hop) dir = 1;

    // if order was broken or distance is too small
    if (dir === 1 || shift > 1e-3) {
      var shifted = circleCircleIntersection(cx, cy, R, ax, ay, minDist);
      if (shifted) {
        var target  = shifted[0];


        hop = (bx > cx && target[0] < cx); // 0 degrees hop

        bx = X[b] = target[0];
        by = Y[b] = target[1];
      }
    } else {
      hop = false;
    }

    // render ();
    // debugger;

    if (i % N === N - 2) {
      var last = N - 1;
      // only I and IV quaters of the circle, crossed the sorting 0 angle
      if (Y[sorted[last]] > cy && Y[sorted[0]] > cy &&
          X[sorted[last]] - sizes[sorted[last]] < X[sorted[0]] + sizes[sorted[0]]) {
        var x = 0;
        I = Math.min(N * SWEEP_MAX, I + N);
        while (Y[sorted[last]] > cy && Y[sorted[0]] > cy &&
            X[sorted[last]] < X[sorted[0]] && ++x < N) {
          sorted.unshift(sorted.pop());
        }
      }
    }
  }

  // rotate the whole circle back to compensate the shift
  var ax = x0       - cx, ay = y0       - cy,
      bx = X[start] - cx, by = Y[start] - cy;

  // can be NaN if the vector didn't move
  var theta = ax === bx ? 0 : Math.abs(Math.acos(
    (ax * bx + ay * by) /
    (Math.sqrt(ax * ax + ay * ay) * Math.sqrt(bx * bx + by * by))
  ));

  if (theta !== 0) {
    var sin = Math.sin(-theta);
    var cos = Math.cos(-theta);
    var x, y, index;

    for (var i = 0; i < N; i++) {
      index = sorted[i];
      // translate point back to origin:
      x = X[index] - cx;
      y = Y[index] - cy;

      // rotate and translate back
      X[index] = (x * cos - y * sin) + cx;
      Y[index] = (x * sin + y * cos) + cy;
    }
  }
}

function rotate (angle) {
  angle = angle * Math.PI / 180;
  var cx = C[0], cy = C[1];
  var sin = Math.sin(angle);
  var cos = Math.cos(angle);
  var x, y;

  for (var i = 0; i < N; i++) {
    index = indexes[i];
    // translate point back to origin:
    x = X[index] - cx;
    y = Y[index] - cy;

    // rotate and translate back
    X[index] = (x * cos - y * sin) + cx;
    Y[index] = (x * sin + y * cos) + cy;
  }

  render();
}

function generate () {
  N      = parseInt(document.querySelector('#n').value);
  sizes  = new Array(N).fill(20).map(m => m - Math.random() * m);
  angles = new Array(N).fill(359).map(a => (0 + a * Math.random()) % 360);

  GAP    = parseInt(document.querySelector('#gap').value);
  R      = Math.min(h / 2, Math.max(20, (sizes.reduce((a, b) => a + b * 2, 0) + GAP  * (sizes.length - 1)) / (2 * Math.PI)));

  console.log(R);

  angles.forEach((a, i) => {
    X[i] = C[0] + R * Math.sin(a * deg2rad);
    Y[i] = C[1] - R * Math.cos(a * deg2rad);
  });

  // 3 nodes example
  // N = 3;
  // X = [22.021999176858913, 16.793700989603053, 17.036710556863795];
  // Y = [79.80257238118364, 97.05521471469118, 92.39301694600297];
  // C = [45.01420575034524, 96.18873037068559];
  // R = distance(X[0], Y[0], C[0], C[1]);
  // sizes = [12,12,12];

  // 3 nodes example
  // X = [-27.977495193481445, -22.992206573486328, -28.220504760742188];
  // Y = [-3.795713424682617, -16.386157989501953, 0.8664843440055847];
  // C = [0, 0];
  // R = distance(X[0], Y[0], C[0], C[1]);
  // sizes = [5, 5, 5];

  // double sweep example
  // N = 21;
  // X = [-99.6483154296875, -95.16764068603516, -90.74275970458984, -85.27777099609375, -107.66104888916016, -104.49362182617188, -101.25088500976562, -96.01097869873047, -77.29906463623047, -110.34211730957031, -106.17959594726562, -112.3492202758789, -84.74922943115234, -109.85372161865234, -111.34769439697266, -113.35269927978516, -113.55818176269531, -81.09383392333984, -112.11846923828125, -113.39584350585938, -113.6285629272461];
  // Y = [-54.62138748168945, -62.09994888305664, -68.40348052978516, -75.10649108886719, -36.36457061767578, -44.658329010009766, -51.59013366699219, -60.78795623779297, -83.29548645019531, -27.164316177368164, -40.48675537109375, -17.056873321533203, -75.70238494873047, -29.076515197753906, 22.693044662475586, -8.028022766113281, 4.221722602844238, -79.60574340820312, -18.51302146911621, -7.393646717071533, 1.3537389039993286];
  // sizes = [12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12];
  // C = [0, 0];
  // R = distance(X[0], Y[0], C[0], C[1]);


  svg.selectAll('circle').remove();
  svg.selectAll('text').remove();

  circles = svg.selectAll('circle')
    .data(sizes)
    .enter()
    .append('circle');

  svg
    .append('circle')
    .attr('class', 'center')
    .attr('cx', C[0]).attr('cy', C[1])
    .attr('r', 2);

  svg
    .append('circle')
    .attr('class', 'general')
    .attr('cx', C[0]).attr('cy', C[1])
    .attr('stroke-dasharray', '2, 4')
    .attr('r', R);

  texts = svg.selectAll('text')
    .data(sizes)
    .enter()
    .append('text');

  render();
}

generate();

document.querySelector('#generate').addEventListener('click', generate, false);
document.querySelector('#relax').addEventListener('click', () => {
  GAP    = parseInt(document.querySelector('#gap').value)
  console.time('relax');
  relax({
    X, Y, sizes,
    indexes: window.indexes || sizes.map((s, i) => i),
    R, N, gap: GAP,
    center: C
  });
  console.timeEnd('relax');
  render();
}, false);