Voronoï playground: Voronoï transitioning thanks to weighted Voronoï

.block

license: mit
border: no

README.md

This block experiments a new way to transition from one Voronoï tesselation to another.

Usually, this is achieved by smoothly changing the locations of sites from their original locations to their final locations, while recomputing the Voronoï tessellation during displacements. Here, I use weighted Voronoï diagram (the 2D additive weighted power diagram variation) to do the job. It gives a totally new feeling: the final tesselation seems to emerge from the initial one. The cherry on the cake, this technic allows to transition between tessellations of a distinct number of sites!

This block is a continuation of the experimentations 3, 2 and 1. It uses the d3-weighted-voronoi plugin.

User interactions :

• the top left slider allows you to change the relative weights of blue sites and green sites; when blue sites overweight green sites, the voronoï tessellation only consider blue sites (and vice versa)
• you can hide/show sites

Acknowledgments to :

• D3.js (v.4)
• d3-weighted-voronoi plugin
• blockbuilder.org
• mkedwards's block: Treemap

ConvexHull.js

// ConvexHull.js

var epsilon = 1E-10;

function epsilonesque(n) {
  return n === 0;
  return n >= -epsilon && n <= epsilon;
}

// IN: vectors or vertices
// OUT: dot product
var dot = function(v1, v2) {
  return (v1.x * v2.x) + (v1.y * v2.y) + (v1.z * v2.z); 
}

// IN: Face face
var Plane3D = function(face) {
  var p1 = face.verts[0];
  var p2 = face.verts[1];
  var p3 = face.verts[2];
  this.a = p1.y * (p2.z-p3.z) + p2.y * (p3.z-p1.z) + p3.y * (p1.z-p2.z);
  this.b = p1.z * (p2.x-p3.x) + p2.z * (p3.x-p1.x) + p3.z * (p1.x-p2.x);
  this.c = p1.x * (p2.y-p3.y) + p2.x * (p3.y-p1.y) + p3.x * (p1.y-p2.y);
  this.d = -1 * (p1.x * (p2.y*p3.z - p3.y*p2.z) + p2.x * (p3.y*p1.z - p1.y*p3.z) + p3.x * (p1.y*p2.z - p2.y*p1.z));	
}

// OUT: int2D
Plane3D.prototype.getDualPointMappedToPlane = function() {
  var nplane = this.getNormZPlane();
  var dualPoint = new Point2D(nplane[0]/2, nplane[1]/2);
  return dualPoint;
}

Plane3D.prototype.getNormZPlane = function() {
  return [
    -1 * (this.a / this.c),
    -1 * (this.b / this.c),
    -1 * (this.d / this.c)
  ];
}

// IN: doubles x and y
var Point2D = function(x, y) {
  this.x = x;
  this.y = y;
}


var ConflictListNode = function(face, vert) {
  this.face = face;
  this.vert = vert;
  this.nextf = null;
  this.prevf = null;
  this.nextv = null;
  this.prevv = null;
}

// IN: boolean forFace
var ConflictList = function(forFace) {
  this.forFace = forFace;
  this.head = null;
}

// IN: ConflictListNode cln
ConflictList.prototype.add = function(cln) {
  if (this.head === null) {
    this.head = cln;
  } else {
    if (this.forFace) {  // Is FaceList
      this.head.prevv = cln;
      cln.nextv = this.head;
      this.head = cln;
    } else {  // Is VertexList
      this.head.prevf = cln;
      cln.nextf = this.head;
      this.head = cln;
    }
  }
}

ConflictList.prototype.isEmpty = function() {
  return this.head === null;
}

// Array of faces visible
ConflictList.prototype.fill = function(visible) {
  if (this.forFace) {
    return;
  }
  var curr = this.head;
  do {
    visible.push(curr.face);
    curr.face.marked = true;
    curr = curr.nextf;
  } while (curr !== null);
}

ConflictList.prototype.removeAll = function() {
  if (this.forFace) {  // Remove all vertices from Face
    var curr = this.head;
    do {
      if (curr.prevf === null) {  // Node is head
        if (curr.nextf === null) {
          curr.vert.conflicts.head = null;
        } else {
          curr.nextf.prevf = null;
          curr.vert.conflicts.head = curr.nextf;
        }
      } else {  // Node is not head
        if (curr.nextf != null) {
          curr.nextf.prevf = curr.prevf;
        }
        curr.prevf.nextf = curr.nextf;
      }
      curr = curr.nextv;
      if (curr != null) {
        curr.prevv = null;
      }
    } while (curr != null);
  } else {  // Remove all JFaces from vertex
    var curr = this.head;
    do {
      if (curr.prevv == null) {  // Node is head
        if (curr.nextv == null) {
          curr.face.conflicts.head = null;
        } else {
          curr.nextv.prevv = null;
          curr.face.conflicts.head = curr.nextv;
        }
      } else {  // Node is not head
        if (curr.nextv != null) {
          curr.nextv.prevv = curr.prevv;
        }
        curr.prevv.nextv = curr.nextv;
      }
      curr = curr.nextf;
      if (curr != null)
        curr.prevf = null;
    } while (curr != null);
  }
}

// IN: list of vertices
ConflictList.prototype.getVertices = function() {
  var list = [],
  		curr = this.head;
  while (curr !== null) {
    list.push(curr.vert);
    curr = curr.nextv;
  }
  return list;
}

// IN: coordinates x, y, z
var Vertex = function(x, y, z, weight, orig, isDummy) {
  this.x = x;
  this.y = y;
  this.weight = epsilon;
  this.index = 0;
  this.conflicts = new ConflictList(false);
  this.neighbours = null;  // Potential trouble
  this.nonClippedPolygon = null;
  this.polygon = null;
  this.originalObject = null;
  this.isDummy = false;

  if (orig !== undefined) {
    this.originalObject = orig;
  }
  if (isDummy != undefined) {
    this.isDummy = isDummy;
  }
  if (weight != null) {
    this.weight = weight;
  }
  if (z != null) {
    this.z = z;
  } else {
    this.z = this.projectZ(this.x, this.y, this.weight);
  }
}

Vertex.prototype.setWeight = function(weight) {
  this.weight = weight;
  this.z = this.projectZ(this.x, this.y, this.weight);
}

Vertex.prototype.projectZ = function(x, y, weight) {
  return ((x*x) + (y*y) - weight);
}

Vertex.prototype.subtract = function(v) {
  return new Vertex(v.x - this.x, v.y - this.y, v.z - this.z);
}

Vertex.prototype.crossproduct = function(v) {
  return new Vertex((this.y * v.z) - (this.z * v.y), (this.z * v.x) - (this.x * v.z), (this.x * v.y) - (this.y * v.x));
}

Vertex.prototype.equals = function(v) {
  return (this.x === v.x && this.y === v.y && this.z === v.z);
}

// IN: coordinates x, y, z
var Vector = function(x, y, z) {
  this.x = x;
  this.y = y;
  this.z = z;
}

Vector.prototype.negate = function() {
  this.x *= -1;
  this.y *= -1;
  this.z *= -1;
}

// Normalizes X Y and Z in-place
Vector.prototype.normalize = function() {
  var len = Math.sqrt((this.x * this.x) + (this.y * this.y) + (this.z * this.z));
  if (len > 0) {
    this.x /= len;
    this.y /= len;
    this.z /= len;
  }
}

// IN: Vertices a, b, c
var Face = function(a, b, c, orient) {
  this.conflicts = new ConflictList(true);
  this.verts = [a, b, c];
  this.marked = false;
  var t = (a.subtract(b)).crossproduct(b.subtract(c));

  this.normal = new Vector(-t.x, -t.y, -t.z);
  this.normal.normalize();
  this.createEdges();
  this.dualPoint = null;

  if (orient != undefined) {
    this.orient(orient);
  }
}

// OUT: Point2D
Face.prototype.getDualPoint = function() {
  if (this.dualPoint == null) {
    var plane3d = new Plane3D(this);
    this.dualPoint = plane3d.getDualPointMappedToPlane();
  }
  return this.dualPoint;
}

Face.prototype.isVisibleFromBelow = function() {
  return (this.normal.z < -1.4259414393190911E-9);
}

Face.prototype.createEdges = function() {
  this.edges = [];
  this.edges[0] = new HEdge(this.verts[0], this.verts[1], this);
  this.edges[1] = new HEdge(this.verts[1], this.verts[2], this);
  this.edges[2] = new HEdge(this.verts[2], this.verts[0], this);
  this.edges[0].next = this.edges[1];
  this.edges[0].prev = this.edges[2];
  this.edges[1].next = this.edges[2];
  this.edges[1].prev = this.edges[0];
  this.edges[2].next = this.edges[0];
  this.edges[2].prev = this.edges[1];
}

// IN: vertex orient
Face.prototype.orient = function(orient) {
  if (!(dot(this.normal,orient) < dot(this.normal, this.verts[0]))){
    var temp = this.verts[1];
    this.verts[1] = this.verts[2];
    this.verts[2] = temp;
    this.normal.negate();
    this.createEdges();
  }
}

// IN: two vertices v0 and v1
Face.prototype.getEdge = function(v0, v1) {
  for (var i = 0; i < 3; i++) {
    if (this.edges[i].isEqual(v0, v1)) {
      return this.edges[i];
    }
  }
  return null;
}

// IN: Face face, vertices v0 and v1
Face.prototype.link = function(face, v0, v1) {
  if (face instanceof Face) {
    var twin = face.getEdge(v0, v1);
    if (twin === null) {

      console.log("ERROR: twin is null");
    }
    var edge = this.getEdge(v0, v1);
    twin.twin = edge;
    edge.twin = twin;
  } else {
    var e = face;
    var edge = this.getEdge(e.orig, e.dest);
    e.twin = edge;
    edge.twin = e;
  }
}

// IN: vertex v
Face.prototype.conflict = function(v) {
  return (dot(this.normal, v) > dot(this.normal, this.verts[0]) + epsilon);
}

Face.prototype.getHorizon = function() {
  for (var i = 0; i < 3; i++) {
    if (this.edges[i].twin !== null && this.edges[i].twin.isHorizon()) {
      return this.edges[i];
    }
  }
  return null;
}

Face.prototype.removeConflict = function() {
  this.conflicts.removeAll();
}

// IN: vertex orig, vertex dest, Face face
var HEdge = function(orig, dest, face) {
  this.next = null;
  this.prev = null;
  this.twin = null;
  this.orig = orig;
  this.dest = dest;
  this.iFace = face;
}

HEdge.prototype.isHorizon = function() {
  return this.twin !== null && this.twin.iFace.marked && !this.iFace.marked;
}

// IN: array horizon
HEdge.prototype.findHorizon = function(horizon) {
  if (this.isHorizon()) {
    if (horizon.length > 0 && this === horizon[0]) {
      return;
    } else {
      horizon.push(this);
      this.next.findHorizon(horizon);
    }
  } else {
    if (this.twin !== null) {
      this.twin.next.findHorizon(horizon);
    }
  }
}

// IN: vertices origin and dest
HEdge.prototype.isEqual = function(origin, dest) {
  return ((this.orig.equals(origin) && this.dest.equals(dest)) || (this.orig.equals(dest) && this.dest.equals(origin)));
}

var ConvexHull = {
  points: [],
  facets: [],
  created: [],
  horizon: [],
  visible: [],
  current: 0,

  // IN: sites (x,y,z)
  init: function(boundingSites, sites) {
    this.points = [];
    for (var i = 0; i < sites.length; i++) {
      this.points[i] = new Vertex(sites[i].x, sites[i].y, sites[i].z, null, sites[i], false);
    }
    this.points = this.points.concat(boundingSites);
  },

  permutate: function() {
    var pointSize = this.points.length;
    for (var i = pointSize -1; i > 0; i--) {
      var ra = Math.floor(Math.random() * i);
      var temp = this.points[ra];
      temp.index = i;
      var currentItem = this.points[i];
      currentItem.index = ra;
      this.points.splice(ra, 1, currentItem);
      this.points.splice(i, 1, temp);
    }
  },

  prep: function() {
    if (this.points.length <= 3) {
      console.log("ERROR: Less than 4 points");
    }
    for (var i = 0; i < this.points.length; i++) {
      this.points[i].index = i;
    }

    var v0, v1, v2, v3;
    var f1, f2, f3, f0;
    v0 = this.points[0];
    v1 = this.points[1];
    v2 = v3 = null;

    for (var i = 2; i < this.points.length; i++) {
      if (!(this.linearDependent(v0, this.points[i]) && this.linearDependent(v1, this.points[i]))) {
        v2 = this.points[i];
        v2.index = 2;
        this.points[2].index = i;
        this.points.splice(i, 1, this.points[2]);
        this.points.splice(2, 1, v2);
        break;
      }
    }
    if (v2 === null) {
      console.log("ERROR: v2 is null");
    }

    f0 = new Face(v0, v1, v2);
    for (var i = 3; i < this.points.length; i++) {
      if (dot(f0.normal, f0.verts[0]) !== dot(f0.normal, this.points[i])) {
        v3 = this.points[i];
        v3.index = 3;
        this.points[3].index = i;
        this.points.splice(i, 1, this.points[3]);
        this.points.splice(3, 1, v3);
        break;
      }
    }
    if (v3 === null) {
      console.log("ERROR: v3 is null");
    }

    f0.orient(v3);
    f1 = new Face(v0, v2, v3, v1);
    f2 = new Face(v0, v1, v3, v2);
    f3 = new Face(v1, v2, v3, v0);
    this.addFacet(f0);
    this.addFacet(f1);
    this.addFacet(f2);
    this.addFacet(f3);
    // Connect facets
    f0.link(f1, v0, v2);
    f0.link(f2, v0, v1);
    f0.link(f3, v1, v2);
    f1.link(f2, v0, v3);
    f1.link(f3, v2, v3);
    f2.link(f3, v3, v1);
    this.current = 4;

    var v;
    for (var i = this.current; i < this.points.length; i++) {
      v = this.points[i];
      if (f0.conflict(v)) {
        this.addConflict(f0, v);
      }
      if (f1.conflict(v)) {
        this.addConflict(f1, v);
      }
      if (f2.conflict(v)) {
        this.addConflict(f2, v);
      }
      if (f3.conflict(v)) {
        this.addConflict(f3,v);
      }
    }
  },

  // IN: Faces old1 old2 and fn
  addConflicts: function(old1, old2, fn) {
    var l1 = old1.conflicts.getVertices();
    var l2 = old2.conflicts.getVertices();
    var nCL = [];
    var v1, v2;
    var i, l;
    i = l = 0;
    // Fill the possible new Conflict List
    while (i < l1.length || l < l2.length) {
      if (i < l1.length && l < l2.length) {
        v1 = l1[i];
        v2 = l2[l];
        // If the index is the same, it's the same vertex and only 1 has to be added
        if (v1.index === v2.index) {
          nCL.push(v1);
          i++;
          l++;
        } else if (v1.index > v2.index) {
          nCL.push(v1);
          i++;
        } else {
          nCL.push(v2);
          l++;
        }
      } else if ( i < l1.length) {
        nCL.push(l1[i++]);
      } else {
        nCL.push(l2[l++]);
      }
    }
    // Check if the possible conflicts are real conflicts
    for (var i = nCL.length - 1; i >= 0; i--) {
      v1 = nCL[i];
      if (fn.conflict(v1))
        this.addConflict(fn, v1);
    }
  },

  // IN: Face face, Vertex v
  addConflict: function(face, vert) {
    var e = new ConflictListNode(face, vert);
    face.conflicts.add(e);
    vert.conflicts.add(e);
  },

  // IN: Face f
  removeConflict: function(f) {
    f.removeConflict();
    var index = f.index;
    f.index = -1;
    if (index === this.facets.length - 1) {
      this.facets.splice(this.facets.length - 1, 1);
      return;
    }
    if (index >= this.facets.length || index < 0)
      return;
    var last = this.facets.splice(this.facets.length - 1, 1);
    last[0].index = index;
    this.facets.splice(index, 1, last[0]);
  },

  // IN: Face face
  addFacet: function(face) {
    face.index = this.facets.length;
    this.facets.push(face);
  },

  compute: function() {
    this.prep();
    while (this.current < this.points.length) {
      var next = this.points[this.current];
      if (next.conflicts.isEmpty()) {  // No conflict, point in hull
        this.current++;
        continue;
      }
      this.created = [];  // TODO: make sure this is okay and doesn't dangle references
      this.horizon = [];
      this.visible = [];
      // The visible faces are also marked
      next.conflicts.fill(this.visible);
      // Horizon edges are orderly added to the horizon list
      var e;
      for (var jF = 0; jF < this.visible.length; jF++) {
        e = this.visible[jF].getHorizon();
        if (e !== null) {
          e.findHorizon(this.horizon);
          break;
        }
      }
      var last = null, first = null;
      // Iterate over horizon edges and create new faces oriented with the marked face 3rd unused point
      for (var hEi = 0; hEi < this.horizon.length; hEi++) {
        var hE = this.horizon[hEi];
        var fn = new Face(next, hE.orig, hE.dest, hE.twin.next.dest);
        fn.conflicts = new ConflictList(true);
        // Add to facet list
        this.addFacet(fn);
        this.created.push(fn);
        // Add new conflicts
        this.addConflicts(hE.iFace, hE.twin.iFace, fn);
        // Link the new face with the horizon edge
        fn.link(hE);
        if (last !== null)
          fn.link(last, next, hE.orig);
        last = fn;
        if (first === null)
          first = fn;
      }
      // Links the first and the last created JFace
      if (first !== null && last !== null) {
        last.link(first, next, this.horizon[0].orig);
      }
      if (this.created.length != 0) {
        // update conflict graph
        for (var f = 0; f < this.visible.length; f++) {
          this.removeConflict(this.visible[f]);
        }
        this.current++;
        this.created = [];
      }
    }
    return this.facets;
  },

  // IN: two vertex objects, p1 and p2
  // OUT: true if they are linearly dependent, false otherwise
  linearDependent: function(p1, p2) {
    if (p1.x == 0 && p2.x == 0) {
      if (p1.y == 0 && p2.y == 0) {
        if (p1.z == 0 && p2.z == 0) {
          return true;
        }
        if (p1.z == 0 || p2.z == 0) {
          return false;
        }
        return true;
      }
      if (p1.y == 0 || p2.y == 0) {
        return false;
      }
      if (epsilonesque(p1.z/p1.y - p2.z/p2.y)) {
        return true;
      } else {
        return false;
      }
    }
    if (p1.x == 0 || p2.x == 0) {
      return false;
    }
    if (epsilonesque(p1.y/p1.x - p2.y/p2.x) && epsilonesque(p1.z/p1.x - p2.y/p2.x)) {
      return true;
    } else {
      return false;
    }
  },

  clear: function() {
    this.points = [];
    this.facets = [];
    this.created = [];
    this.horizon = [];
    this.visible = [];
    this.current = 0;
  }
}

d3-polygon-clip.js

// Version 0.0.0. Copyright 2017 Mike Bostock.
(function (global, factory) {
  typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
  typeof define === 'function' && define.amd ? define(['exports'], factory) :
  (factory((global.d3 = global.d3 || {})));
}(this, function (exports) { 'use strict';

  // Clips the specified subject polygon to the specified clip polygon;
  // requires the clip polygon to be counterclockwise and convex.
  // https://en.wikipedia.org/wiki/Sutherland–Hodgman_algorithm
  exports.polygonClip = function(clip, subject) {
    var input,
        closed = polygonClosed(subject),
        i = -1,
        n = clip.length - polygonClosed(clip),
        j,
        m,
        a = clip[n - 1],
        b,
        c,
        d;

    while (++i < n) {
      input = subject.slice();
      subject.length = 0;
      b = clip[i];
      c = input[(m = input.length - closed) - 1];
      j = -1;
      while (++j < m) {
        d = input[j];
        if (polygonInside(d, a, b)) {
          if (!polygonInside(c, a, b)) {
            subject.push(polygonIntersect(c, d, a, b));
          }
          subject.push(d);
        } else if (polygonInside(c, a, b)) {
          subject.push(polygonIntersect(c, d, a, b));
        }
        c = d;
      }
      if (closed) subject.push(subject[0]);
      a = b;
    }

    return subject;
  };

  function polygonInside(p, a, b) {
    return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
  }

  // Intersect two infinite lines cd and ab.
  function polygonIntersect(c, d, a, b) {
    var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3,
        y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3,
        ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
    return [x1 + ua * x21, y1 + ua * y21];
  }

  // Returns true if the polygon is closed.
  function polygonClosed(coordinates) {
    var a = coordinates[0],
        b = coordinates[coordinates.length - 1];
    return !(a[0] - b[0] || a[1] - b[1]);
  }

  Object.defineProperty(exports, '__esModule', {value: true});
}));

index.html

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>Voronoï playground: Voronoï transitioning thanks to weighted Voronoï</title>
    <meta name="description" content="Transitioning from one Voronoï tessellation to another thanks to Weighted Voronoï, using D3.js and the d3-weighted-voronoi plugin">
    <script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script>
    <script src="https://rawcdn.githack.com/Kcnarf/d3-weighted-voronoi/v1.0.0/build/d3-weighted-voronoi.js"></script>
    
    <style>
      #wip {
        display: none;
        position: absolute;
        top: 200px;
        left: 330px;
        font-size: 40px;
        text-align: center;
      }


      .control {
        position: absolute;
        top: 5px;
      }
      .control#control-0 {
        left: 5px;
        text-align: center;
      }
      .control#control-1 {
        left: 5px;
        top: 25px;
      }
      .control#control-2 {
        right: 460px;
        top: 25px;
      }
      .control span {
        width: 100px;
      }
      .control input[type="range"] {
        width: 210px;
      }

      svg {
        position: absolute;
        top: 25px;
        left: 15px;
        margin: 1px;
        border-radius: 1000px;
        box-shadow: 2px 2px 6px grey;
      }


      #site-container {
        clip-path: url("#clipper");
      }
      .seed {
        fill: steelblue;
      }
      .seed.group-green {
        fill: lightgreen;
      }
      .seed.hide {
        display: none;
      }


      .cell {
        fill-opacity: 0.1;
        fill: lightsteelBlue;
        stroke: lightsteelBlue;
      }
      .cell.group-green {
        fill: lightgreen;
        stroke: lightgreen;
      }
    </style>
  </head>
  <body>

    <svg>
      <defs>
        <clipPath id="clipper">
          <rect x="0" y="0" width="960" height="500" />
        </clipPath>
      </defs>
      <g id="drawing-area">
        <g id="cell-container"></g>
        <g id="site-container"></g>
      </g>
    </svg>
    
    <div id="control-0" class="control">
      <span>Voronoï of blue sites</span>
      <input id="weight" type="range" name="points" min="-5000" max="5000" value="0" oninput="weightUpdated()">
      <span>Voronoï of green sites</span>
    </div>
    <div id="control-1" class="control">
      <span>Show blue sites</span>
      <input id="weight" type="checkbox" name="showSites" onchange="blueSiteVisibilityUpdated()">
    </div>
    <div id="control-2" class="control">
      <input id="weight" type="checkbox" name="showSites" onchange="greenSiteVisibilityUpdated()">
      <span>Show green sites</span>
    </div>

    <div id="wip">
      Work in progress ...
    </div>
  </body>

  <script>
    var WITH_TRANSITION = true;
    var WITHOUT_TRANSITION = false;
    var duration = 250;
    var _2PI = 2*Math.PI;

    //begin: layout conf.
    var totalHeight = 500,
        controlsHeight = 30,
        svgRadius = (totalHeight-controlsHeight)/2,
        svgbw = 1, //svg border width
        svgHeight = 2*svgRadius,
    		svgWidth = 2*svgRadius,
        radius = svgRadius-svgbw,
        width = 2*svgRadius,
        height = 2*svgRadius,
        halfRadius = radius/2
        halfWidth = halfRadius,
        halfHeight = halfRadius,
        quarterRadius = radius/4;
        quarterWidth = quarterRadius,
        quarterHeight = quarterRadius;
    //end: layout conf.

    //begin: voronoi stuff definitions
    var siteCount = 120,
        quarterSiteCount = siteCount/4;
    var blueSites = [],
        greenSites = [];
    var baseWeight = 10000,
        x, y;
    for (i=0; i<quarterSiteCount; i++) {
      //use (x,y) instead of (r,a) for a better uniform (ie. less centered) placement of sites
      x = width*Math.random();
      y = height*Math.random();
      while (Math.sqrt(Math.pow(x-radius,2)+Math.pow(y-radius,2))>radius) {
        x = width*Math.random();
      	y = height*Math.random();
      }
      blueSites.push({index: i, group: "blue", x: x, y: y, weight: baseWeight});
      
      [0,1,2].forEach(function () {
        x = width*Math.random();
        y = height*Math.random();
        while (Math.sqrt(Math.pow(x-radius,2)+Math.pow(y-radius,2))>radius) {
          x = width*Math.random();
          y = height*Math.random();
        }
        greenSites.push({index: i+siteCount, group: "green", x: x, y: y, weight: baseWeight});
      })
    }
    var	sites = blueSites.concat(greenSites);
    var clippingPolygon = [[0,0], [0,height], [width,height], [width,0]];
    var weightedVoronoi = d3.weightedVoronoi().clip(clippingPolygon);
    var cells = sites.map(function(s){ return []; });	// stores, for each site, each cell's verteces
    //end: voronoi stuff definitions

    //begin: utilities
    var cellLiner = d3.line()
    .x(function(d){ return d[0]; })
    .y(function(d){ return d[1]; });
    //end: utilities

    //begin: reusable d3-selections
    var svg = d3.select("svg"),
        clipper = d3.select("#clipper>rect"),
        drawingArea = d3.select("#drawing-area"),
        cellContainer = d3.select("#cell-container"),
        siteContainer = d3.select("#site-container");
    //end: reusable d3-selections

    //begin: user interaction handlers
    function weightUpdated() {
      var deltaWeight,
          newBlueWeigth,
          newGreenWeight;
      deltaWeight = +d3.select("#control-0 input").node().value;
      newBlueWeigth = baseWeight - deltaWeight;
      newGreenWeight = baseWeight + deltaWeight;

      blueSites.forEach(function(s){ s.weight = newBlueWeigth });
      greenSites.forEach(function(s){ s.weight = newGreenWeight });
      computeAllCells();

      redrawAllCells(WITHOUT_TRANSITION);
    }
    
    function blueSiteVisibilityUpdated() {
      visibility = d3.select("#control-1 input").node().checked? 1:0;
      redrawGroup("blue", visibility , WITH_TRANSITION);
    }
    
    function greenSiteVisibilityUpdated() {
      visibility = d3.select("#control-2 input").node().checked? 1:0;
      redrawGroup("green", visibility, WITH_TRANSITION);
    }
    //end: user interaction handlers

    computeAllCells();

    initLayout();
    redrawAllCells(WITHOUT_TRANSITION);

    /***************/
    /* Computation */
    /***************/

    function computeAllCells() {
      cells = weightedVoronoi(sites);
    }

    /***********/
    /* Drawing */
    /***********/

    //redraw group = show/hide sites of particular group
    function redrawGroup(color, finalOpacity, withTransition) {
      siteContainer.selectAll(".seed").filter(function(d){ return d.group === color; })
        .transition()
          .duration(withTransition? duration : 0)
          .attr("opacity", finalOpacity);
    }

    function redrawAllCells(withTransition) {
			var cellSelection = cellContainer.selectAll(".cell")
        .data(cells, function(c){ return c.site.originalObject.index; });
      
      cellSelection.enter()
        .append("path")
          .attr("class", function(d){ return "group-"+d.site.originalObject.group; })
          .classed("cell", true)
          .attr("id", function(d,i){ return "cell-"+d.site.originalObject.index; })
      	.merge(cellSelection)
      		.transition()
            .duration(withTransition? duration : 0)
            .attr("d", function(d){ return cellLiner(d)+"z"; });
      
      cellSelection.exit().remove();
    }

    function initLayout () {
      svg.attr("width", svgWidth)
        .attr("height", svgHeight);

      clipper.attr("x", 0)
        .attr("y", 0)
        .attr("width", width)
        .attr("height", height);

      drawingArea.attr("width", width)
        .attr("height", height)
        .attr("transform", "translate("+[svgbw, svgbw]+")");

      //begin: draw sites
      var drawnSites = siteContainer.selectAll(".site")
      .data(sites)
      .enter()
        .append("g")
          .attr("id", function(d){ return "site-"+d.index})
          .classed("site", true);
      drawnSites.append("circle")
        .attr("id", function(d,i){ return "seed-"+i; })
        .attr("class", function(d){ return "group-"+d.group; })
        .classed("seed", true)
        .attr("r", 2)
      	.attr("opacity", 0)
      	.attr("transform", function(d){ return "translate("+[d.x,d.y]+")"; });;
      //end: draw sites

      //begin: draw cells
      cellContainer.selectAll(".cell")
        .data(cells)
        .enter()
        .append("path")
        .attr("class", function(d){ return "group-"+d.site.originalObject.group; })
        .classed("cell", true)
        .attr("id", function(d,i){ return "cell-"+d.site.originalObject.index; });
      //end: draw cells
    }
  </script>
</html>

PowerDiagram.js

// PowerDiagram.js - computePowerDiagramIntegrated() and subroutines

// IN: HEdge edge
function getFacesOfDestVertex(edge) {
  var faces = [];
  var previous = edge;
  var first = edge.dest;
  var site = first.originalObject;
  var neighbours = [];
  do {
    previous = previous.twin.prev;
    var siteOrigin = previous.orig.originalObject;
    if (!siteOrigin.isDummy) {
      neighbours.push(siteOrigin);
    }
    var iFace = previous.iFace;
    if (iFace.isVisibleFromBelow()) {
      faces.push(iFace);
    }
  } while (previous !== edge);
  site.neighbours = neighbours;
  return faces;
}

// IN: Omega = convex bounding polygon
// IN: S = unique set of sites with weights
// OUT: Set of lines making up the voronoi power diagram
function computePowerDiagramIntegrated(sites, boundingSites, clippingPolygon) {
  ConvexHull.clear();
  ConvexHull.init(boundingSites, sites);

  var facets = ConvexHull.compute(sites);
  var polygons = [];
  var vertexCount = ConvexHull.points.length; 
  var verticesVisited = [];
  var facetCount = facets.length;

  for (var i = 0; i < facetCount; i++) {
    var facet = facets[i];
    if (facet.isVisibleFromBelow()) {
      for (var e = 0; e < 3; e++) {
        // go through the edges and start to build the polygon by going through the double connected edge list
        var edge = facet.edges[e];
        var destVertex = edge.dest;
        var site = destVertex.originalObject; 

        if (!verticesVisited[destVertex.index]) {
          verticesVisited[destVertex.index] = true;
          if (site.isDummy) {
            // Check if this is one of the sites making the bounding polygon
            continue;
          }
          // faces around the vertices which correspond to the polygon corner points
          var faces = getFacesOfDestVertex(edge);
          var protopoly = [];
          var lastX = null;
          var lastY = null;
          var dx = 1;
          var dy = 1;
          for (var j = 0; j < faces.length; j++) {
            var point = faces[j].getDualPoint();
            var x1 = point.x;
            var y1 = point.y;
            if (lastX !== null) {
              dx = lastX - x1;
              dy = lastY - y1;
              if (dx < 0) {
                dx = -dx;
              }
              if (dy < 0) {
                dy = -dy;
              }
            }
            if (dx > epsilon || dy > epsilon) {
              protopoly.push([x1, y1]);
              lastX = x1;
              lastY = y1;
            }
          }
          
          site.nonClippedPolygon = protopoly.reverse();
          if (!site.isDummy && d3.polygonLength(site.nonClippedPolygon) > 0) {
            var clippedPoly = d3.polygonClip(clippingPolygon, site.nonClippedPolygon);
            site.polygon = clippedPoly;
            clippedPoly.site = site;
            if (clippedPoly.length > 0) {
              polygons.push(clippedPoly);
            }
          }
        }
      }
    }
  }
  return polygons;
}

thumbnail.png