Weighted Voronoi Treemap in D3v4

.block

license: mit
height: 1000

README.md

Port of mkedwards's block: Treemap in D3v4.

Warning not stable. Sometimes, code fails to compute the layout, and doesn't update the svg. In such a case, you have to (re-)compute diagram.

Done

• add d3-polygon-clip.js (no longer in D3v4)
• add d3-rebind.js (no longer in D3v4)
• use d3.polygoneArea(poly), d3.polygonLength(poly) and d3.polygonCentroid(poly) (instead of respectively poly.area(), poly.length() and poly.centroid())
• use d3.scaleLinear(), d3.scaleOrdinal(d3.schemeCategory20c) (instead of respectively d3.scale.linear(), d3.scale.categories20())
• in function paint(), rework painting order of polygons for a better perception of each partition (strokes no longer overlap each others, so that the stroke of a partition is consistant all over it's perimeter)
• the result of d3v3.layout.hierarchy() was an array of nodes (each with their respective descendants), but the result of d3v4.hierarchy() is the root node; hence this huge change may have unseen impacts (or can lead to futher refactoring, but this is not the point here); current seen impact is on paint() function
• add a label.json file, with a very simple hierarchy, for debug purposes

On-going issues

• sometimes, code fails to compute the layout, and doesn't update the svg; console shows a Cannot set property 'twin' of null error; this error was already part of the original block, and I don't found the root cause ...
• don't understand what I'm doing with d3_layout_hierarchyRebind (in voronoiTreemapD3.js)

Original README

A treemap recursively subdivides area into rectangles; the area of any node in the tree corresponds to its value. This example uses color to encode different packages of the Flare visualization toolkit. Treemap design invented by Ben Shneiderman. Squarified algorithm by Bruls, Huizing and van Wijk. Data courtesy Jeff Heer.

forked from Kcnarf's block: Weighted Voronoi Treemap in D3v4

activity.csv

ConvexHull.js

// ConvexHull.js

var epsilon = 1E-10;

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

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

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

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

// Array of faces visible
ConflictList.prototype.fill = function(visible) {
    if (this.face) {
    	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.face) {  // 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.getList().head = null;
		        } else {
        		    curr.nextv.prevv = null;
		            curr.face.getList().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(l1) {
    curr = this.head;
    while (curr !== null) {
	    l1.push(curr.vert);
	    curr = curr.nextv;
    }
    return l1;
}

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

    if (orig == undefined) {
        this.originalObject = null;
    } else {
        this.originalObject = orig;
    }
    if (isDummy != undefined) {
        this.isDummy = isDummy;
    } else {
        this.isDummy = false;
    }
    if (weight != null) {
        this.weight = weight;
    } else {
        this.weight = epsilon;        
    }
    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 GraphEdge = function(face, vert) {
    this.face = face;
    this.vert = vert;
    this.nextf = null;
    this.prevf = null;
    this.nextv = null;
    this.prevv = null;
}

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(l1);
    	var l2 = [];
        old2.conflicts.getVertices(l2);
	    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 GraphEdge(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.empty()) {  // 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;
                }
            }
            if (p1.y == 0 || p2.y == 0) {
                return false;
            }
            if (p1.z/p1.y >= p2.z/p2.y - epsilon && p1.z/p1.y <= p2.z/p2.y + epsilon) {
                return true;
            } else {
                return false;
            }
        }
        if (p1.x == 0 || p1.x == 0) {
            return false;
        }
        if (p1.y/p1.x <= p2.y/p2.x + epsilon && p1.y/p1.x >= p2.y/p2.x - epsilon
            && p1.z/p1.x >= p2.y/p2.x - epsilon && p1.z/p1.x <= p2.z/p2.x + epsilon) {
            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});
}));

d3-rebind.js

// Copies a variable number of methods from source to target.
d3.rebind = function(target, source) {
  var i = 1, n = arguments.length, method;
  while (++i < n) target[method = arguments[i]] = d3_rebind(target, source, source[method]);
  return target;
};

// Method is assumed to be a standard D3 getter-setter:
// If passed with no arguments, gets the value.
// If passed with arguments, sets the value and returns the target.
function d3_rebind(target, source, method) {
  return function() {
    var value = method.apply(source, arguments);
    return value === source ? target : value;
  };
}

flare.json

{
 "name": "flare",
 "children": [
  {
   "name": "analytics",
   "children": [
    {
     "name": "cluster",
     "children": [
      {"name": "AgglomerativeCluster", "size": 3938},
      {"name": "CommunityStructure", "size": 3812},
      {"name": "HierarchicalCluster", "size": 6714},
      {"name": "MergeEdge", "size": 743}
     ]
    },
    {
     "name": "graph",
     "children": [
      {"name": "BetweennessCentrality", "size": 3534},
      {"name": "LinkDistance", "size": 5731},
      {"name": "MaxFlowMinCut", "size": 7840},
      {"name": "ShortestPaths", "size": 5914},
      {"name": "SpanningTree", "size": 3416}
     ]
    },
    {
     "name": "optimization",
     "children": [
      {"name": "AspectRatioBanker", "size": 7074}
     ]
    }
   ]
  },
  {
   "name": "animate",
   "children": [
    {"name": "Easing", "size": 17010},
    {"name": "FunctionSequence", "size": 5842},
    {
     "name": "interpolate",
     "children": [
      {"name": "ArrayInterpolator", "size": 1983},
      {"name": "ColorInterpolator", "size": 2047},
      {"name": "DateInterpolator", "size": 1375},
      {"name": "Interpolator", "size": 8746},
      {"name": "MatrixInterpolator", "size": 2202},
      {"name": "NumberInterpolator", "size": 1382},
      {"name": "ObjectInterpolator", "size": 1629},
      {"name": "PointInterpolator", "size": 1675},
      {"name": "RectangleInterpolator", "size": 2042}
     ]
    },
    {"name": "ISchedulable", "size": 1041},
    {"name": "Parallel", "size": 5176},
    {"name": "Pause", "size": 449},
    {"name": "Scheduler", "size": 5593},
    {"name": "Sequence", "size": 5534},
    {"name": "Transition", "size": 9201},
    {"name": "Transitioner", "size": 19975},
    {"name": "TransitionEvent", "size": 1116},
    {"name": "Tween", "size": 6006}
   ]
  },
  {
   "name": "data",
   "children": [
    {
     "name": "converters",
     "children": [
      {"name": "Converters", "size": 721},
      {"name": "DelimitedTextConverter", "size": 4294},
      {"name": "GraphMLConverter", "size": 9800},
      {"name": "IDataConverter", "size": 1314},
      {"name": "JSONConverter", "size": 2220}
     ]
    },
    {"name": "DataField", "size": 1759},
    {"name": "DataSchema", "size": 2165},
    {"name": "DataSet", "size": 586},
    {"name": "DataSource", "size": 3331},
    {"name": "DataTable", "size": 772},
    {"name": "DataUtil", "size": 3322}
   ]
  },
  {
   "name": "display",
   "children": [
    {"name": "DirtySprite", "size": 8833},
    {"name": "LineSprite", "size": 1732},
    {"name": "RectSprite", "size": 3623},
    {"name": "TextSprite", "size": 10066}
   ]
  },
  {
   "name": "flex",
   "children": [
    {"name": "FlareVis", "size": 4116}
   ]
  },
  {
   "name": "physics",
   "children": [
    {"name": "DragForce", "size": 1082},
    {"name": "GravityForce", "size": 1336},
    {"name": "IForce", "size": 319},
    {"name": "NBodyForce", "size": 10498},
    {"name": "Particle", "size": 2822},
    {"name": "Simulation", "size": 9983},
    {"name": "Spring", "size": 2213},
    {"name": "SpringForce", "size": 1681}
   ]
  },
  {
   "name": "query",
   "children": [
    {"name": "AggregateExpression", "size": 1616},
    {"name": "And", "size": 1027},
    {"name": "Arithmetic", "size": 3891},
    {"name": "Average", "size": 891},
    {"name": "BinaryExpression", "size": 2893},
    {"name": "Comparison", "size": 5103},
    {"name": "CompositeExpression", "size": 3677},
    {"name": "Count", "size": 781},
    {"name": "DateUtil", "size": 4141},
    {"name": "Distinct", "size": 933},
    {"name": "Expression", "size": 5130},
    {"name": "ExpressionIterator", "size": 3617},
    {"name": "Fn", "size": 3240},
    {"name": "If", "size": 2732},
    {"name": "IsA", "size": 2039},
    {"name": "Literal", "size": 1214},
    {"name": "Match", "size": 3748},
    {"name": "Maximum", "size": 843},
    {
     "name": "methods",
     "children": [
      {"name": "add", "size": 593},
      {"name": "and", "size": 330},
      {"name": "average", "size": 287},
      {"name": "count", "size": 277},
      {"name": "distinct", "size": 292},
      {"name": "div", "size": 595},
      {"name": "eq", "size": 594},
      {"name": "fn", "size": 460},
      {"name": "gt", "size": 603},
      {"name": "gte", "size": 625},
      {"name": "iff", "size": 748},
      {"name": "isa", "size": 461},
      {"name": "lt", "size": 597},
      {"name": "lte", "size": 619},
      {"name": "max", "size": 283},
      {"name": "min", "size": 283},
      {"name": "mod", "size": 591},
      {"name": "mul", "size": 603},
      {"name": "neq", "size": 599},
      {"name": "not", "size": 386},
      {"name": "or", "size": 323},
      {"name": "orderby", "size": 307},
      {"name": "range", "size": 772},
      {"name": "select", "size": 296},
      {"name": "stddev", "size": 363},
      {"name": "sub", "size": 600},
      {"name": "sum", "size": 280},
      {"name": "update", "size": 307},
      {"name": "variance", "size": 335},
      {"name": "where", "size": 299},
      {"name": "xor", "size": 354},
      {"name": "_", "size": 264}
     ]
    },
    {"name": "Minimum", "size": 843},
    {"name": "Not", "size": 1554},
    {"name": "Or", "size": 970},
    {"name": "Query", "size": 13896},
    {"name": "Range", "size": 1594},
    {"name": "StringUtil", "size": 4130},
    {"name": "Sum", "size": 791},
    {"name": "Variable", "size": 1124},
    {"name": "Variance", "size": 1876},
    {"name": "Xor", "size": 1101}
   ]
  },
  {
   "name": "scale",
   "children": [
    {"name": "IScaleMap", "size": 2105},
    {"name": "LinearScale", "size": 1316},
    {"name": "LogScale", "size": 3151},
    {"name": "OrdinalScale", "size": 3770},
    {"name": "QuantileScale", "size": 2435},
    {"name": "QuantitativeScale", "size": 4839},
    {"name": "RootScale", "size": 1756},
    {"name": "Scale", "size": 4268},
    {"name": "ScaleType", "size": 1821},
    {"name": "TimeScale", "size": 5833}
   ]
  },
  {
   "name": "util",
   "children": [
    {"name": "Arrays", "size": 8258},
    {"name": "Colors", "size": 10001},
    {"name": "Dates", "size": 8217},
    {"name": "Displays", "size": 12555},
    {"name": "Filter", "size": 2324},
    {"name": "Geometry", "size": 10993},
    {
     "name": "heap",
     "children": [
      {"name": "FibonacciHeap", "size": 9354},
      {"name": "HeapNode", "size": 1233}
     ]
    },
    {"name": "IEvaluable", "size": 335},
    {"name": "IPredicate", "size": 383},
    {"name": "IValueProxy", "size": 874},
    {
     "name": "math",
     "children": [
      {"name": "DenseMatrix", "size": 3165},
      {"name": "IMatrix", "size": 2815},
      {"name": "SparseMatrix", "size": 3366}
     ]
    },
    {"name": "Maths", "size": 17705},
    {"name": "Orientation", "size": 1486},
    {
     "name": "palette",
     "children": [
      {"name": "ColorPalette", "size": 6367},
      {"name": "Palette", "size": 1229},
      {"name": "ShapePalette", "size": 2059},
      {"name": "SizePalette", "size": 2291}
     ]
    },
    {"name": "Property", "size": 5559},
    {"name": "Shapes", "size": 19118},
    {"name": "Sort", "size": 6887},
    {"name": "Stats", "size": 6557},
    {"name": "Strings", "size": 22026}
   ]
  },
  {
   "name": "vis",
   "children": [
    {
     "name": "axis",
     "children": [
      {"name": "Axes", "size": 1302},
      {"name": "Axis", "size": 24593},
      {"name": "AxisGridLine", "size": 652},
      {"name": "AxisLabel", "size": 636},
      {"name": "CartesianAxes", "size": 6703}
     ]
    },
    {
     "name": "controls",
     "children": [
      {"name": "AnchorControl", "size": 2138},
      {"name": "ClickControl", "size": 3824},
      {"name": "Control", "size": 1353},
      {"name": "ControlList", "size": 4665},
      {"name": "DragControl", "size": 2649},
      {"name": "ExpandControl", "size": 2832},
      {"name": "HoverControl", "size": 4896},
      {"name": "IControl", "size": 763},
      {"name": "PanZoomControl", "size": 5222},
      {"name": "SelectionControl", "size": 7862},
      {"name": "TooltipControl", "size": 8435}
     ]
    },
    {
     "name": "data",
     "children": [
      {"name": "Data", "size": 20544},
      {"name": "DataList", "size": 19788},
      {"name": "DataSprite", "size": 10349},
      {"name": "EdgeSprite", "size": 3301},
      {"name": "NodeSprite", "size": 19382},
      {
       "name": "render",
       "children": [
        {"name": "ArrowType", "size": 698},
        {"name": "EdgeRenderer", "size": 5569},
        {"name": "IRenderer", "size": 353},
        {"name": "ShapeRenderer", "size": 2247}
       ]
      },
      {"name": "ScaleBinding", "size": 11275},
      {"name": "Tree", "size": 7147},
      {"name": "TreeBuilder", "size": 9930}
     ]
    },
    {
     "name": "events",
     "children": [
      {"name": "DataEvent", "size": 2313},
      {"name": "SelectionEvent", "size": 1880},
      {"name": "TooltipEvent", "size": 1701},
      {"name": "VisualizationEvent", "size": 1117}
     ]
    },
    {
     "name": "legend",
     "children": [
      {"name": "Legend", "size": 20859},
      {"name": "LegendItem", "size": 4614},
      {"name": "LegendRange", "size": 10530}
     ]
    },
    {
     "name": "operator",
     "children": [
      {
       "name": "distortion",
       "children": [
        {"name": "BifocalDistortion", "size": 4461},
        {"name": "Distortion", "size": 6314},
        {"name": "FisheyeDistortion", "size": 3444}
       ]
      },
      {
       "name": "encoder",
       "children": [
        {"name": "ColorEncoder", "size": 3179},
        {"name": "Encoder", "size": 4060},
        {"name": "PropertyEncoder", "size": 4138},
        {"name": "ShapeEncoder", "size": 1690},
        {"name": "SizeEncoder", "size": 1830}
       ]
      },
      {
       "name": "filter",
       "children": [
        {"name": "FisheyeTreeFilter", "size": 5219},
        {"name": "GraphDistanceFilter", "size": 3165},
        {"name": "VisibilityFilter", "size": 3509}
       ]
      },
      {"name": "IOperator", "size": 1286},
      {
       "name": "label",
       "children": [
        {"name": "Labeler", "size": 9956},
        {"name": "RadialLabeler", "size": 3899},
        {"name": "StackedAreaLabeler", "size": 3202}
       ]
      },
      {
       "name": "layout",
       "children": [
        {"name": "AxisLayout", "size": 6725},
        {"name": "BundledEdgeRouter", "size": 3727},
        {"name": "CircleLayout", "size": 9317},
        {"name": "CirclePackingLayout", "size": 12003},
        {"name": "DendrogramLayout", "size": 4853},
        {"name": "ForceDirectedLayout", "size": 8411},
        {"name": "IcicleTreeLayout", "size": 4864},
        {"name": "IndentedTreeLayout", "size": 3174},
        {"name": "Layout", "size": 7881},
        {"name": "NodeLinkTreeLayout", "size": 12870},
        {"name": "PieLayout", "size": 2728},
        {"name": "RadialTreeLayout", "size": 12348},
        {"name": "RandomLayout", "size": 870},
        {"name": "StackedAreaLayout", "size": 9121},
        {"name": "TreeMapLayout", "size": 9191}
       ]
      },
      {"name": "Operator", "size": 2490},
      {"name": "OperatorList", "size": 5248},
      {"name": "OperatorSequence", "size": 4190},
      {"name": "OperatorSwitch", "size": 2581},
      {"name": "SortOperator", "size": 2023}
     ]
    },
    {"name": "Visualization", "size": 16540}
   ]
  }
 ]
}

index.html

<!DOCTYPE html>
<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><meta charset="utf-8">
<title>Weighted Voronoi Treemap in D3v4</title>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
<script src="//d3js.org/d3.v4.min.js" charset="utf-8"></script>
<script language="javascript" type="text/javascript" src="d3-rebind.js"></script>
<script language="javascript" type="text/javascript" src="d3-polygon-clip.js"></script>
<script language="javascript" type="text/javascript" src="ConvexHull.js"></script>
<script language="javascript" type="text/javascript" src="PowerDiagram.js"></script>
<script language="javascript" type="text/javascript" src="VoronoiTreemap.js"></script>
<script language="javascript" type="text/javascript" src="VoronoiTreemapD3.js"></script>
  <style>
      #wip {
        display: none;
        position: absolute;
        top: 200px;
        left: 330px;
        font-size: 40px;
        text-align: center;
      }
  </style>
</head>
<body>
<h2>Voronoi Treemap</h2>
<div>
<select id="select_polygon">
<option value="rectangle">Rectangle</option>
<option value="triangle">Triangle</option>
<option value="pentagon">Pentagon</option>
<option value="octagon">Octagon</option>
<option value="circle">Circle (100-gon)</option>
</select>

<button type="button" id="button_compute">Compute Diagram!</button>

<br><br>

<label><input type="checkbox" name="checkbox_stroke" id="checkbox_stroke" checked>Stroke Width</label>

&nbsp;&nbsp;

Color: 
<select id="select_color">
  <option value="linear">Linear</option>
  <option value="name">Name</option>
  <option value="none">None</option>
</select>

&nbsp;&nbsp;

Max depth to show: 
<select id="select_max_depth">
  <option value="none">None</option>
  <option value="1">1</option>
  <option value="2">2</option>
  <option value="3">3</option>
  <option value="4">4</option>
  <option value="5">5</option>
  <option value="6">6</option>
  <option value="7">7</option>
  <option value="8">8</option>
  <option value="9">9</option>
  <option value="10">10</option>
  <option value="11">11</option>
  <option value="12">12</option>
</select>
</div>
  <div id="wip">
    Work in progress ...
  </div>

<script language="javascript">
function make_regular_polygon(width, height, border, sides) {
	var center = [width*0.5, height*0.5],
		width_radius = (width - 2*border) * 0.5,
		height_radius = (height - 2*border) * 0.5,
		radius = Math.min( width_radius, height_radius ),
		angle_radians = 2*Math.PI / sides,
		initial_angle = sides%2==0 ? -Math.PI/2 -angle_radians*0.5 : -Math.PI/2, // subtract angles
		result = [],
		somevariable = 0;
	
	// special case few sides
	if (sides == 3) {
		center[1] += height_radius / 3.0; // can always do this (I think?)
	
		radius_for_width = width_radius * 2 / Math.sqrt(3);
		radius_for_height = height_radius * 4.0 / 3.0;
		radius = Math.min(radius_for_width, radius_for_height);
	}
	else if (sides == 4) {
		radius *= Math.sqrt(2);
	}
	
	for (var i = 0; i < sides; i++) {
		result.push([center[0] + radius * Math.cos(initial_angle - i * angle_radians), center[1] + radius * Math.sin(initial_angle - i * angle_radians)]);
	}

	return result;
}

// here we set up the svg
var width = 960;
var height = 800;
var border = 10;
var svg_container = d3.select("body").append("svg")
	.attr("width",width)
	.attr("height",height)
	.attr("id","svgid");

///////// bounding polygon
function get_selected_polygon() {
	var width_less_border = width - 2*border;
	var height_less_border = height - 2*border;
	var entire_svg_polygon = [[border,border],
		[border,height_less_border],
		[width_less_border,height_less_border],
		[width_less_border,border]];

	var select_polygon = d3.select("#select_polygon").node().value;
	if (select_polygon == "rectangle") {
		return entire_svg_polygon;
	}
	else if (select_polygon == "triangle") {
		return make_regular_polygon(width, height, border, 3);
	}
	else if (select_polygon == "pentagon") {
		return make_regular_polygon(width, height, border, 5);
	}
	else if (select_polygon == "octagon") {
		return make_regular_polygon(width, height, border, 8);
	}
	else if (select_polygon == "circle") {
		return make_regular_polygon(width, height, border, 100);
	}	
}

function make_d3_poly(d) {
	return "M" + d.join("L") + "Z";
}


var paint = function(root){
  //sort nodes to draw by depth-first
  nodes = root.descendants().sort(function(a,b) { return b.depth - a.depth});
	svg_container.selectAll("path").remove();

	// background color
	//var background_color = "lightgray";
	var background_color = "none";
	svg_container.append("g").append("rect")
		.attr("x", 0)
		.attr("y", 0)
		.attr("width", width)
		.attr("height", height)
		.attr("fill", background_color);

	// strokes by depth
	// a bit awkward to use the UI element here
	var stroke_by_depth = d3.select("#checkbox_stroke").property('checked');		
	var stroke_min = 2,
		stroke_max = stroke_by_depth ? 10 : stroke_min,
		stroke_levels = 3,// could determine from max depth...see color...
		stroke_delta = (stroke_max - stroke_min) * 1.0 / stroke_levels;
	
	// color
	var select_color = d3.select("#select_color").node().value;
	if (select_color == "linear") {
    
		var nodes_max_depth = root.height;
		var color_d3_linear = d3.scaleLinear().domain([0, nodes_max_depth]).range(["blue","lightblue"]);
		var color_func = function(d) { return color_d3_linear(d.depth); };
	}
	else if (select_color == "name") {
		var color_d3 = d3.scaleOrdinal(d3.schemeCategory20c);
		var color_func = function(d) { return d.children ? color_d3(d.name) : "none"; };
	}
	else {
		// none or some other weird thing ;)
		var color_func = "lightblue"; // or whatever color
	}
	
	// any maximum depth?
	var select_max_depth = d3.select("#select_max_depth").node().value;
	var max_depth = 12; // or whatever big thing...
	if (select_max_depth != "none") {
		max_depth = parseInt(select_max_depth);
	}
	
	
	
	// consolidate and draw polygons
    var selected_node_list = [];
    for (var i = 0; i < nodes.length; i++){
        var node = nodes[i];
        if (node.polygon != null && node.depth <= max_depth){
            selected_node_list.push(node);
        }
    }
    var polylines = svg_container.append("g").selectAll("path").data(selected_node_list);
	polylines.enter().append("path")
	        .attr("d", function(d) {return make_d3_poly(d.polygon);})
			.attr("stroke-width", function(d) { return Math.max(stroke_max - stroke_delta*d.depth, stroke_min) + "px";})
	        .attr("stroke", "black")
	        .attr("fill", color_func)
  				.attr("fill-opacity", function(d){ return d.children? 0 : 1; });
    polylines.exit().remove();
	
	
	// also circles?  only for leaves?
	// a subset of selected_node_list as it turns out
	var leaf_node_list = [];
    for (var i = 0; i < selected_node_list.length; i++){
        var node = selected_node_list[i];
        if (!node.children || node.depth == max_depth){
            leaf_node_list.push(node);
        }
    }

	// disabled because of weirdness with non-leaf centroids
	// centroid circles
	//var show_leaf_centroids = d3.select("#checkbox_leaf_centroids").property('checked');
	if (false) {
		var center_circles = svg_container.append("g").selectAll(".center.circle").data(leaf_node_list);
		center_circles.enter().append("circle")
			.attr("class", "center circle")
			.attr("cx", function(d) {return (d.site.x);})
			.attr("cy", function(d) {return (d.site.y);})
			.attr("r", function(d) {return 5;})
			//.attr("r", function(d) {return (Math.sqrt(d.weight));})
			//.attr("r", function(d) {return (Math.max(Math.sqrt(d.weight), 2));})
			.attr("stroke", "black")
			.attr("fill", "black");
	}
	
	// weight circles
	// this does work...but is kind of ugly
	if (false) {
		var radius_circles = svg_container.append("g").selectAll(".radius.circle").data(leaf_node_list);
		radius_circles.enter().append("circle")
			.attr("class", "radius circle")
			.attr("cx", function(d) {return (d.site.x);})
			.attr("cy", function(d) {return (d.site.y);})
			//.attr("r", function(d) {return 5;})
			.attr("r", function(d) {return (Math.sqrt(d.weight));})
			//.attr("r", function(d) {return (Math.max(Math.sqrt(d.weight), 2));})
			.attr("stroke", "white")
			.attr("stroke-width", "5px")
			.attr("fill", "none");
	}
}

var newroot;
function compute() {
	var select_polygon = get_selected_polygon();
	var vt = d3.voronoitreemap()
		.root_polygon(select_polygon)
		.value(function(d) {return d.size; })
		.iterations(100);
	d3.json("flare.json", function(error, flare) {
  // d3.json("flare.json", function(error, flare) {	// for debug purpose
		if (error) throw error;
		newroot = vt(flare);
		paint(newroot);
	});
}



// yeah...should probably update on all input changes
// nope...only the fast ones!
d3.select("#checkbox_stroke").on("click", function() {paint(newroot)});
d3.select("#select_color").on("change", function() {paint(newroot)});
d3.select("#checkbox_leaf_centroids").on("click", function() {paint(newroot)});
d3.select("#select_max_depth").on("change", function() {paint(newroot)});

d3.select("#button_compute").on("click", function() {compute();});


</script>


</body></html>

label.json

{
  "name": "label",
  "children": [
    {"name": "Labeler", "size": 9956},
    {"name": "RadialLabeler", "size": 3899},
    {"name": "StackedAreaLabeler", "size": 3202}
  ]
}

PowerDiagram.js

// PowerDiagram.js - computePowerDiagramIntegrated() and subroutines

// IN: sites and weights
// OUT: sites with Z coordinate based on X, Y, and W
function applyDeltaPi(S, W) {
  var result = [];
  for (var i = 0; i < S.length; i++) {
    var x = S[i].p[0], y = S[i].p[1], w = W[i];
    result[i] = [x, y, (x*x) + (y*y) - w];
  }
  return result;
}

function max(list) {
  var max = null;
  for (var i = 1; i < list.length; i++) {
    if (list[i] > max) {
      max = list[i];
    }
  }
  return max;
}

function min(list) {
  var min = null;
  for (var i = 1; i < list.length; i++) {
    if (list[i] < min) {
      min = list[i];
    }
  }
  return min;
}

// As applyDeltaPi, but applies a minimum weight
// IN: sites
// OUT: sites with Z coordinate based on X,Y,and W
function applyDeltaPiToBounds(S) {
  var result = [];

  var maxX = max(S.map(function(a) {return a[0];}));
  var minX = min(S.map(function(a) {return a[0];}));
  var maxY = max(S.map(function(a) {return a[1];}));
  var minY = min(S.map(function(a) {return a[1];}));

  var x0 = minX - maxX;
  var x1 = 2 * maxX;
  var y0 = minY - maxY;
  var y1 = 2 * maxY;

  result[0] = [x0, y0, (x0 * x0) + (y0 * y0) - epsilon];
  result[1] = [x1, y0, (x1 * x1) + (y0 * y0) - epsilon];
  result[2] = [x1, y1, (x1 * x1) + (y1 * y1) - epsilon];
  result[3] = [x0, y1, (x0 * x0) + (y1 * y1) - epsilon];

  return result;
}

// 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) {
  var width = 1000;
  var height = 1000;

  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;
            if (clippedPoly.length > 0) {
              polygons.push(clippedPoly);
            }
          }
        }
      }
    }
  }
  return polygons;
}

VoronoiTreemap.js

var VoronoiTreemap = {
    debugMode: false,
    firstIteration: true,
    nearlyOne: 0.99,
    preflowPercentage: 0.08,
    useNegativeWeights: true,
    useExtrapolation: false,
    cancelOnAreaErrorThreshold: true,
    cancelOnMaxIterat: true,
    errorAreaThreshold: 0,
	//errorAreaThreshold: 5.0, // try to stop the crashes (doesn't seem to help too much)
    clipPolygon: [],
    guaranteeInvariant:false,
    sites: [],
    numberMaxIterations: 0,
    completeArea: 1,
    preflowFinished: false,
    maxDelta: 0,
    diagram: [],
    currentMaxError: 0,
    currentAreaError: 0,
    currentEuclidChange: 0,
    lastMaxWeight: 0,
    lastAreaError: 1,
    lastAVGError: 1,
    lastMaxError: 1E10,
    lastSumErrorChange: 1,
    lastEuclidChange: 0,
    currentMaxNegativeWeight: 0,
    aggressiveMode: false,
    boundingSites: [],
    seed: 25, 

    init:function(bounding_polygon, node) {
        this.clear();
        var sites = [];
        var random_points = this.getRandomPointsInPolygon(bounding_polygon, node.children.length);
      
        for (var c = 0; c < node.children.length; c++) {
	    // calculate percentage weights
            var size = (node.children[c].value * 1.0 / node.value)
            sites.push(new Vertex(random_points[c][0],random_points[c][1], null, epsilon, null, false, size));
        }


        return sites;
    },

    getPolygonBoundingRect:function(polygon) {
	var x_list = polygon.map(function(p) {return p[0];});
	var y_list = polygon.map(function(p) {return p[1];});
	var x_min = Math.min.apply(null, x_list);
	var x_max = Math.max.apply(null, x_list);
	var y_min = Math.min.apply(null, y_list);
	var y_max = Math.max.apply(null, y_list);
	return {"x":x_min,"y":y_min,"w":(x_max-x_min),"h":(y_max-y_min)};
    },
    doesPolygonContain:function(polygon, point) {
	var contains = false;
	// could check bounds first (as above)
	for (var i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
	    if ((((polygon[i][1] <= point[1]) && (point[1] < polygon[j][1]) ||
		  ((polygon[j][1] <= point[1]) && (point[1] < polygon[i][1]))) &&
		 (point[0] < (polygon[j][0] - polygon[i][0]) * (point[1] - polygon[i][1]) / (polygon[j][1] - polygon[i][1]) + polygon[i][0]))) {
		contains = !contains;
	    }
	}
	return contains;
    },

    random:function() {
        var x = Math.sin(this.seed++) * 10000;
        return x - Math.floor(x);
    },

    getRandomPointsInPolygon:function(polygon, n_points) {
	// get bounding rect
	var rect = this.getPolygonBoundingRect(polygon);
	var result = []
	for (var i = 0; i < n_points; i++) {
            var p = [rect.x + Math.random() * rect.w, rect.y + Math.random() * rect.h];
            //	    var p = [rect.x + this.random() * rect.w, rect.y + this.random() * rect.h];
	    // see if p in polygon itself
	    //console.log(p)
	    if (this.doesPolygonContain(polygon, p)) {
		//console.log("does contain");
		result.push(p);
	    }
	    else {
		//console.log("does NOT contain");
		i--; // try again
	    }
	}

        // result = [];
	// result[0] = [130.92696687905118,91.98442592052743];
	// result[1] = [392.4537549354136,212.1577649912797];
	// result[2] = [260.31649184413254,26.87118007801473];
        // result[3] = [327.5536074768752,504.62498559616506];
	// result[4] = [261.0148494830355,14.232384245842695];
	// result[5] = [424.6814074809663,501.3572446606122];
	// result[6] = [234.0266134799458,33.144795794505626];
	// result[7] = [325.7570087816566,298.1421837885864];

        //console.log("Result: " + result);
	return result;
    },
    

    clear: function(){
        this.debugMode = false;
        this.firstIteration = true;
        this.nearlyOne = 0.99;
        this.preflowPercentage = 0.08;
        this.useNegativeWeights = true;
        this.useExtrapolation = false;
        //        this.cancelOnAreaErrorThreshold = true;
        this.cancelOnMaxIterat = true;
        //        this.errorAreaThreshold = 1000;
        this.firstIteration = true;
        this.clipPolygon= [];
        this.sites= [];
        this.numberMaxIterations= 0;
        this.completeArea= 1;
        this.preflowFinished= false;
        this.maxDelta= 0;
        this.diagram= [];
        this.currentMaxError= 0;
        this.currentAreaError= 0;
        this.currentEuclidChange = 0;
        this.lastMaxWeight = 0;
        this.lastAreaError = 1;
        this.lastAVGError = 1;
        this.lastMaxError = 1E10;
        this.lastSumErrorChange = 1;
        this.lastEuclidChange = 0;
        this.currentMaxNegativeWeight = 0;
        this.aggressiveMode = false;
        this.boundingSites = [];
    },
    max: function(list){
        var max = null;
        for (var i = 0; i < list.length; i++) {
            if (list[i] > max){
                max = list[i];
            }
        }
        return max;
    },
    min: function(list){
        var min = null;
        for (var i = 0; i < list.length; i++) {
            if (list[i] < min){
                min = list[i];
            }
        }
        return min;
    },

    setClipPolygon: function(polygon){
        this.clipPolygon = polygon;
        this.maxDelta = Math.max(polygon[2][0] - polygon[0][0], polygon[2][1] - polygon[0][1]); // TODO: assumes polygon is a square starting in the upper left corner.

        this.boundingSites = [];

        var maxX = this.max(polygon.map(function(a) {return a[0];}));
        var minX = this.min(polygon.map(function(a) {return a[0];}));
        var maxY = this.max(polygon.map(function(a) {return a[1];}));
        var minY = this.min(polygon.map(function(a) {return a[1];}));

        var x0 = minX - maxX;
        var x1 = 2 * maxX;
        var y0 = minY - maxY;
        var y1 = 2 * maxY;

        var result = [];
        result[0] = [x0, y0];
        result[1] = [x1, y0];
        result[2] = [x1, y1];
        result[3] = [x0, y1];

        for (var i = 0; i < result.length; i++){
            this.boundingSites[i] = new Vertex(result[i][0], result[i][1], null, epsilon, new Vertex(result[i][0], result[i][1], null, epsilon, null, true), true);
        }


    },

    // getMinDistanceToBorder(polygon, point){
    //     var result = this.computeDistanceBorder(polygon, point);
    //     for (var i = 0; i < polygon.length; i++){
            
    //     }
    // },

    // http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line
    computeDistanceBorder:function(polygon, point) { // Getting somewhat higher results than Java
	for (var i = 0; i < polygon.length; i++) {
	    var p1 = polygon[i];
	    if (i+1 < polygon.length) {
                var p2 = polygon[i+1];
            }
	    else {
                var p2 = polygon[0];
            }
	    
	    var dx = p1[0] - p2[0];
	    var dy = p1[1] - p2[1];
	    
	    var d = Math.abs(dy * point[0] - dx * point[1] + p1[0]*p2[1] - p2[0]-p1[1]) / Math.sqrt(dx*dx + dy*dy);
            
	    if (i == 0 || d < result) {
                var result = d;
            }
	}
        
	return result;
    },

    // final double px = x2-x1;
    // 	final double py = y2-y1;
    // 	final double d= Math.sqrt(px * px + py * py);
    
    // 	final double u = ((x3-x1)*(x2-x1)+(y3-y1)*(y2-y1))/(d*d);
    // 	final double kx = x1+u*(x2-x1);
    // 	final double ky=y1+u*(y2-y1);
    
    // 	final double dkx = x3-kx;
    // 	final double dky = y3-ky;
    // 	return Math.sqrt(dkx*dkx+dky*dky);

	// public double getMinDistanceToBorder(double x, double y) {
	//     double result = Geometry.distancePointToSegment(this.x[length - 1],
	// 			                            this.y[length - 1], this.x[0], this.y[0], x, y);
	//     for (int i = 0; i < (length - 1); i++) {
	// 	double distance = Geometry.distancePointToSegment(this.x[i],
	// 				                          this.y[i], this.x[i + 1], this.y[i + 1], x, y);
	// 	if (distance < result) {
	// 	    result = distance;
	// 	}
	//     }
	//     return result;

	// }
    normalizeSites: function(sites){
        var sum = 0;
        for (var z = 0; z < sites.length; z++){
            var s = sites[z];
            sum += s.percentage; // TODO: actually the same as getPercentage?
        }
        for (var z = 0; z < sites.length; z++){
            var s = sites[z];
            s.percentage = (s.percentage / sum);
        }
    },

    voroDiagram: function(){
        this.diagram = computePowerDiagramIntegrated(this.sites, this.boundingSites, this.clipPolygon);
    },

    distance: function(p1, p2){
        var dx = p1[0] - p2[0];
        var dy = p1[1] - p2[1]
        return Math.sqrt((dx*dx) + (dy*dy));
    },

    getMinNeighbourDistance: function(point){
        var minDistance = 1E10; // TODO: max value?
        for (var i = 0; i < point.neighbours.length; i++){
            var distance = this.distance(point.neighbours[i], point);
            if (distance < minDistance){
                minDistance = distance;
            }
        }
        return minDistance;
    },

    iterate: function(){
        var polygons = [];
//        console.log("iterate()");
        
	this.currentMaxNegativeWeight=0;
	this.currentEuclidChange = 0;
	this.currentAreaError = 0;
	this.currentMaxError = 0;

        this.completeArea = d3.polygonArea(this.clipPolygon); // TODO: make sure this works

        var errorArea = 0;

        // ***
        // TODO: omitting extrapolation code here
        // ***

        // Move to centers
        for (var z = 0; z < this.sites.length; z++){
            var point = this.sites[z];
            var error = 0;
            var percentage = point.percentage; // TODO: Same as percentage?

            var poly = point.polygon; // TODO: make site a "class"? Anyways, this may be null
            if (poly != null){
                var centroid = d3.polygonCentroid(poly);
                var centroidX = centroid[0];
                var centroidY = centroid[1];
                var dx = centroidX - point.x;
                var dy = centroidY - point.y;
                this.currentEuclidChange += (dx*dx) + (dy*dy);
                var currentArea = d3.polygonArea(poly);
                var wantedArea = completeArea * point.percentage; // TODO: Same as percentage?
                // var increase = (wantedArea / currentArea); // not used
                error = Math.abs(wantedArea - currentArea);
                // Omitted minDistanceClipped because its use is within extrapolation code
                //
                //

                //                var minDistance = point.nonClippedPolygon.getMinDistanceToBorder(centroidX, centroidY); // TODO
                var minDistance = this.computeDistanceBorder(point.nonClippedPolygon, centroid);
   
                var weight = Math.min(point.weight, minDistance * minDistance);
                if (weight < 1E-8){
                    weight = 1E-8;
                }
                
                point.x = centroidX;
                point.y = centroidY;
                point.setWeight(weight);

            }
            
            error = error / (completeArea * 2);
            
            errorArea += error;
        }

        this.currentAreaError += errorArea;

        this.voroDiagram();

        // var sitesCopy = null;
        // Omitting because guaranteeInvariant is always false
        //
        //
        for (var z = 0; z < this.sites.length; z++){
            var point = this.sites[z];
            var poly = point.polygon; // Definitely should not be null
            var completeArea = d3.polygonArea(this.clipPolygon);
            var currentArea = d3.polygonArea(poly);
            var wantedArea = completeArea * point.percentage // TODO: same as percentage?

            var currentRadius = Math.sqrt(currentArea/Math.PI);
            var wantedRadius = Math.sqrt(wantedArea/Math.PI);
            var deltaCircle = currentRadius - wantedRadius;

            var increase = wantedArea / currentArea;
            
            if (!this.aggressiveMode){
                increase = Math.sqrt(increase);
            }

            var minDistance = 0;
            // Omitted because guaranteeInvariant is never true
            //
            minDistance = this.getMinNeighbourDistance(point); // TODO
            minDistance = minDistance * this.nearlyOne;

            var radiusOld = Math.sqrt(point.weight);
            var radiusNew = radiusOld * increase;
            
            var deltaRadius = radiusNew - radiusOld;
            if (radiusNew > minDistance){
                radiusNew = minDistance;
            }
            
            var finalWeight = radiusNew*radiusNew;
            
            if (this.useNegativeWeights){
                var center = poly.centroid();
                var distanceBorder = this.computeDistanceBorder(poly, center);
                var maxDelta = Math.min(distanceBorder, deltaCircle);
                if (finalWeight < 1E-4){
                    var radiusNew2 = radiusNew - maxDelta;
                    if (radiusNew2 < 0){
                    finalWeight = -(radiusNew2 * radiusNew2);
                        if (finalWeight < this.currentMaxNegativeWeight){
                            this.currentMaxNegativeWeight = finalWeight;
                        }
                    }
                }
            }

            //console.log("new weight: " + finalWeight + " : " + point);

            point.setWeight(finalWeight);
        }

        if (this.useNegativeWeights){
            
            if (this.currentMaxNegativeWeight < 0){
                this.currentMaxNegativeWeight += (1-this.nearlyOne);
                this.currentMaxNegativeWeight = -this.currentMaxNegativeWeight;
                for (var z = 0; z < this.sites.length; z++){
                    var s = this.sites[z];
                    var w = s.weight;
                    w += this.currentMaxNegativeWeight;
                    s.setWeight(w);
                }
            }
        }

        this.voroDiagram();

        this.currentMaxError = 0;
        for (var z = 0; z < this.sites.length; z++){
            var site = this.sites[z];
            var poly = site.polygon;
            var percentage = site.percentage // TODO: same as percentage?
            var wantedArea = completeArea * percentage;
            var currentArea = d3.polygonArea(poly);
            var singleError = Math.abs(1 - ( currentArea / wantedArea));
            if (singleError > this.currentMaxError){
                this.currentMaxError = singleError;
            }
        }

        this.lastEuclidChange = this.currentEuclidChange / this.sites.length;
        this.lastSumErrorChange = Math.abs(this.lastAreaError - this.currentAreaError);
        this.lastAreaError = this.currentAreaError;
        this.lastMaxError = this.currentMaxError;
        this.lastAVGError = this.currentAreaError / this.sites.length;

        return this.sites.map(function(s) {return s.polygon;});
    },

    // Return list of polygons
    doIterate: function(iterationAmount){
        
        var polygons = [];
        
        if (this.sites.length == 1){
            polygons.push(this.clipPolygon);
            return polygons;
        }

        if (this.firstIteration){
            this.voroDiagram();
        }

        var k = 0;
        for (var i = 0; i < iterationAmount; i++){
            polygons = this.iterate();
            //console.log(i + ": error: " + this.lastMaxError);
            if (this.cancelOnAreaErrorThreshold && this.lastMaxError < this.errorAreaThreshold){
                break;
            }
        }

        return polygons;
    }

}

VoronoiTreemapD3.js

///////// from hierarchy.js

// A method assignment helper for hierarchy subclasses.
function d3_layout_hierarchyRebind(object, hierarchy) {
    //d3.rebind(object, d3.hierarchy, "sort", "children", "value");

    // Add an alias for nodes and links, for convenience.
    object.nodes = object;
    object.links = d3_layout_hierarchyLinks;

    return object;
}

// Returns an array source+target objects for the specified nodes.
function d3_layout_hierarchyLinks(nodes) {
    return d3.merge(nodes.map(function(parent) {
        return (parent.children || []).map(function(child) {
            return {source: parent, target: child};
        });
    }));
}

///////////////////////
// the actual implementation

d3.voronoitreemap = function() {
    var hierarchy = d3.hierarchy("").sort(null),
        root_polygon = [[0,0],[500,0],[500,500],[0,500]], // obviously stupid...set somehow
        iterations = 100,
        value = function (d) { return d.value; },
        somenewvariable = 0;

    function voronoitreemap(d, depth) {
      hierarchy = d3.hierarchy(d).sum(function(d){ return +d.size; });
    	var root = hierarchy;
			
    	root.polygon = root_polygon;
	    root.site = null;  // hmm?

    	if (depth != null) {
	    	max_depth = depth;
    	} else {
    		max_depth = "Infinity";
	    }
    	var date = new Date();
	    var startTime = 0 + date.getTime();
	    computeDiagramRecursively(root, 0);
	    var endTime = (new Date).getTime();
	    // alert("TIME: " + (endTime - startTime));
    	return root;
    }

    function computeDiagramRecursively(node, level) {
    	var children = node.children;
    	if (children && children.length && level < max_depth) {
	        node.sites = VoronoiTreemap.init(node.polygon, node);  // can't say dataset, how about node?
	        VoronoiTreemap.normalizeSites(node.sites);
    	    VoronoiTreemap.sites = node.sites;
	        VoronoiTreemap.setClipPolygon(node.polygon);
	        VoronoiTreemap.useNegativeWeights = false;
    	    VoronoiTreemap.cancelOnAreaErrorThreshold = true;
	        var polygons = VoronoiTreemap.doIterate(iterations);
    	    // set children polygons and sites
	        for (var i = 0; i < children.length; i++) {
		        children[i].polygon = polygons[i];
        		children[i].site = VoronoiTreemap.sites[i];
		        // goes all the way down
        		computeDiagramRecursively(children[i], (level + 1));
    	    }
    	}
    }

    voronoitreemap.root_polygon = function(x) {
      if (!arguments.length)
          return root_polygon;
      root_polygon = x;
      return voronoitreemap;
      };

    voronoitreemap.iterations = function(x) {
      if (!arguments.length)
          return iterations;
      iterations = x;
      return voronoitreemap;
    };
  
  	voronoitreemap.value = function(x) {
      if (!arguments.length)
          return value;
      value = x;
      return voronoitreemap;
    };
	
  	return d3_layout_hierarchyRebind(voronoitreemap, hierarchy);
}