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


function relax ({ X, Y, sizes, indexes, R, N, center, gap }) {
  N = indexes.length;
  let I      = N;
  let cx     = center[0],
      cy     = center[1];
  let sorted = indexes.sort((a, b) => {
    return compare(X[a], Y[a], X[b], Y[b], cx, cy);
  });

  console.log(sorted, center, sorted.length, N);

  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);
      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 * 10, 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(30).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      = (sizes.reduce((a, b) => a + b * 2, 0) + GAP * 3 * (sizes.length - 1)) / (2 * Math.PI);

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

  // X = [
  //   75.82254791259766,
  //   43.08230972290039,
  //   26.89663314819336,
  //   19.295494079589844,
  //   21.451080322265625,
  //   33.03097915649414,
  //   52.24942398071289,
  //   76.14268493652344,
  //   101.02611541748047,
  //   123.0624008178711,
  //   138.85324096679688,
  //   145.96351623535156,
  //   143.2967071533203,
  //   131.2640838623047,
  //   111.72122955322266,
  //   100.71785736083984
  // ];
  // Y = [
  //   66.19557189941406,
  //   52.83225631713867,
  //   33.77907180786133,
  //   9.962634086608887,
  //   -14.944262504577637,
  //   -37.10065841674805,
  //   -53.08976364135742,
  //   -60.44585418701172,
  //   -58.03452682495117,
  //   -46.22765350341797,
  //   -26.845979690551758,
  //   -2.8784143924713135,
  //   21.97894287109375,
  //   43.89277267456055,
  //   59.48369216918945,
  //   63.91008758544922
  // ];
  // sizes = [
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10,
  //   10
  // ];
  // C = [
  //   82.56354522705078,
  //   2.8914947509765625
  // ];
  // R = 63.661979412695295;

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

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