var π = Math.PI,
    size = 150,
    margin = 15,
    node_radius = 5;

function randPoint() {
  return [Math.floor(Math.random() * (size - 2 * margin) + margin), Math.floor(Math.random() * (size - 2 * margin) + margin)];
}

var stops = [
  [[10,10],[85,25],[130,15],[90,55],[60,40],[10,10]],
  [[15,20],[20,30],[100,50],[95,60],[105,40],[60,20]],
  [[10,30],[20,40],[30,30],[40,40],[50,30],[60,50]],
  [[49,89],[100,110],[38,69],[115,97],[114,57],[27,57],[96,28]],
  [[28,87],[31,100],[129,127],[135,80],[137,96],[97,128],[97,74],[59,82],[57,125]],
  [[60,63],[114,25],[129,36],[74,19],[47,100],[32,29],[72,74]],
  d3.range(12).map(randPoint),
  d3.range(11).map(randPoint),
  d3.range(10).map(randPoint),
  d3.range(9).map(randPoint),
  d3.range(8).map(randPoint),
  d3.range(7).map(randPoint),
  d3.range(6).map(randPoint),
  d3.range(5).map(randPoint),
  d3.range(4).map(randPoint),
];

var Itinerary = function() {
  var buffer,
      iterations = 10,
      r_opt = 0.25,
      r_max = 0.8,
      r_step = 0.1;

  var w = {
    edge_edge_intersection: 20,
    edge_node_intersection: 21,
    edge_pair_angle: 2,
    edge_ratio_dev: 3,
    edge_pair_ratio: 1,
  };

  var debug_intersect_tests;

  function itinerary(stops) {
    debug_intersect_tests = 0;

    var best_ratios = d3.range(stops.length - 1).map(function() {return r_opt;}),
        last_best_energy = 2e10,
        best_energy = 1e10,
        current_ratios,
        edges,
        energy;
    for (var l = 0; l < iterations; l++) {
      last_best_energy = best_energy;
      for (var e = 0; e < stops.length - 1; e++) {
        current_ratios = best_ratios.slice();
        for (var r = -r_max; r <= r_max; r += r_step) {
          current_ratios[e] = r;
          edges = getEdges(stops, current_ratios);
          energy = computeEnergy(edges);
          if (energy < best_energy) {
            best_ratios = current_ratios.slice();
            best_energy = energy;
          }
        }
      }
      if (last_best_energy == best_energy) {
        edges = getEdges(stops, best_ratios);
        computeEnergy(edges, true);
        break;
      }
    }
    return pathString(edges);
  }

  function getEdges(stops, ratios) {
    var edges = [];
    for (var i = 0; i < stops.length - 1; i++) {
      edges.push(edge(stops[i], stops[i+1], ratios[i]));
    }
    return edges;
  }

  function edge(s1, s2, ratio) {
    var xq = Math.round((s1[0] + s2[0]) / 2 + (s2[1] - s1[1]) * ratio),
        yq = Math.round((s1[1] + s2[1]) / 2 - (s2[0] - s1[0]) * ratio);
    return {x1: s1[0], y1: s1[1], xq: xq, yq: yq, x2: s2[0], y2: s2[1], r: ratio};
  }

  // computes energy of layout. optimal energy is 0.
  function computeEnergy(edges, debug) {

    var edge_pairs = [];
    for (var i = 0; i < edges.length - 1; i++) {
      edge_pairs.push([edges[i], edges[i+1]]);
    }
    if (edges[0].x1 == edges[edges.length - 1].x2 && edges[0].y1 == edges[edges.length - 1].y2) {
      edge_pairs.push([edges[edges.length - 1], edges[0]]);
    }

    energy = 0;

    // minimize number of edge/edge intersections
    edges.forEach(function(e1, i) {
      edges.forEach(function(e2, j) {
        if (j <= i) {return;}
        if (edgeEdgeIntersect(e1, e2)) {
          energy += w['edge_edge_intersection'];
        }
      });
    });

    // minimize number of edge/node intersections
    edges.forEach(function(e, i) {
      edges.forEach(function(e2, j) {
        if (j == i || j == i + 1) {return;} // don't test nodes on edge
        var node = {x: e2.x1, y: e2.y1};
        if (edgeNodeIntersect(e, node)) {
          energy += w['edge_node_intersection'];
        }
      });
    });

    // maximize sum of angles between edges at each node
    edge_pairs.forEach(function(sp, i) {
      var a1 = Math.atan2(sp[0].yq - sp[0].y2, sp[0].xq - sp[0].x2),
          a2 = Math.atan2(sp[1].yq - sp[1].y1, sp[1].xq - sp[1].x1),
          delta = π - Math.abs(π - Math.abs(a2 - a1));
      energy += w['edge_pair_angle'] * (π - delta);
    });

    // minimize ratio deviation from +/- optimal (r_opt)
    edges.forEach(function(e) {
      energy += w['edge_ratio_dev'] * Math.abs(Math.abs(e.r) - r_opt);
    });

    // minimize difference between consecutive edge ratios
    edge_pairs.forEach(function(sp) {
      energy += w['edge_pair_ratio'] * Math.abs(sp[0].r - sp[1].r);
    });
    return energy;
  }

  function bez(v1, v2, v3, t) {
    return (1-t) * ((1-t) * v1 + t * v2) + t * ((1 - t) * v2 + t * v3);
  }

  // edgeEdgeIntersect: test whether an edge intersects with another edge
  function edgeEdgeIntersect(e1, e2) {
    // test if bounding boxes intersect.  If no, return false.
    // If both bounding boxes have area < 9px^2, return true if
    // intersection is not at endpoitns, else return false
    // Otherwise, return disjunction of intersection tests of half-edges
    var area_threshold = 9;
    debug_intersect_tests++;

    var e1x_min = Math.min(e1.x1, e1.xq, e1.x2),
        e1x_max = Math.max(e1.x1, e1.xq, e1.x2),
        e1y_min = Math.min(e1.y1, e1.yq, e1.y2),
        e1y_max = Math.max(e1.y1, e1.yq, e1.y2),

        e2x_min = Math.min(e2.x1, e2.xq, e2.x2),
        e2x_max = Math.max(e2.x1, e2.xq, e2.x2),
        e2y_min = Math.min(e2.y1, e2.yq, e2.y2),
        e2y_max = Math.max(e2.y1, e2.yq, e2.y2);

    var bb_intersect = (e1x_min < e2x_max && e1x_max > e2x_min &&
                        e1y_min < e2y_max && e1y_max > e2y_min);

    if (!bb_intersect) {return false;}

    if ((e1x_max - e1x_min) * (e1y_max - e1y_min) < area_threshold &&
        (e2x_max - e2x_min) * (e2y_max - e2y_min) < area_threshold) {
      if ((e1.x1 == e2.x1 && e1.y1 == e2.y1) || (e1.x1 == e2.x2 && e1.x1 == e2.y2) ||
          (e1.x2 == e2.x1 && e1.x2 == e2.y1) || (e1.x2 == e2.x2 && e1.x2 == e2.y2)) {
        return false;
      }
      return true;
    }

    var e11 = {
      x1: e1.x1, y1: e1.y1, xq: (e1.x1 + e1.xq) / 2, yq: (e1.y1 + e1.yq) / 2,
      x2: (e1.x1 + 2 * e1.xq + e1.x2) / 4, y2: (e1.y1 + 2 * e1.yq + e1.y2) / 4
    };
    var e12 = {
      x1: (e1.x1 + 2 * e1.xq + e1.x2) / 4, y1: (e1.y1 + 2 * e1.yq + e1.y2) / 4,
      xq: (e1.x2 + e1.xq) / 2, yq: (e1.y2 + e1.yq) / 2, x2: e1.x2, y2: e1.y2
    };
    var e21 = {
      x1: e2.x1, y1: e2.y1, xq: (e2.x1 + e2.xq) / 2, yq: (e2.y1 + e2.yq) / 2,
      x2: (e2.x1 + 2 * e2.xq + e2.x2) / 4, y2: (e2.y1 + 2 * e2.yq + e2.y2) / 4
    };
    var e22 = {
      x1: (e2.x1 + 2 * e2.xq + e2.x2) / 4, y1: (e2.y1 + 2 * e2.yq + e2.y2) / 4,
      xq: (e2.x2 + e2.xq) / 2, yq: (e2.y2 + e2.yq) / 2, x2: e2.x2, y2: e2.y2
    };


    return (edgeEdgeIntersect(e11, e21) ||
            edgeEdgeIntersect(e11, e22) ||
            edgeEdgeIntersect(e12, e21) ||
            edgeEdgeIntersect(e12, e22));
  }

  // edgeNodeIntersect: test whether an edge intersects with a node
  function edgeNodeIntersect(edge, node) {
    var t1 = 0,
        t2 = 1,
        pt1x, pt1y,
        pt2x, pt2y,
        diff = 1,
        d1,
        d2;

    // compute d1 (distance from p(t1) to n), d2 (from p(t2) to n)
    // if d1 < d2, set t2 = (t1+t2)/2, else set t1 = (t1+t2)/2
    // repeat until p(t1) and p(t2) don't change

    pt1x = bez(edge.x1, edge.xq, edge.x2, t1);
    pt1y = bez(edge.y1, edge.yq, edge.y2, t1);
    pt2x = bez(edge.x1, edge.xq, edge.x2, t2);
    pt2y = bez(edge.y1, edge.yq, edge.y2, t2);

    while (diff > 0) {
      d1 = Math.pow(node.x - pt1x, 2) + Math.pow(node.y - pt1y, 2);
      d2 = Math.pow(node.x - pt2x, 2) + Math.pow(node.y - pt2y, 2);
      t_mid = (t1 + t2) / 2;
      if (d1 < d2) {
        t2 = t_mid;
        ox = pt2x;
        oy = pt2y;
        pt2x = bez(edge.x1, edge.xq, edge.x2, t2);
        pt2y = bez(edge.y1, edge.yq, edge.y2, t2);
        diff = Math.round(Math.abs(pt2x - ox) + Math.abs(pt2y - oy));
      } else {
        t1 = t_mid;
        ox = pt1x;
        oy = pt1y;
        pt1x = bez(edge.x1, edge.xq, edge.x2, t1);
        pt1y = bez(edge.y1, edge.yq, edge.y2, t1);
        diff = Math.round(Math.abs(pt1x - ox) + Math.abs(pt1y - oy));
      }
    }
    return d1 < Math.pow(node_radius + 2, 2) || d2 < Math.pow(node_radius + 2, 2);
  }

  function pathString(edges) {
    return edges.reduce(function(p, s) {
      if (p === '') {p = 'M' + s.x1 + ',' + s.y1;}
      return p + 'Q' + s.xq + ',' + s.yq + ',' + s.x2 + ',' + s.y2;
    }, '');
  }

  return itinerary;
};

var color = d3.scale.category10();

var itinerary = Itinerary();


var svg = d3.select('#container')
  .append('svg')
    .attr('width', 5 * size + 2 * margin)
    .attr('height', Math.ceil(stops.length/5) * size + 2 * margin);

var g = svg.selectAll('g').data(stops)
  .enter().append('g')
    .attr('transform', function(d, i, j) {return 'translate(' + (i % 5) * size + ',' + Math.floor(i / 5) * size + ')';});

g.selectAll('circle.stop').data(function(d) {return d;})
  .enter().append('circle')
    .attr('class', 'stop')
    .attr('cx', function(d) {return d[0];})
    .attr('cy', function(d) {return d[1];})
    .attr('fill', function(d, i, j) {return color(j);})
    .attr('r', node_radius);

g.append('path')
  .attr('d', function(d) {return itinerary(d);});

g.selectAll('circle.stop2').data(function(d) {return d;})
  .enter().append('circle')
    .attr('class', 'stop2')
    .attr('cx', function(d) {return d[0];})
    .attr('cy', function(d) {return d[1];})
    .attr('fill', function(d, i, j) {return color(j);})
    .attr('r', node_radius - 2);

/* Questions:
 * - How can you draw an SVG arrow?
 * - Can you ensure a certain amount of bend in an SVG line? (like tikz)
 */