Rock Pool V0.02 - OpenProcessing

mySketch
xxxxxxxxxx
 
function Voronoi() {
  this.vertices = null;
  this.edges = null;
  this.cells = null;
  this.toRecycle = null;
  this.beachsectionJunkyard = [];
  this.circleEventJunkyard = [];
  this.vertexJunkyard = [];
  this.edgeJunkyard = [];
  this.cellJunkyard = [];
  }
​
// ---------------------------------------------------------------------------
​
Voronoi.prototype.reset = function() {
  if (!this.beachline) {
      this.beachline = new this.RBTree();
      }
  // Move leftover beachsections to the beachsection junkyard.
  if (this.beachline.root) {
      var beachsection = this.beachline.getFirst(this.beachline.root);
      while (beachsection) {
          this.beachsectionJunkyard.push(beachsection); // mark for reuse
          beachsection = beachsection.rbNext;
          }
      }
  this.beachline.root = null;
  if (!this.circleEvents) {
      this.circleEvents = new this.RBTree();
      }
  this.circleEvents.root = this.firstCircleEvent = null;
  this.vertices = [];
  this.edges = [];
  this.cells = [];
  };
​
Voronoi.prototype.sqrt = Math.sqrt;
Voronoi.prototype.abs = Math.abs;
Voronoi.prototype.ε = Voronoi.ε = 1e-9;
Voronoi.prototype.invε = Voronoi.invε = 1.0 / Voronoi.ε;
Voronoi.prototype.equalWithEpsilon = function(a,b){return this.abs(a-b)<1e-9;};
Voronoi.prototype.greaterThanWithEpsilon = function(a,b){return a-b>1e-9;};
Voronoi.prototype.greaterThanOrEqualWithEpsilon = function(a,b){return b-a<1e-9;};
Voronoi.prototype.lessThanWithEpsilon = function(a,b){return b-a>1e-9;};
Voronoi.prototype.lessThanOrEqualWithEpsilon = function(a,b){return a-b<1e-9;};
​
// ---------------------------------------------------------------------------
// Red-Black tree code (based on C version of "rbtree" by Franck Bui-Huu
// https://github.com/fbuihuu/libtree/blob/master/rb.c
​
Voronoi.prototype.RBTree = function() {
  this.root = null;
  };
​
Voronoi.prototype.RBTree.prototype.rbInsertSuccessor = function(node, successor) {
  var parent;
  if (node) {
      // >>> rhill 2011-05-27: Performance: cache previous/next nodes
      successor.rbPrevious = node;
      successor.rbNext = node.rbNext;
      if (node.rbNext) {
          node.rbNext.rbPrevious = successor;
          }
      node.rbNext = successor;
      // <<<
      if (node.rbRight) {
          // in-place expansion of node.rbRight.getFirst();
          node = node.rbRight;
          while (node.rbLeft) {node = node.rbLeft;}
          node.rbLeft = successor;
          }
      else {
          node.rbRight = successor;
          }
      parent = node;
      }
  // rhill 2011-06-07: if node is null, successor must be inserted
  // to the left-most part of the tree
  else if (this.root) {
      node = this.getFirst(this.root);
      // >>> Performance: cache previous/next nodes
      successor.rbPrevious = null;
      successor.rbNext = node;
      node.rbPrevious = successor;
      // <<<
      node.rbLeft = successor;
      parent = node;
      }
  else {
      // >>> Performance: cache previous/next nodes
      successor.rbPrevious = successor.rbNext = null;
      // <<<
      this.root = successor;
      parent = null;
      }
  successor.rbLeft = successor.rbRight = null;
  successor.rbParent = parent;
  successor.rbRed = true;
  // Fixup the modified tree by recoloring nodes and performing
  // rotations (2 at most) hence the red-black tree properties are
  // preserved.
  var grandpa, uncle;
  node = successor;
  while (parent && parent.rbRed) {
      grandpa = parent.rbParent;
      if (parent === grandpa.rbLeft) {
          uncle = grandpa.rbRight;
          if (uncle && uncle.rbRed) {
              parent.rbRed = uncle.rbRed = false;
              grandpa.rbRed = true;
              node = grandpa;
              }
          else {
              if (node === parent.rbRight) {
                  this.rbRotateLeft(parent);
                  node = parent;
                  parent = node.rbParent;
                  }
              parent.rbRed = false;
              grandpa.rbRed = true;
              this.rbRotateRight(grandpa);
              }
          }
      else {
          uncle = grandpa.rbLeft;
          if (uncle && uncle.rbRed) {
              parent.rbRed = uncle.rbRed = false;
              grandpa.rbRed = true;
              node = grandpa;
              }
          else {
              if (node === parent.rbLeft) {
                  this.rbRotateRight(parent);
                  node = parent;
                  parent = node.rbParent;
                  }
              parent.rbRed = false;
              grandpa.rbRed = true;
              this.rbRotateLeft(grandpa);
              }
          }
      parent = node.rbParent;
      }
  this.root.rbRed = false;
  };
​
Voronoi.prototype.RBTree.prototype.rbRemoveNode = function(node) {
  // >>> rhill 2011-05-27: Performance: cache previous/next nodes
  if (node.rbNext) {
      node.rbNext.rbPrevious = node.rbPrevious;
      }
  if (node.rbPrevious) {
      node.rbPrevious.rbNext = node.rbNext;
      }
  node.rbNext = node.rbPrevious = null;
  // <<<
  var parent = node.rbParent,
      left = node.rbLeft,
      right = node.rbRight,
      next;
  if (!left) {
      next = right;
      }
  else if (!right) {
      next = left;
      }
  else {
      next = this.getFirst(right);
      }
  if (parent) {
      if (parent.rbLeft === node) {
          parent.rbLeft = next;
          }
      else {
          parent.rbRight = next;
          }
      }
  else {
      this.root = next;
      }
  // enforce red-black rules
  var isRed;
  if (left && right) {
      isRed = next.rbRed;
      next.rbRed = node.rbRed;
      next.rbLeft = left;
      left.rbParent = next;
      if (next !== right) {
          parent = next.rbParent;
          next.rbParent = node.rbParent;
          node = next.rbRight;
          parent.rbLeft = node;
          next.rbRight = right;
          right.rbParent = next;
          }
      else {
          next.rbParent = parent;
          parent = next;
          node = next.rbRight;
          }
      }
  else {
      isRed = node.rbRed;
      node = next;
      }
  // 'node' is now the sole successor's child and 'parent' its
  // new parent (since the successor can have been moved)
  if (node) {
      node.rbParent = parent;
      }
  // the 'easy' cases
  if (isRed) {return;}
  if (node && node.rbRed) {
      node.rbRed = false;
      return;
      }
  // the other cases
  var sibling;
  do {
      if (node === this.root) {
          break;
          }
      if (node === parent.rbLeft) {
          sibling = parent.rbRight;
          if (sibling.rbRed) {
              sibling.rbRed = false;
              parent.rbRed = true;
              this.rbRotateLeft(parent);
              sibling = parent.rbRight;
              }
          if ((sibling.rbLeft && sibling.rbLeft.rbRed) || (sibling.rbRight && sibling.rbRight.rbRed)) {
              if (!sibling.rbRight || !sibling.rbRight.rbRed) {
                  sibling.rbLeft.rbRed = false;
                  sibling.rbRed = true;
                  this.rbRotateRight(sibling);
                  sibling = parent.rbRight;
                  }
              sibling.rbRed = parent.rbRed;
              parent.rbRed = sibling.rbRight.rbRed = false;
              this.rbRotateLeft(parent);
              node = this.root;
              break;
              }
          }
      else {
          sibling = parent.rbLeft;
          if (sibling.rbRed) {
              sibling.rbRed = false;
              parent.rbRed = true;
              this.rbRotateRight(parent);
              sibling = parent.rbLeft;
              }
          if ((sibling.rbLeft && sibling.rbLeft.rbRed) || (sibling.rbRight && sibling.rbRight.rbRed)) {
              if (!sibling.rbLeft || !sibling.rbLeft.rbRed) {
                  sibling.rbRight.rbRed = false;
                  sibling.rbRed = true;
                  this.rbRotateLeft(sibling);
                  sibling = parent.rbLeft;
                  }
              sibling.rbRed = parent.rbRed;
              parent.rbRed = sibling.rbLeft.rbRed = false;
              this.rbRotateRight(parent);
              node = this.root;
              break;
              }
          }
      sibling.rbRed = true;
      node = parent;
      parent = parent.rbParent;
  } while (!node.rbRed);
  if (node) {node.rbRed = false;}
  };
​
Voronoi.prototype.RBTree.prototype.rbRotateLeft = function(node) {
  var p = node,
      q = node.rbRight, // can't be null
      parent = p.rbParent;
  if (parent) {
      if (parent.rbLeft === p) {
          parent.rbLeft = q;
          }
      else {
          parent.rbRight = q;
          }
      }
  else {
      this.root = q;
      }
  q.rbParent = parent;
  p.rbParent = q;
  p.rbRight = q.rbLeft;
  if (p.rbRight) {
      p.rbRight.rbParent = p;
      }
  q.rbLeft = p;
  };
​
Voronoi.prototype.RBTree.prototype.rbRotateRight = function(node) {
  var p = node,
      q = node.rbLeft, // can't be null
      parent = p.rbParent;
  if (parent) {
      if (parent.rbLeft === p) {
          parent.rbLeft = q;
          }
      else {
          parent.rbRight = q;
          }
      }
  else {
      this.root = q;
      }
  q.rbParent = parent;
  p.rbParent = q;
  p.rbLeft = q.rbRight;
  if (p.rbLeft) {
      p.rbLeft.rbParent = p;
      }
  q.rbRight = p;
  };
​
Voronoi.prototype.RBTree.prototype.getFirst = function(node) {
  while (node.rbLeft) {
      node = node.rbLeft;
      }
  return node;
  };
​
Voronoi.prototype.RBTree.prototype.getLast = function(node) {
  while (node.rbRight) {
      node = node.rbRight;
      }
  return node;
  };
​
// ---------------------------------------------------------------------------
// Diagram methods
​
Voronoi.prototype.Diagram = function(site) {
  this.site = site;
  };
​
// ---------------------------------------------------------------------------
// Cell methods
​
Voronoi.prototype.Cell = function(site) {
  this.site = site;
  this.halfedges = [];
  this.closeMe = false;
  };
​
Voronoi.prototype.Cell.prototype.init = function(site) {
  this.site = site;
  this.halfedges = [];
  this.closeMe = false;
  return this;
  };
​
Voronoi.prototype.createCell = function(site) {
  var cell = this.cellJunkyard.pop();
  if ( cell ) {
      return cell.init(site);
      }
  return new this.Cell(site);
  };
​
Voronoi.prototype.Cell.prototype.prepareHalfedges = function() {
  var halfedges = this.halfedges,
      iHalfedge = halfedges.length,
      edge;
  // get rid of unused halfedges
  // rhill 2011-05-27: Keep it simple, no point here in trying
  // to be fancy: dangling edges are a typically a minority.
  while (iHalfedge--) {
      edge = halfedges[iHalfedge].edge;
      if (!edge.vb || !edge.va) {
          halfedges.splice(iHalfedge,1);
          }
      }
​
  // rhill 2011-05-26: I tried to use a binary search at insertion
  // time to keep the array sorted on-the-fly (in Cell.addHalfedge()).
  // There was no real benefits in doing so, performance on
  // Firefox 3.6 was improved marginally, while performance on
  // Opera 11 was penalized marginally.
  halfedges.sort(function(a,b){return b.angle-a.angle;});
  return halfedges.length;
  };
​
// Return a list of the neighbor Ids
Voronoi.prototype.Cell.prototype.getNeighborIds = function() {
  var neighbors = [],
      iHalfedge = this.halfedges.length,
      edge;
  while (iHalfedge--){
      edge = this.halfedges[iHalfedge].edge;
      if (edge.lSite !== null && edge.lSite.voronoiId != this.site.voronoiId) {
          neighbors.push(edge.lSite.voronoiId);
          }
      else if (edge.rSite !== null && edge.rSite.voronoiId != this.site.voronoiId){
          neighbors.push(edge.rSite.voronoiId);
          }
      }
  return neighbors;
  };
​
// Compute bounding box
//
Voronoi.prototype.Cell.prototype.getBbox = function() {
  var halfedges = this.halfedges,
      iHalfedge = halfedges.length,
      xmin = Infinity,
      ymin = Infinity,
      xmax = -Infinity,
      ymax = -Infinity,
      v, vx, vy;
  while (iHalfedge--) {
      v = halfedges[iHalfedge].getStartpoint();
      vx = v.x;
      vy = v.y;
      if (vx < xmin) {xmin = vx;}
      if (vy < ymin) {ymin = vy;}
      if (vx > xmax) {xmax = vx;}
      if (vy > ymax) {ymax = vy;}
      // we dont need to take into account end point,
      // since each end point matches a start point
      }
  return {
      x: xmin,
      y: ymin,
      width: xmax-xmin,
      height: ymax-ymin
      };
  };
​
// Return whether a point is inside, on, or outside the cell:
//   -1: point is outside the perimeter of the cell
//    0: point is on the perimeter of the cell
//    1: point is inside the perimeter of the cell
//
Voronoi.prototype.Cell.prototype.pointIntersection = function(x, y) {
  // Check if point in polygon. Since all polygons of a Voronoi
  // diagram are convex, then:
  // http://paulbourke.net/geometry/polygonmesh/
  // Solution 3 (2D):
  //   "If the polygon is convex then one can consider the polygon
  //   "as a 'path' from the first vertex. A point is on the interior
  //   "of this polygons if it is always on the same side of all the
  //   "line segments making up the path. ...
  //   "(y - y0) (x1 - x0) - (x - x0) (y1 - y0)
  //   "if it is less than 0 then P is to the right of the line segment,
  //   "if greater than 0 it is to the left, if equal to 0 then it lies
  //   "on the line segment"
  var halfedges = this.halfedges,
      iHalfedge = halfedges.length,
      halfedge,
      p0, p1, r;
  while (iHalfedge--) {
      halfedge = halfedges[iHalfedge];
      p0 = halfedge.getStartpoint();
      p1 = halfedge.getEndpoint();
      r = (y-p0.y)*(p1.x-p0.x)-(x-p0.x)*(p1.y-p0.y);
      if (!r) {
          return 0;
          }
      if (r > 0) {
          return -1;
          }
      }
  return 1;
  };
​
// ---------------------------------------------------------------------------
// Edge methods
//
​
Voronoi.prototype.Vertex = function(x, y) {
  this.x = x;
  this.y = y;
  };
​
Voronoi.prototype.Edge = function(lSite, rSite) {
  this.lSite = lSite;
  this.rSite = rSite;
  this.va = this.vb = null;
  };
​
Voronoi.prototype.Halfedge = function(edge, lSite, rSite) {
  this.site = lSite;
  this.edge = edge;
  // 'angle' is a value to be used for properly sorting the
  // halfsegments counterclockwise. By convention, we will
  // use the angle of the line defined by the 'site to the left'
  // to the 'site to the right'.
  // However, border edges have no 'site to the right': thus we
  // use the angle of line perpendicular to the halfsegment (the
  // edge should have both end points defined in such case.)
  if (rSite) {
      this.angle = Math.atan2(rSite.y-lSite.y, rSite.x-lSite.x);
      }
  else {
      var va = edge.va,
          vb = edge.vb;
      // rhill 2011-05-31: used to call getStartpoint()/getEndpoint(),
      // but for performance purpose, these are expanded in place here.
      this.angle = edge.lSite === lSite ?
          Math.atan2(vb.x-va.x, va.y-vb.y) :
          Math.atan2(va.x-vb.x, vb.y-va.y);
      }
  };
​
Voronoi.prototype.createHalfedge = function(edge, lSite, rSite) {
  return new this.Halfedge(edge, lSite, rSite);
  };
​
Voronoi.prototype.Halfedge.prototype.getStartpoint = function() {
  return this.edge.lSite === this.site ? this.edge.va : this.edge.vb;
  };
​
Voronoi.prototype.Halfedge.prototype.getEndpoint = function() {
  return this.edge.lSite === this.site ? this.edge.vb : this.edge.va;
  };
​
​
​
// this create and add a vertex to the internal collection
​
Voronoi.prototype.createVertex = function(x, y) {
  var v = this.vertexJunkyard.pop();
  if ( !v ) {
      v = new this.Vertex(x, y);
      }
  else {
      v.x = x;
      v.y = y;
      }
  this.vertices.push(v);
  return v;
  };
​
// this create and add an edge to internal collection, and also create
// two halfedges which are added to each site's counterclockwise array
// of halfedges.
​
Voronoi.prototype.createEdge = function(lSite, rSite, va, vb) {
  var edge = this.edgeJunkyard.pop();
  if ( !edge ) {
      edge = new this.Edge(lSite, rSite);
      }
  else {
      edge.lSite = lSite;
      edge.rSite = rSite;
      edge.va = edge.vb = null;
      }
​
  this.edges.push(edge);
  if (va) {
      this.setEdgeStartpoint(edge, lSite, rSite, va);
      }
  if (vb) {
      this.setEdgeEndpoint(edge, lSite, rSite, vb);
      }
  this.cells[lSite.voronoiId].halfedges.push(this.createHalfedge(edge, lSite, rSite));
  this.cells[rSite.voronoiId].halfedges.push(this.createHalfedge(edge, rSite, lSite));
  return edge;
  };
​
Voronoi.prototype.createBorderEdge = function(lSite, va, vb) {
  var edge = this.edgeJunkyard.pop();
  if ( !edge ) {
      edge = new this.Edge(lSite, null);
      }
  else {
      edge.lSite = lSite;
      edge.rSite = null;
      }
  edge.va = va;
  edge.vb = vb;
  this.edges.push(edge);
  return edge;
  };
​
Voronoi.prototype.setEdgeStartpoint = function(edge, lSite, rSite, vertex) {
  if (!edge.va && !edge.vb) {
      edge.va = vertex;
      edge.lSite = lSite;
      edge.rSite = rSite;
      }
  else if (edge.lSite === rSite) {
      edge.vb = vertex;
      }
  else {
      edge.va = vertex;
      }
  };
​
Voronoi.prototype.setEdgeEndpoint = function(edge, lSite, rSite, vertex) {
  this.setEdgeStartpoint(edge, rSite, lSite, vertex);
  };
​
// ---------------------------------------------------------------------------
// Beachline methods
​
// rhill 2011-06-07: For some reasons, performance suffers significantly
// when instanciating a literal object instead of an empty ctor
Voronoi.prototype.Beachsection = function() {
  };
​
// rhill 2011-06-02: A lot of Beachsection instanciations
// occur during the computation of the Voronoi diagram,
// somewhere between the number of sites and twice the
// number of sites, while the number of Beachsections on the
// beachline at any given time is comparatively low. For this
// reason, we reuse already created Beachsections, in order
// to avoid new memory allocation. This resulted in a measurable
// performance gain.
​
Voronoi.prototype.createBeachsection = function(site) {
  var beachsection = this.beachsectionJunkyard.pop();
  if (!beachsection) {
      beachsection = new this.Beachsection();
      }
  beachsection.site = site;
  return beachsection;
  };
​
// calculate the left break point of a particular beach section,
// given a particular sweep line
Voronoi.prototype.leftBreakPoint = function(arc, directrix) {
  // http://en.wikipedia.org/wiki/Parabola
  // http://en.wikipedia.org/wiki/Quadratic_equation
  // h1 = x1,
  // k1 = (y1+directrix)/2,
  // h2 = x2,
  // k2 = (y2+directrix)/2,
  // p1 = k1-directrix,
  // a1 = 1/(4*p1),
  // b1 = -h1/(2*p1),
  // c1 = h1*h1/(4*p1)+k1,
  // p2 = k2-directrix,
  // a2 = 1/(4*p2),
  // b2 = -h2/(2*p2),
  // c2 = h2*h2/(4*p2)+k2,
  // x = (-(b2-b1) + Math.sqrt((b2-b1)*(b2-b1) - 4*(a2-a1)*(c2-c1))) / (2*(a2-a1))
  // When x1 become the x-origin:
  // h1 = 0,
  // k1 = (y1+directrix)/2,
  // h2 = x2-x1,
  // k2 = (y2+directrix)/2,
  // p1 = k1-directrix,
  // a1 = 1/(4*p1),
  // b1 = 0,
  // c1 = k1,
  // p2 = k2-directrix,
  // a2 = 1/(4*p2),
  // b2 = -h2/(2*p2),
  // c2 = h2*h2/(4*p2)+k2,
  // x = (-b2 + Math.sqrt(b2*b2 - 4*(a2-a1)*(c2-k1))) / (2*(a2-a1)) + x1
​
  // change code below at your own risk: care has been taken to
  // reduce errors due to computers' finite arithmetic precision.
  // Maybe can still be improved, will see if any more of this
  // kind of errors pop up again.
  var site = arc.site,
      rfocx = site.x,
      rfocy = site.y,
      pby2 = rfocy-directrix;
  // parabola in degenerate case where focus is on directrix
  if (!pby2) {
      return rfocx;
      }
  var lArc = arc.rbPrevious;
  if (!lArc) {
      return -Infinity;
      }
  site = lArc.site;
  var lfocx = site.x,
      lfocy = site.y,
      plby2 = lfocy-directrix;
  // parabola in degenerate case where focus is on directrix
  if (!plby2) {
      return lfocx;
      }
  var hl = lfocx-rfocx,
      aby2 = 1/pby2-1/plby2,
      b = hl/plby2;
  if (aby2) {
      return (-b+this.sqrt(b*b-2*aby2*(hl*hl/(-2*plby2)-lfocy+plby2/2+rfocy-pby2/2)))/aby2+rfocx;
      }
  // both parabolas have same distance to directrix, thus break point is midway
  return (rfocx+lfocx)/2;
  };
​
// calculate the right break point of a particular beach section,
// given a particular directrix
Voronoi.prototype.rightBreakPoint = function(arc, directrix) {
  var rArc = arc.rbNext;
  if (rArc) {
      return this.leftBreakPoint(rArc, directrix);
      }
  var site = arc.site;
  return site.y === directrix ? site.x : Infinity;
  };
​
Voronoi.prototype.detachBeachsection = function(beachsection) {
  this.detachCircleEvent(beachsection); // detach potentially attached circle event
  this.beachline.rbRemoveNode(beachsection); // remove from RB-tree
  this.beachsectionJunkyard.push(beachsection); // mark for reuse
  };
​
Voronoi.prototype.removeBeachsection = function(beachsection) {
  var circle = beachsection.circleEvent,
      x = circle.x,
      y = circle.ycenter,
      vertex = this.createVertex(x, y),
      previous = beachsection.rbPrevious,
      next = beachsection.rbNext,
      disappearingTransitions = [beachsection],
      abs_fn = Math.abs;
​
  // remove collapsed beachsection from beachline
  this.detachBeachsection(beachsection);
​
  // there could be more than one empty arc at the deletion point, this
  // happens when more than two edges are linked by the same vertex,
  // so we will collect all those edges by looking up both sides of
  // the deletion point.
  // by the way, there is *always* a predecessor/successor to any collapsed
  // beach section, it's just impossible to have a collapsing first/last
  // beach sections on the beachline, since they obviously are unconstrained
  // on their left/right side.
​
  // look left
  var lArc = previous;
  while (lArc.circleEvent && abs_fn(x-lArc.circleEvent.x)<1e-9 && abs_fn(y-lArc.circleEvent.ycenter)<1e-9) {
      previous = lArc.rbPrevious;
      disappearingTransitions.unshift(lArc);
      this.detachBeachsection(lArc); // mark for reuse
      lArc = previous;
      }
  // even though it is not disappearing, I will also add the beach section
  // immediately to the left of the left-most collapsed beach section, for
  // convenience, since we need to refer to it later as this beach section
  // is the 'left' site of an edge for which a start point is set.
  disappearingTransitions.unshift(lArc);
  this.detachCircleEvent(lArc);
​
  // look right
  var rArc = next;
  while (rArc.circleEvent && abs_fn(x-rArc.circleEvent.x)<1e-9 && abs_fn(y-rArc.circleEvent.ycenter)<1e-9) {
      next = rArc.rbNext;
      disappearingTransitions.push(rArc);
      this.detachBeachsection(rArc); // mark for reuse
      rArc = next;
      }
  // we also have to add the beach section immediately to the right of the
  // right-most collapsed beach section, since there is also a disappearing
  // transition representing an edge's start point on its left.
  disappearingTransitions.push(rArc);
  this.detachCircleEvent(rArc);
​
  // walk through all the disappearing transitions between beach sections and
  // set the start point of their (implied) edge.
  var nArcs = disappearingTransitions.length,
      iArc;
  for (iArc=1; iArc<nArcs; iArc++) {
      rArc = disappearingTransitions[iArc];
      lArc = disappearingTransitions[iArc-1];
      this.setEdgeStartpoint(rArc.edge, lArc.site, rArc.site, vertex);
      }
​
  // create a new edge as we have now a new transition between
  // two beach sections which were previously not adjacent.
  // since this edge appears as a new vertex is defined, the vertex
  // actually define an end point of the edge (relative to the site
  // on the left)
  lArc = disappearingTransitions[0];
  rArc = disappearingTransitions[nArcs-1];
  rArc.edge = this.createEdge(lArc.site, rArc.site, undefined, vertex);
​
  // create circle events if any for beach sections left in the beachline
  // adjacent to collapsed sections
  this.attachCircleEvent(lArc);
  this.attachCircleEvent(rArc);
  };
​
Voronoi.prototype.addBeachsection = function(site) {
  var x = site.x,
      directrix = site.y;
​
  // find the left and right beach sections which will surround the newly
  // created beach section.
  // rhill 2011-06-01: This loop is one of the most often executed,
  // hence we expand in-place the comparison-against-epsilon calls.
  var lArc, rArc,
      dxl, dxr,
      node = this.beachline.root;
​
  while (node) {
      dxl = this.leftBreakPoint(node,directrix)-x;
      // x lessThanWithEpsilon xl => falls somewhere before the left edge of the beachsection
      if (dxl > 1e-9) {
          // this case should never happen
          // if (!node.rbLeft) {
          //    rArc = node.rbLeft;
          //    break;
          //    }
          node = node.rbLeft;
          }
      else {
          dxr = x-this.rightBreakPoint(node,directrix);
          // x greaterThanWithEpsilon xr => falls somewhere after the right edge of the beachsection
          if (dxr > 1e-9) {
              if (!node.rbRight) {
                  lArc = node;
                  break;
                  }
              node = node.rbRight;
              }
          else {
              // x equalWithEpsilon xl => falls exactly on the left edge of the beachsection
              if (dxl > -1e-9) {
                  lArc = node.rbPrevious;
                  rArc = node;
                  }
              // x equalWithEpsilon xr => falls exactly on the right edge of the beachsection
              else if (dxr > -1e-9) {
                  lArc = node;
                  rArc = node.rbNext;
                  }
              // falls exactly somewhere in the middle of the beachsection
              else {
                  lArc = rArc = node;
                  }
              break;
              }
          }
      }
  // at this point, keep in mind that lArc and/or rArc could be
  // undefined or null.
​
  // create a new beach section object for the site and add it to RB-tree
  var newArc = this.createBeachsection(site);
  this.beachline.rbInsertSuccessor(lArc, newArc);
​
  // cases:
  //
​
  // [null,null]
  // least likely case: new beach section is the first beach section on the
  // beachline.
  // This case means:
  //   no new transition appears
  //   no collapsing beach section
  //   new beachsection become root of the RB-tree
  if (!lArc && !rArc) {
      return;
      }
​
  // [lArc,rArc] where lArc == rArc
  // most likely case: new beach section split an existing beach
  // section.
  // This case means:
  //   one new transition appears
  //   the left and right beach section might be collapsing as a result
  //   two new nodes added to the RB-tree
  if (lArc === rArc) {
      // invalidate circle event of split beach section
      this.detachCircleEvent(lArc);
​
      // split the beach section into two separate beach sections
      rArc = this.createBeachsection(lArc.site);
      this.beachline.rbInsertSuccessor(newArc, rArc);
​
      // since we have a new transition between two beach sections,
      // a new edge is born
      newArc.edge = rArc.edge = this.createEdge(lArc.site, newArc.site);
​
      // check whether the left and right beach sections are collapsing
      // and if so create circle events, to be notified when the point of
      // collapse is reached.
      this.attachCircleEvent(lArc);
      this.attachCircleEvent(rArc);
      return;
      }
​
  // [lArc,null]
  // even less likely case: new beach section is the *last* beach section
  // on the beachline -- this can happen *only* if *all* the previous beach
  // sections currently on the beachline share the same y value as
  // the new beach section.
  // This case means:
  //   one new transition appears
  //   no collapsing beach section as a result
  //   new beach section become right-most node of the RB-tree
  if (lArc && !rArc) {
      newArc.edge = this.createEdge(lArc.site,newArc.site);
      return;
      }
​
  // [null,rArc]
  // impossible case: because sites are strictly processed from top to bottom,
  // and left to right, which guarantees that there will always be a beach section
  // on the left -- except of course when there are no beach section at all on
  // the beach line, which case was handled above.
  // rhill 2011-06-02: No point testing in non-debug version
  //if (!lArc && rArc) {
  //    throw "Voronoi.addBeachsection(): What is this I don't even";
  //    }
​
  // [lArc,rArc] where lArc != rArc
  // somewhat less likely case: new beach section falls *exactly* in between two
  // existing beach sections
  // This case means:
  //   one transition disappears
  //   two new transitions appear
  //   the left and right beach section might be collapsing as a result
  //   only one new node added to the RB-tree
  if (lArc !== rArc) {
      // invalidate circle events of left and right sites
      this.detachCircleEvent(lArc);
      this.detachCircleEvent(rArc);
​
      // an existing transition disappears, meaning a vertex is defined at
      // the disappearance point.
      // since the disappearance is caused by the new beachsection, the
      // vertex is at the center of the circumscribed circle of the left,
      // new and right beachsections.
      // http://mathforum.org/library/drmath/view/55002.html
      // Except that I bring the origin at A to simplify
      // calculation
      var lSite = lArc.site,
          ax = lSite.x,
          ay = lSite.y,
          bx=site.x-ax,
          by=site.y-ay,
          rSite = rArc.site,
          cx=rSite.x-ax,
          cy=rSite.y-ay,
          d=2*(bx*cy-by*cx),
          hb=bx*bx+by*by,
          hc=cx*cx+cy*cy,
          vertex = this.createVertex((cy*hb-by*hc)/d+ax, (bx*hc-cx*hb)/d+ay);
​
      // one transition disappear
      this.setEdgeStartpoint(rArc.edge, lSite, rSite, vertex);
​
      // two new transitions appear at the new vertex location
      newArc.edge = this.createEdge(lSite, site, undefined, vertex);
      rArc.edge = this.createEdge(site, rSite, undefined, vertex);
​
      // check whether the left and right beach sections are collapsing
      // and if so create circle events, to handle the point of collapse.
      this.attachCircleEvent(lArc);
      this.attachCircleEvent(rArc);
      return;
      }
  };
​
// ---------------------------------------------------------------------------
// Circle event methods
​
// rhill 2011-06-07: For some reasons, performance suffers significantly
// when instanciating a literal object instead of an empty ctor
Voronoi.prototype.CircleEvent = function() {
  // rhill 2013-10-12: it helps to state exactly what we are at ctor time.
  this.arc = null;
  this.rbLeft = null;
  this.rbNext = null;
  this.rbParent = null;
  this.rbPrevious = null;
  this.rbRed = false;
  this.rbRight = null;
  this.site = null;
  this.x = this.y = this.ycenter = 0;
  };
​
Voronoi.prototype.attachCircleEvent = function(arc) {
  var lArc = arc.rbPrevious,
      rArc = arc.rbNext;
  if (!lArc || !rArc) {return;} // does that ever happen?
  var lSite = lArc.site,
      cSite = arc.site,
      rSite = rArc.site;
​
  // If site of left beachsection is same as site of
  // right beachsection, there can't be convergence
  if (lSite===rSite) {return;}
​
  // Find the circumscribed circle for the three sites associated
  // with the beachsection triplet.
  // rhill 2011-05-26: It is more efficient to calculate in-place
  // rather than getting the resulting circumscribed circle from an
  // object returned by calling Voronoi.circumcircle()
  // http://mathforum.org/library/drmath/view/55002.html
  // Except that I bring the origin at cSite to simplify calculations.
  // The bottom-most part of the circumcircle is our Fortune 'circle
  // event', and its center is a vertex potentially part of the final
  // Voronoi diagram.
  var bx = cSite.x,
      by = cSite.y,
      ax = lSite.x-bx,
      ay = lSite.y-by,
      cx = rSite.x-bx,
      cy = rSite.y-by;
​
  // If points l->c->r are clockwise, then center beach section does not
  // collapse, hence it can't end up as a vertex (we reuse 'd' here, which
  // sign is reverse of the orientation, hence we reverse the test.
  // http://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon
  // rhill 2011-05-21: Nasty finite precision error which caused circumcircle() to
  // return infinites: 1e-12 seems to fix the problem.
  var d = 2*(ax*cy-ay*cx);
  if (d >= -2e-12){return;}
​
  var ha = ax*ax+ay*ay,
      hc = cx*cx+cy*cy,
      x = (cy*ha-ay*hc)/d,
      y = (ax*hc-cx*ha)/d,
      ycenter = y+by;
​
  // Important: ybottom should always be under or at sweep, so no need
  // to waste CPU cycles by checking
​
  // recycle circle event object if possible
  var circleEvent = this.circleEventJunkyard.pop();
  if (!circleEvent) {
      circleEvent = new this.CircleEvent();
      }
  circleEvent.arc = arc;
  circleEvent.site = cSite;
  circleEvent.x = x+bx;
  circleEvent.y = ycenter+this.sqrt(x*x+y*y); // y bottom
  circleEvent.ycenter = ycenter;
  arc.circleEvent = circleEvent;
​
  // find insertion point in RB-tree: circle events are ordered from
  // smallest to largest
  var predecessor = null,
      node = this.circleEvents.root;
  while (node) {
      if (circleEvent.y < node.y || (circleEvent.y === node.y && circleEvent.x <= node.x)) {
          if (node.rbLeft) {
              node = node.rbLeft;
              }
          else {
              predecessor = node.rbPrevious;
              break;
              }
          }
      else {
          if (node.rbRight) {
              node = node.rbRight;
              }
          else {
              predecessor = node;
              break;
              }
          }
      }
  this.circleEvents.rbInsertSuccessor(predecessor, circleEvent);
  if (!predecessor) {
      this.firstCircleEvent = circleEvent;
      }
  };
​
Voronoi.prototype.detachCircleEvent = function(arc) {
  var circleEvent = arc.circleEvent;
  if (circleEvent) {
      if (!circleEvent.rbPrevious) {
          this.firstCircleEvent = circleEvent.rbNext;
          }
      this.circleEvents.rbRemoveNode(circleEvent); // remove from RB-tree
      this.circleEventJunkyard.push(circleEvent);
      arc.circleEvent = null;
      }
  };
​
// ---------------------------------------------------------------------------
// Diagram completion methods
​
// connect dangling edges (not if a cursory test tells us
// it is not going to be visible.
// return value:
//   false: the dangling endpoint couldn't be connected
//   true: the dangling endpoint could be connected
Voronoi.prototype.connectEdge = function(edge, bbox) {
  // skip if end point already connected
  var vb = edge.vb;
  if (!!vb) {return true;}
​
  // make local copy for performance purpose
  var va = edge.va,
      xl = bbox.xl,
      xr = bbox.xr,
      yt = bbox.yt,
      yb = bbox.yb,
      lSite = edge.lSite,
      rSite = edge.rSite,
      lx = lSite.x,
      ly = lSite.y,
      rx = rSite.x,
      ry = rSite.y,
      fx = (lx+rx)/2,
      fy = (ly+ry)/2,
      fm, fb;
​
  // if we reach here, this means cells which use this edge will need
  // to be closed, whether because the edge was removed, or because it
  // was connected to the bounding box.
  this.cells[lSite.voronoiId].closeMe = true;
  this.cells[rSite.voronoiId].closeMe = true;
​
  // get the line equation of the bisector if line is not vertical
  if (ry !== ly) {
      fm = (lx-rx)/(ry-ly);
      fb = fy-fm*fx;
      }
​
  // remember, direction of line (relative to left site):
  // upward: left.x < right.x
  // downward: left.x > right.x
  // horizontal: left.x == right.x
  // upward: left.x < right.x
  // rightward: left.y < right.y
  // leftward: left.y > right.y
  // vertical: left.y == right.y
​
  // depending on the direction, find the best side of the
  // bounding box to use to determine a reasonable start point
​
  // rhill 2013-12-02:
  // While at it, since we have the values which define the line,
  // clip the end of va if it is outside the bbox.
  // https://github.com/gorhill/Javascript-Voronoi/issues/15
  // TODO: Do all the clipping here rather than rely on Liang-Barsky
  // which does not do well sometimes due to loss of arithmetic
  // precision. The code here doesn't degrade if one of the vertex is
  // at a huge distance.
​
  // special case: vertical line
  if (fm === undefined) {
      // doesn't intersect with viewport
      if (fx < xl || fx >= xr) {return false;}
      // downward
      if (lx > rx) {
          if (!va || va.y < yt) {
              va = this.createVertex(fx, yt);
              }
          else if (va.y >= yb) {
              return false;
              }
          vb = this.createVertex(fx, yb);
          }
      // upward
      else {
          if (!va || va.y > yb) {
              va = this.createVertex(fx, yb);
              }
          else if (va.y < yt) {
              return false;
              }
          vb = this.createVertex(fx, yt);
          }
      }
  // closer to vertical than horizontal, connect start point to the
  // top or bottom side of the bounding box
  else if (fm < -1 || fm > 1) {
      // downward
      if (lx > rx) {
          if (!va || va.y < yt) {
              va = this.createVertex((yt-fb)/fm, yt);
              }
          else if (va.y >= yb) {
              return false;
              }
          vb = this.createVertex((yb-fb)/fm, yb);
          }
      // upward
      else {
          if (!va || va.y > yb) {
              va = this.createVertex((yb-fb)/fm, yb);
              }
          else if (va.y < yt) {
              return false;
              }
          vb = this.createVertex((yt-fb)/fm, yt);
          }
      }
  // closer to horizontal than vertical, connect start point to the
  // left or right side of the bounding box
  else {
      // rightward
      if (ly < ry) {
          if (!va || va.x < xl) {
              va = this.createVertex(xl, fm*xl+fb);
              }
          else if (va.x >= xr) {
              return false;
              }
          vb = this.createVertex(xr, fm*xr+fb);
          }
      // leftward
      else {
          if (!va || va.x > xr) {
              va = this.createVertex(xr, fm*xr+fb);
              }
          else if (va.x < xl) {
              return false;
              }
          vb = this.createVertex(xl, fm*xl+fb);
          }
      }
  edge.va = va;
  edge.vb = vb;
​
  return true;
  };
​
// line-clipping code taken from:
//   Liang-Barsky function by Daniel White
//   http://www.skytopia.com/project/articles/compsci/clipping.html
// Thanks!
// A bit modified to minimize code paths
Voronoi.prototype.clipEdge = function(edge, bbox) {
  var ax = edge.va.x,
      ay = edge.va.y,
      bx = edge.vb.x,
      by = edge.vb.y,
      t0 = 0,
      t1 = 1,
      dx = bx-ax,
      dy = by-ay;
  // left
  var q = ax-bbox.xl;
  if (dx===0 && q<0) {return false;}
  var r = -q/dx;
  if (dx<0) {
      if (r<t0) {return false;}
      if (r<t1) {t1=r;}
      }
  else if (dx>0) {
      if (r>t1) {return false;}
      if (r>t0) {t0=r;}
      }
  // right
  q = bbox.xr-ax;
  if (dx===0 && q<0) {return false;}
  r = q/dx;
  if (dx<0) {
      if (r>t1) {return false;}
      if (r>t0) {t0=r;}
      }
  else if (dx>0) {
      if (r<t0) {return false;}
      if (r<t1) {t1=r;}
      }
  // top
  q = ay-bbox.yt;
  if (dy===0 && q<0) {return false;}
  r = -q/dy;
  if (dy<0) {
      if (r<t0) {return false;}
      if (r<t1) {t1=r;}
      }
  else if (dy>0) {
      if (r>t1) {return false;}
      if (r>t0) {t0=r;}
      }
  // bottom        
  q = bbox.yb-ay;
  if (dy===0 && q<0) {return false;}
  r = q/dy;
  if (dy<0) {
      if (r>t1) {return false;}
      if (r>t0) {t0=r;}
      }
  else if (dy>0) {
      if (r<t0) {return false;}
      if (r<t1) {t1=r;}
      }
​
  // if we reach this point, Voronoi edge is within bbox
​
  // if t0 > 0, va needs to change
  // rhill 2011-06-03: we need to create a new vertex rather
  // than modifying the existing one, since the existing
  // one is likely shared with at least another edge
  if (t0 > 0) {
      edge.va = this.createVertex(ax+t0*dx, ay+t0*dy);
      }
​
  // if t1 < 1, vb needs to change
  // rhill 2011-06-03: we need to create a new vertex rather
  // than modifying the existing one, since the existing
  // one is likely shared with at least another edge
  if (t1 < 1) {
      edge.vb = this.createVertex(ax+t1*dx, ay+t1*dy);
      }
​
  // va and/or vb were clipped, thus we will need to close
  // cells which use this edge.
  if ( t0 > 0 || t1 < 1 ) {
      this.cells[edge.lSite.voronoiId].closeMe = true;
      this.cells[edge.rSite.voronoiId].closeMe = true;
  }
​
  return true;
  };
​
// Connect/cut edges at bounding box
Voronoi.prototype.clipEdges = function(bbox) {
  // connect all dangling edges to bounding box
  // or get rid of them if it can't be done
  var edges = this.edges,
      iEdge = edges.length,
      edge,
      abs_fn = Math.abs;
​
  // iterate backward so we can splice safely
  while (iEdge--) {
      edge = edges[iEdge];
      // edge is removed if:
      //   it is wholly outside the bounding box
      //   it is looking more like a point than a line
      if (!this.connectEdge(edge, bbox) ||
          !this.clipEdge(edge, bbox) ||
          (abs_fn(edge.va.x-edge.vb.x)<1e-9 && abs_fn(edge.va.y-edge.vb.y)<1e-9)) {
          edge.va = edge.vb = null;
          edges.splice(iEdge,1);
          }
      }
  };
​
// Close the cells.
// The cells are bound by the supplied bounding box.
// Each cell refers to its associated site, and a list
// of halfedges ordered counterclockwise.
Voronoi.prototype.closeCells = function(bbox) {
  var xl = bbox.xl,
      xr = bbox.xr,
      yt = bbox.yt,
      yb = bbox.yb,
      cells = this.cells,
      iCell = cells.length,
      cell,
      iLeft,
      halfedges, nHalfedges,
      edge,
      va, vb, vz,
      lastBorderSegment,
      abs_fn = Math.abs;
​
  while (iCell--) {
      cell = cells[iCell];
      // prune, order halfedges counterclockwise, then add missing ones
      // required to close cells
      if (!cell.prepareHalfedges()) {
          continue;
          }
      if (!cell.closeMe) {
          continue;
          }
      // find first 'unclosed' point.
      // an 'unclosed' point will be the end point of a halfedge which
      // does not match the start point of the following halfedge
      halfedges = cell.halfedges;
      nHalfedges = halfedges.length;
      // special case: only one site, in which case, the viewport is the cell
      // ...
​
      // all other cases
      iLeft = 0;
      while (iLeft < nHalfedges) {
          va = halfedges[iLeft].getEndpoint();
          vz = halfedges[(iLeft+1) % nHalfedges].getStartpoint();
          // if end point is not equal to start point, we need to add the missing
          // halfedge(s) up to vz
          if (abs_fn(va.x-vz.x)>=1e-9 || abs_fn(va.y-vz.y)>=1e-9) {
​
              // rhill 2013-12-02:
              // "Holes" in the halfedges are not necessarily always adjacent.
              // https://github.com/gorhill/Javascript-Voronoi/issues/16
​
              // find entry point:
              switch (true) {
​
                  // walk downward along left side
                  case this.equalWithEpsilon(va.x,xl) && this.lessThanWithEpsilon(va.y,yb):
                      lastBorderSegment = this.equalWithEpsilon(vz.x,xl);
                      vb = this.createVertex(xl, lastBorderSegment ? vz.y : yb);
                      edge = this.createBorderEdge(cell.site, va, vb);
                      iLeft++;
                      halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null));
                      nHalfedges++;
                      if ( lastBorderSegment ) { break; }
                      va = vb;
                      // fall through
​
                  // walk rightward along bottom side
                  case this.equalWithEpsilon(va.y,yb) && this.lessThanWithEpsilon(va.x,xr):
                      lastBorderSegment = this.equalWithEpsilon(vz.y,yb);
                      vb = this.createVertex(lastBorderSegment ? vz.x : xr, yb);
                      edge = this.createBorderEdge(cell.site, va, vb);
                      iLeft++;
                      halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null));
                      nHalfedges++;
                      if ( lastBorderSegment ) { break; }
                      va = vb;
                      // fall through
​
                  // walk upward along right side
                  case this.equalWithEpsilon(va.x,xr) && this.greaterThanWithEpsilon(va.y,yt):
                      lastBorderSegment = this.equalWithEpsilon(vz.x,xr);
                      vb = this.createVertex(xr, lastBorderSegment ? vz.y : yt);
                      edge = this.createBorderEdge(cell.site, va, vb);
                      iLeft++;
                      halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null));
                      nHalfedges++;
                      if ( lastBorderSegment ) { break; }
                      va = vb;
                      // fall through
​
                  // walk leftward along top side
                  case this.equalWithEpsilon(va.y,yt) && this.greaterThanWithEpsilon(va.x,xl):
                      lastBorderSegment = this.equalWithEpsilon(vz.y,yt);
                      vb = this.createVertex(lastBorderSegment ? vz.x : xl, yt);
                      edge = this.createBorderEdge(cell.site, va, vb);
                      iLeft++;
                      halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null));
                      nHalfedges++;
                      if ( lastBorderSegment ) { break; }
                      va = vb;
                      // fall through
​
                      // walk downward along left side
                      lastBorderSegment = this.equalWithEpsilon(vz.x,xl);
                      vb = this.createVertex(xl, lastBorderSegment ? vz.y : yb);
                      edge = this.createBorderEdge(cell.site, va, vb);
                      iLeft++;
                      halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null));
                      nHalfedges++;
                      if ( lastBorderSegment ) { break; }
                      va = vb;
                      // fall through
​
                      // walk rightward along bottom side
                      lastBorderSegment = this.equalWithEpsilon(vz.y,yb);
                      vb = this.createVertex(lastBorderSegment ? vz.x : xr, yb);
                      edge = this.createBorderEdge(cell.site, va, vb);
                      iLeft++;
                      halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null));
                      nHalfedges++;
                      if ( lastBorderSegment ) { break; }
                      va = vb;
                      // fall through
​
                      // walk upward along right side
                      lastBorderSegment = this.equalWithEpsilon(vz.x,xr);
                      vb = this.createVertex(xr, lastBorderSegment ? vz.y : yt);
                      edge = this.createBorderEdge(cell.site, va, vb);
                      iLeft++;
                      halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null));
                      nHalfedges++;
                      if ( lastBorderSegment ) { break; }
                      // fall through
​
                  default:
                      throw "Voronoi.closeCells() > this makes no sense!";
                  }
              }
          iLeft++;
          }
      cell.closeMe = false;
      }
  };
​
// ---------------------------------------------------------------------------
// Debugging helper
​
Voronoi.prototype.dumpBeachline = function(y) {
  console.log('Voronoi.dumpBeachline(%f) > Beachsections, from left to right:', y);
  if ( !this.beachline ) {
      console.log('  None');
      }
  else {
      var bs = this.beachline.getFirst(this.beachline.root);
      while ( bs ) {
          console.log('  site %d: xl: %f, xr: %f', bs.site.voronoiId, this.leftBreakPoint(bs, y), this.rightBreakPoint(bs, y));
          bs = bs.rbNext;
          }
      }
  };
​
​
// ---------------------------------------------------------------------------
// Helper: Quantize sites
​
// rhill 2013-10-12:
// This is to solve https://github.com/gorhill/Javascript-Voronoi/issues/15
// Since not all users will end up using the kind of coord values which would
// cause the issue to arise, I chose to let the user decide whether or not
// he should sanitize his coord values through this helper. This way, for
// those users who uses coord values which are known to be fine, no overhead is
// added.
​
​
Voronoi.prototype.quantizeSites = function(sites) {
  var ε = this.ε,
      n = sites.length,
      site;
  while ( n-- ) {
      site = sites[n];
      site.x = Math.floor(site.x / ε) * ε;
      site.y = Math.floor(site.y / ε) * ε;
      }
  };
​
// ---------------------------------------------------------------------------
// Helper: Recycle diagram: all vertex, edge and cell objects are
// "surrendered" to the Voronoi object for reuse.
// TODO: rhill-voronoi-core v2: more performance to be gained
// when I change the semantic of what is returned.
​
​
Voronoi.prototype.recycle = function(diagram) {
  if ( diagram ) {
      if ( diagram instanceof this.Diagram ) {
          this.toRecycle = diagram;
          }
      else {
          throw 'Voronoi.recycleDiagram() > Need a Diagram object.';
          }
      }
  };
​
// ---------------------------------------------------------------------------
// Top-level Fortune loop
​
// rhill 2011-05-19:
//   Voronoi sites are kept client-side now, to allow
//   user to freely modify content. At compute time,
//   *references* to sites are copied locally.
​
Voronoi.prototype.compute = function(sites, bbox) {
  // to measure execution time
  var startTime = new Date();
​
  // init internal state
  this.reset();
​
  // any diagram data available for recycling?
  // I do that here so that this is included in execution time
  if ( this.toRecycle ) {
      this.vertexJunkyard = this.vertexJunkyard.concat(this.toRecycle.vertices);
      this.edgeJunkyard = this.edgeJunkyard.concat(this.toRecycle.edges);
      this.cellJunkyard = this.cellJunkyard.concat(this.toRecycle.cells);
      this.toRecycle = null;
      }
​
  // Initialize site event queue
  var siteEvents = sites.slice(0);
  siteEvents.sort(function(a,b){
      var r = b.y - a.y;
      if (r) {return r;}
      return b.x - a.x;
      });
​
  // process queue
  var site = siteEvents.pop(),
      siteid = 0,
      xsitex, // to avoid duplicate sites
      xsitey,
      cells = this.cells,
      circle;
​
  // main loop
  for (;;) {
      // we need to figure whether we handle a site or circle event
      // for this we find out if there is a site event and it is
      // 'earlier' than the circle event
      circle = this.firstCircleEvent;
​
      // add beach section
      if (site && (!circle || site.y < circle.y || (site.y === circle.y && site.x < circle.x))) {
          // only if site is not a duplicate
          if (site.x !== xsitex || site.y !== xsitey) {
              // first create cell for new site
              cells[siteid] = this.createCell(site);
              site.voronoiId = siteid++;
              // then create a beachsection for that site
              this.addBeachsection(site);
              // remember last site coords to detect duplicate
              xsitey = site.y;
              xsitex = site.x;
              }
          site = siteEvents.pop();
          }
​
      // remove beach section
      else if (circle) {
          this.removeBeachsection(circle.arc);
          }
​
      // all done, quit
      else {
          break;
          }
      }
​
  // wrapping-up:
  //   connect dangling edges to bounding box
  //   cut edges as per bounding box
  //   discard edges completely outside bounding box
  //   discard edges which are point-like
  this.clipEdges(bbox);
​
  //   add missing edges in order to close opened cells
  this.closeCells(bbox);
​
  // to measure execution time
  var stopTime = new Date();
​
  // prepare return values
  var diagram = new this.Diagram();
  diagram.cells = this.cells;
  diagram.edges = this.edges;
  diagram.vertices = this.vertices;
  diagram.execTime = stopTime.getTime()-startTime.getTime();
​
  // clean up
  this.reset();
​
  return diagram;
  };
​
/******************************************************************************/
​
if ( typeof module !== 'undefined' ) {
  module.exports = Voronoi;
}
​
​
​
​
function edge_centre(inhalfedge) {
  let edgecentre = {};
  edgecentre.x = inhalfedge.edge.va.x - (inhalfedge.edge.va.x - inhalfedge.edge.vb.x) / 2;
  edgecentre.y = inhalfedge.edge.va.y - (inhalfedge.edge.va.y - inhalfedge.edge.vb.y) / 2;
  return edgecentre;
}
​
function vertex_scale(a, b, inscale) {
  let scaledVertex = {};
  let pdist = dist2D(a.x, a.y, b.x, b.y)/offset
  scaledVertex.x = a.x - (a.x - b.x) / pdist;
  scaledVertex.y = a.y - (a.y - b.y) / pdist;
  return scaledVertex;
}
​
​
​
function dist2D(ix, iy, fx, fy){
  return (Math.sqrt((ix - fx)**2+(iy - fy)**2))
}
​
function setRandoms(width, height, randomMinimumDist, rnum){
    var ran = [];
  for (var i = 0; i < rnum; i++) {
    var flag;
    var nX = R.random_between(0, width);
    var nY = R.random_between(0, height);
    var triesLimit = 500;
    var tries = 0;
    if (randomMinimumDist > 0) {
      do{
        flag = false;
        nX = R.random_between(0, width);
        nY = R.random_between(0, height);
        for (var j = 0; j < ran.length; j++) {
          if(dist2D(nX, nY, ran[j].x, ran[j].y) < randomMinimumDist)
            flag = true;
        }
        tries++;
      }while(flag == true && tries <= triesLimit)
    }
    ran.push({x:nX, y:nY});
  }
    return ran;
}
​
function castVoronoi(i){
    for (var j = 0; j < vcells[i].halfedges.length; j++) {
        if (dist2D(vcells[i].halfedges[j].edge.va.x, vcells[i].halfedges[j].edge.va.y, vcells[i].halfedges[j].edge.vb.x, vcells[i].halfedges[j].edge.vb.y) < canvasSize/20) {continue;}
        if (dist2D(vcells[i].halfedges[(j+1)%vcells[i].halfedges.length].edge.va.x, vcells[i].halfedges[(j+1)%vcells[i].halfedges.length].edge.va.y, vcells[i].halfedges[(j+1)%vcells[i].halfedges.length].edge.vb.x, vcells[i].halfedges[(j+1)%vcells[i].halfedges.length].edge.vb.y) > canvasSize/20) {
          vertex(vertex_scale(edge_centre(vcells[i].halfedges[j]), cursite, cellscale).x,vertex_scale(edge_centre(vcells[i].halfedges[j]), cursite, cellscale).y * cor);
          quadraticVertex(vertex_scale(curvert[j],cursite, cellscale).x,vertex_scale(curvert[j],cursite, cellscale).y * cor,vertex_scale(edge_centre(vcells[i].halfedges[(j+1)%vcells[i].halfedges.length]), cursite, cellscale).x,vertex_scale(edge_centre(vcells[i].halfedges[(j+1)%vcells[i].halfedges.length]), cursite, cellscale).y * cor);
        }
        else {
          let nskip = 0;
          while (dist2D(vcells[i].halfedges[(j+nskip+1)%vcells[i].halfedges.length].edge.va.x, vcells[i].halfedges[(j+nskip+1)%vcells[i].halfedges.length].edge.va.y, vcells[i].halfedges[(j+nskip+1)%vcells[i].halfedges.length].edge.vb.x, vcells[i].halfedges[(j+nskip+1)%vcells[i].halfedges.length].edge.vb.y) <= canvasSize/20) {
            nskip += 1;
          }
          vertex(vertex_scale(edge_centre(vcells[i].halfedges[j]), cursite, cellscale).x,vertex_scale(edge_centre(vcells[i].halfedges[j]), cursite, cellscale).y * cor);
          quadraticVertex(vertex_scale(curvert[(j+nskip)%vcells[i].halfedges.length],cursite, cellscale).x,vertex_scale(curvert[(j+nskip)%vcells[i].halfedges.length],cursite, cellscale).y * cor,vertex_scale(edge_centre(vcells[i].halfedges[(j+nskip+1)%vcells[i].halfedges.length]), cursite, cellscale).x,vertex_scale(edge_centre(vcells[i].halfedges[(j+nskip+1)%vcells[i].halfedges.length]), cursite, cellscale).y * cor);
        }
      }
}
​
function castVertexes(i) {
    check = {x:vcells[i].halfedges[vcells[i].halfedges.length - 1].edge.va.x,y:vcells[i].halfedges[vcells[i].halfedges.length - 1].edge.vb.x}
    cursite = vcells[i].site
    curvert = [];
    for (var j = 0; j < vcells[i].halfedges.length; j++) {
      vert = {}
      if (vcells[i].halfedges[j].edge.va.x != check.x && vcells[i].halfedges[j].edge.va.x != check.y) {
        check.x = vcells[i].halfedges[j].edge.va.x;
        check.y = vcells[i].halfedges[j].edge.va.y;
        vert.x = vcells[i].halfedges[j].edge.va.x;
        vert.y = vcells[i].halfedges[j].edge.va.y;
      }
      else {
        check.x = vcells[i].halfedges[j].edge.vb.x;
        check.y = vcells[i].halfedges[j].edge.vb.y;
        vert.x = vcells[i].halfedges[j].edge.vb.x;
        vert.y = vcells[i].halfedges[j].edge.vb.y;
      }
      curvert.push(vert)
    }
}
​
function frame() {
    erase();
    beginShape();
    vertex(0, 0);
    vertex(canvasSize, 0);
    vertex(canvasSize, canvasSize);
    vertex(0, canvasSize);
    beginContour();
    vertex(canvasSize/2, canvasSize/100);
    quadraticVertex(framecor, framecor, canvasSize/100, canvasSize/2);
    quadraticVertex(framecor, canvasSize - framecor, canvasSize/2, canvasSize-canvasSize/100);
    quadraticVertex(canvasSize - framecor, canvasSize - framecor, canvasSize-canvasSize/100, canvasSize/2);
    quadraticVertex(canvasSize - framecor, framecor, canvasSize/2, canvasSize/100);
    endContour();
    endShape(CLOSE);
    noErase();
}
​
function Particle() {
    this.pos = createVector(random(width), random(height));
    this.privpos = createVector(0, 0);
    this.vel = createVector(0, 0);
    this.acc = createVector(0, 0);
    this.maxspeed = canvasSize / 400;
    this.body = createVector(0, 0);
    this.bodyl = createVector(0,0)
    this.bodyr = createVector(0,0)
  
    this.update = function(speedcoef) {
      this.vel.add(this.acc);
      this.vel.limit(this.maxspeed * speedcoef);
      this.pos.add(this.vel);
      this.acc.mult(0);
    }
  
    this.applyForce = function(force, vcoef) {
      this.acc.add(force);
      this.acc.rotate(vcoef);
    }
  
    this.show = function(sizecoef, bcolor) {
      this.body.mult(0);
      this.body.add(createVector(this.privpos.x - this.pos.x, this.privpos.y - this.pos.y));
      this.bodyl.mult(0);
      this.bodyr.mult(0);
      this.body.normalize()
      this.bodyl.add(this.body) 
      this.bodyl.rotate(90)
      this.bodyr.add(this.body) 
      this.bodyr.rotate(-90)
      this.body.mult(canvasSize/80 * sizecoef)
      this.bodyl.mult(canvasSize/400 * sizecoef)
      this.bodyr.mult(canvasSize/400 * sizecoef)
      stroke(bcolor)
      push();
      strokeWeight(canvasSize/300 * sizecoef)
      translate(this.pos.x, this.pos.y);
      line(this.bodyl.x, this.bodyl.y, this.body.x, this.body.y)
      line(this.bodyr.x, this.bodyr.y, this.body.x, this.body.y)
      pop();
      circle(this.pos.x, this.pos.y, canvasSize/400 * sizecoef);
    }
​
    this.castShadow = function(sizecoef, slen, scolor) {
      var corx = 0
      var cory = 0
      if (this.pos.x + slen > fieldSize - canvOffset) corx = -fieldSize
      if (this.pos.y + slen > fieldSize - canvOffset) cory = -fieldSize
      stroke(scolor)
      push();
      strokeWeight(canvasSize/300 * sizecoef)
      translate(this.pos.x, this.pos.y);
      line(this.bodyl.x + slen + corx, this.bodyl.y + slen + cory, this.body.x + slen + corx, this.body.y + slen + cory)
      line(this.bodyr.x + slen + corx, this.bodyr.y + slen + cory, this.body.x + slen + corx, this.body.y + slen + cory)
      pop();
      circle(this.pos.x + slen + corx, this.pos.y + slen + cory, canvasSize/400);
    }
  
    this.edges = function() {
      if (this.pos.x > fieldSize - canvOffset) this.pos.x = -canvOffset;
      if (this.pos.x < -canvOffset) this.pos.x = fieldSize -canvOffset;
      if (this.pos.y > fieldSize - canvOffset) this.pos.y = -canvOffset;
      if (this.pos.y < -canvOffset) this.pos.y = fieldSize -canvOffset;
    }
  
    this.follow = function(vectors, vcoef) {
      var x = floor((this.pos.x + canvOffset) / vscale)
      var y = floor((this.pos.y + canvOffset) / vscale)
      this.privpos.mult(0)
      this.privpos.add(this.pos)
      var index = x + y * vcols;
      var force = vectors[index];
      this.applyForce(force, vcoef);
    }
  }
​
​
​
function random_hash() {
  let chars = "0123456789abcdef";
  let result = '0x';
  for (let i = 64; i > 0; --i) result += chars[Math.floor(Math.random() * chars.length)];
  return result;
}
​
tokenData = {"hash": random_hash()}
let seed = parseInt(tokenData.hash.slice(0, 16), 16);
​
class Random {
  constructor(seed) {
  this.seed = seed
  }
  random_dec() {
  this.seed ^= this.seed << 13
  this.seed ^= this.seed >> 17
  this.seed ^= this.seed << 5
  return ((this.seed < 0 ? ~this.seed + 1 : this.seed) % 1000) / 1000
  }
  random_between(a, b) {
    return a + (b - a) * this.random_dec()
  }
  random_int(a, b) {
  return Math.floor(this.random_between(a, b+1))
  }
  random_choice(x) {
    return x[Math.floor(this.random_between(0, x.length * 0.99))]
  }
}
​
let hash = tokenData.hash
let R = new Random(seed)
​
var canvasSize = 800
var canvOffset = canvasSize/10
var fieldSize = canvasSize + canvOffset * 2
var cor = canvasSize / (canvasSize + canvasSize/2)
var framecor = canvasSize/100
​
​
​
var numcells = 50;
var vertexMinimumDist = canvasSize / 15
var offset = canvasSize / 80
​
var voronoi = new Voronoi();
var bbox = {xl: 0, xr: canvasSize, yt: 0, yb: canvasSize + canvasSize/2}; // xl is x-left, xr is x-right, yt is y-top, and yb is y-bottom
var sites = []; // {x: 200, y: 200}, {x: 50, y: 250}, {x: 400, y: 100} /* , ... */ 
​
sites = setRandoms(canvasSize, canvasSize + canvasSize/2, vertexMinimumDist, numcells);
var coloption = R.random_between(0, 50) - 30;
​
​
var diagram = voronoi.compute(sites, bbox);
var vedges = diagram.edges;
var vcells = diagram.cells;
var cursite;
var curvert;
var vert;
var check;
var cellscale = 0.8;
var sky;
var bottom;
var t1;
var t2;
var coloffset = 0.9;
​
​
var pninc = 0.05;
var vinc = 0.0003;
var vscale = 25;
var vcols, vrows;
var zoff = 0;
var speedcoef = [];
var fishgroups = R.random_between(1, 4)
var fishcount = []
var delay = []
var sinlen = []
var sinadd = []
var magnit = []
var groupCoef = []
var groupColor = []
var pnvalue = []
var v = []
var c = []
var shadow = []
​
var particles = []
var flowfield = []
var start = 0
​
for (var g = 0; g < fishgroups; g++) {
    fishcount.push(R.random_between(80 / fishgroups, 200 / fishgroups))
    sinlen.push(R.random_between(500, 1000))
    sinadd.push(R.random_between(1.5, 2))
    magnit.push(R.random_between(1, 1.8))
    groupCoef.push(R.random_between(0.8, 1.2) + g / fishgroups / 2)
    groupColor.push(R.random_between(0, 1))
    delay.push(g * 1000)
    particles.push([])
    speedcoef.push(0)
    shadow.push(canvasSize/60 * groupCoef[g])
  }
​
groupCoef.sort()
shadow.sort()
​
​
function setup() {
  createCanvas(834, 834);
  colorMode(HSB);
  var c1 = color(186 + coloption, 90, 59);
    var c2 = color(224 + coloption, 100, 19);
    colorMode(RGB)
​
    var c3 = color(160)
    var c4 = color(0)
​
  img2 = createImage(width, height)
  img2.loadPixels()
  for (let i = 0; i < width; i++) {
    for (let j = 0; j < height; j++) {
      col = color(c3.levels[0] + (c4.levels[0] - c3.levels[0])*j/canvasSize)
      img2.set(i, j, col)
    }
  }
  img2.updatePixels()
  image(img2, 0, 0)
  fill(c4)
  offset = canvasSize / 30
  for (var i = 0; i < vcells.length; i++) {
    castVertexes(i)
    beginShape();
    castVoronoi(i);
    endShape(CLOSE);
  }
  sky = get();
  sky.filter(BLUR,10)
​
  img1 = createImage(width, height)
  img1.loadPixels()
  for (let i = 0; i < width; i++) {
    for (let j = 0; j < height; j++) {
        if (j < canvasSize * coloffset) {
            col = color(c1.levels[0] + (c2.levels[0] - c1.levels[0])*j/canvasSize/coloffset,
                        c1.levels[1] + (c2.levels[1] - c1.levels[1])*j/canvasSize/coloffset, 
                        c1.levels[2] + (c2.levels[2] - c1.levels[2])*j/canvasSize/coloffset)
        }
      else {
          col = color(c2)
      }
      img1.set(i, j, col)
    }
  }
  img1.updatePixels()
  image(img1, 0, 0)
​
  fill(c2)
  offset = canvasSize / 80
  noStroke();
  beginShape();
  vertex(0, 0)
  vertex(canvasSize, 0)
  vertex(canvasSize, canvasSize)
  vertex(0, canvasSize)
  for (var i = 0; i < vedges.length; i++) {
    noStroke();
    line(vedges[i].va.x, vedges[i].va.y, vedges[i].vb.x, vedges[i].vb.y);
  }
​
  for (var i = 0; i < vcells.length; i++) {
    castVertexes(i);
    beginContour();
    castVoronoi(i);
    endContour(CLOSE);
  }
  endShape(CLOSE);
  bottom = get();
​
  frameRate(30)
  colorMode(HSB);
  var fc1 = color(206 + coloption, 27, 82)
  var fc2 = color(200 + coloption, 70, 65)
  colorMode(RGB);
  vcols = floor(fieldSize / vscale);
  vrows = floor(fieldSize / vscale);
  for (var g = 0; g < fishgroups; g++) {
    flowfield[g] = new Array(vcols * vrows);
    c.push(color((((fc2.levels[0] - fc1.levels[0]) * groupColor[g] + fc1.levels[0]) - c2.levels[0]) * (groupCoef[g] - 0.3) + c2.levels[0],
                 (((fc2.levels[1] - fc1.levels[1]) * groupColor[g] + fc1.levels[1]) - c2.levels[1]) * (groupCoef[g] - 0.3) + c2.levels[1], 
                 (((fc2.levels[2] - fc1.levels[2]) * groupColor[g] + fc1.levels[2]) - c2.levels[2]) * (groupCoef[g] - 0.3) + c2.levels[2]))
    for (var i = 0; i < fishcount[g]; i++) {
      particles[g][i] = new Particle()
      pnvalue.push(0)
      v.push(0)
    }
  }
​
  frame()
}
​
function draw() {
  translate(20, 0)
    colorMode(HSB);
    var c2 = color(224 + coloption, 100, 19);
    colorMode(RGB);
    t1 = 200 + (Math.sin(millis()/8000) + 1) * 200
    t2 = 200 + (Math.sin(millis()/1000) + 1) * 10
    blendMode(BLEND);
    image(bottom, 0, 0);
​
    push()
  noiseDetail(4, 0.2)
  for (var g = 0; g < fishgroups; g++) {
    speedcoef[g] = (noise((millis()/500)+ delay[g]) + 0.2) * 3 * (Math.sin((millis()+delay[g])/sinlen[g])+sinadd[g])
  }
  pop();
  noiseSeed(0)
  var yoff = 0;
  for (var y = 0; y < vrows; y++) {
    var xoff = 0;
    for (var x = 0; x < vcols; x++) {
      var index = x + y * vcols;
      for (var g = 0; g < fishgroups; g++) {
        pnvalue[g] = noise(xoff + delay[g], yoff + delay[g], zoff + delay[g]) * TWO_PI * 4;
        v[g] = p5.Vector.fromAngle(pnvalue[g]);
        v[g].setMag(magnit[g]);
        flowfield[g][index] = v[g];
      }
      xoff += pninc;
    }
    yoff += pninc;
    zoff += vinc;
  }
​
​
  for (var g = 0; g < fishgroups; g++) {
    for (var i = 0; i < particles[g].length; i++) {
      strokeWeight(canvasSize/200  * groupCoef[g])
      particles[g][i].follow(flowfield[g], i * 2)
      particles[g][i].update(speedcoef[g])
      particles[g][i].castShadow(groupCoef[g], shadow[g], c2)
      particles[g][i].edges()
    }
  }
​
  for (var g = 0; g < fishgroups; g++) {
    for (var i = 0; i < particles[g].length; i++) {
      strokeWeight(canvasSize/200  * groupCoef[g])
      particles[g][i].show(groupCoef[g], c[g])
    }
  }
​
    push();
    angleMode(DEGREES)
    rotate(-45)
    scale(2.5,0.5)
    blendMode(SCREEN);
    image(sky, -t1, t2);
    pop();
    frame()
    // the next lines conceal artifacts due to canvas size change
    noStroke();
    fill(255);
    rect(-27, 0, 30, height);
    rect(796, 0, 30, height);
    rect(-100, 800, width*1.2, 150);
}
  
//save JPG
let lapse = 0;    // mouse timer
function mousePressed(){
  // prevents mouse press from registering twice
  if (millis() - lapse > 400){
    save("img_" + month() + '-' + day() + '_' + hour() + '-' + minute() + '-' + second() + ".jpg");
    lapse = millis();
  }
}
​