"use strict";

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.circles = exports.cells = exports.beaches = void 0;
exports.default = Diagram;
exports.epsilon2 = exports.epsilon = exports.edges = void 0;

var _Beach = require("./Beach");

var _Cell = require("./Cell");

var _Circle = require("./Circle");

var _Edge = require("./Edge");

var _RedBlackTree = _interopRequireDefault(require("./RedBlackTree"));

function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }

var epsilon = 1e-6;
exports.epsilon = epsilon;
var epsilon2 = 1e-12;
exports.epsilon2 = epsilon2;
var beaches;
exports.beaches = beaches;
var cells;
exports.cells = cells;
var circles;
exports.circles = circles;
var edges;
exports.edges = edges;

function triangleArea(a, b, c) {
  return (a[0] - c[0]) * (b[1] - a[1]) - (a[0] - b[0]) * (c[1] - a[1]);
}

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

function Diagram(sites, extent) {
  var site = sites.sort(lexicographic).pop(),
      x,
      y,
      circle;
  exports.edges = edges = [];
  exports.cells = cells = new Array(sites.length);
  exports.beaches = beaches = new _RedBlackTree.default();
  exports.circles = circles = new _RedBlackTree.default();

  while (true) {
    circle = _Circle.firstCircle;

    if (site && (!circle || site[1] < circle.y || site[1] === circle.y && site[0] < circle.x)) {
      if (site[0] !== x || site[1] !== y) {
        (0, _Beach.addBeach)(site);
        x = site[0], y = site[1];
      }

      site = sites.pop();
    } else if (circle) {
      (0, _Beach.removeBeach)(circle.arc);
    } else {
      break;
    }
  }

  (0, _Cell.sortCellHalfedges)();

  if (extent) {
    var x0 = +extent[0][0],
        y0 = +extent[0][1],
        x1 = +extent[1][0],
        y1 = +extent[1][1];
    (0, _Edge.clipEdges)(x0, y0, x1, y1);
    (0, _Cell.clipCells)(x0, y0, x1, y1);
  }

  this.edges = edges;
  this.cells = cells;
  exports.beaches = beaches = exports.circles = circles = exports.edges = edges = exports.cells = cells = null;
}

Diagram.prototype = {
  constructor: Diagram,
  polygons: function () {
    var edges = this.edges;
    return this.cells.map(function (cell) {
      var polygon = cell.halfedges.map(function (i) {
        return (0, _Cell.cellHalfedgeStart)(cell, edges[i]);
      });
      polygon.data = cell.site.data;
      return polygon;
    });
  },
  triangles: function () {
    var triangles = [],
        edges = this.edges;
    this.cells.forEach(function (cell, i) {
      if (!(m = (halfedges = cell.halfedges).length)) return;
      var site = cell.site,
          halfedges,
          j = -1,
          m,
          s0,
          e1 = edges[halfedges[m - 1]],
          s1 = e1.left === site ? e1.right : e1.left;

      while (++j < m) {
        s0 = s1;
        e1 = edges[halfedges[j]];
        s1 = e1.left === site ? e1.right : e1.left;

        if (s0 && s1 && i < s0.index && i < s1.index && triangleArea(site, s0, s1) < 0) {
          triangles.push([site.data, s0.data, s1.data]);
        }
      }
    });
    return triangles;
  },
  links: function () {
    return this.edges.filter(function (edge) {
      return edge.right;
    }).map(function (edge) {
      return {
        source: edge.left.data,
        target: edge.right.data
      };
    });
  },
  find: function (x, y, radius) {
    var that = this,
        i0,
        i1 = that._found || 0,
        n = that.cells.length,
        cell; // Use the previously-found cell, or start with an arbitrary one.

    while (!(cell = that.cells[i1])) if (++i1 >= n) return null;

    var dx = x - cell.site[0],
        dy = y - cell.site[1],
        d2 = dx * dx + dy * dy; // Traverse the half-edges to find a closer cell, if any.

    do {
      cell = that.cells[i0 = i1], i1 = null;
      cell.halfedges.forEach(function (e) {
        var edge = that.edges[e],
            v = edge.left;
        if ((v === cell.site || !v) && !(v = edge.right)) return;
        var vx = x - v[0],
            vy = y - v[1],
            v2 = vx * vx + vy * vy;
        if (v2 < d2) d2 = v2, i1 = v.index;
      });
    } while (i1 !== null);

    that._found = i0;
    return radius == null || d2 <= radius * radius ? cell.site : null;
  }
};