Skip to content

Instantly share code, notes, and snippets.

@Kcnarf

Kcnarf/.block

Last active October 8, 2019 06:14
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save Kcnarf/15d54f4ccae6a3710cd3029546664eec to your computer and use it in GitHub Desktop.
Save Kcnarf/15d54f4ccae6a3710cd3029546664eec to your computer and use it in GitHub Desktop.
Download ZIP
Weighted Voronoi Treemap in D3v4
Raw
.block
license: gpl-3.0
height: 1000
Raw
README.md

This block is a port, from d3v3 to d3v4, of mkedwards's block: Treemap.

Warning sometimes (1% of time), code fails to compute the layout, and doesn't update the svg. In such a case, you have to (re-)compute diagram.

Updates

  • 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)
  • min and max functions consider all elements (instead of starting at index 1)
  • rework computeDistanceBorder to make it compatible with the wikipedia formula (fixes error Cannot set property 'twin' of null of the original block)
  • in voronoiTreemap/iterate, when adapt weight (second adaptation), compute min distance border based on clipped polygon (initialy, was computed on NON clipped polygon)
  • rework linearDependant function
  • in setClipPolygon, order bounding sites in counterclockwise
  • 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 impacts are on paint() function
  • add a label.json file, with a very simple hierarchy, for debug purpose
  • remove activity.json file

On-going issues

  • sometimes (1% of time), 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; I've already work on this error, and drastically lower its arising; but there is still some unknown situations that still raise this error ...
  • 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.

Raw
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
// from https://math.stackexchange.com/questions/1144357/how-can-i-prove-that-two-vectors-in-%E2%84%9D3-are-linearly-independent-iff-their-cro
linearDependent: function(p1, p2) {
var xy = p1.x*p2.y - p1.y*p2.x,
yz = p1.y*p2.z - p1.z*p2.y,
zx = p1.z*p2.x - p1.x*p2.z;
return (xy>=-epsilon && xy<=epsilon)
&& (yz>=-epsilon && yz<=epsilon)
&& (zx>=-epsilon && zx<=epsilon);
},
clear: function() {
this.points = [];
this.facets = [];
this.created = [];
this.horizon = [];
this.visible = [];
this.current = 0;
}
}
Raw
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});
}));
Raw
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;
};
}
Raw
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}
]
}
]
}
Raw
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="https://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.data.children ? "none" : d.parent ? color_d3(d.parent.data.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.depth<max_depth && 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>
Raw
label.json
{
"name": "label",
"children": [
{"name": "Labeler", "size": 9956},
{"name": "RadialLabeler", "size": 3899},
{"name": "StackedAreaLabeler", "size": 3202}
]
}
Raw
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 = 0; i < list.length; i++) {
if (list[i] > max) {
max = list[i];
}
}
return max;
}
function min(list) {
var min = null;
for (var i = 0; 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;
}
Raw
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] = [x0, y1];
result[2] = [x1, y1];
result[3] = [x1, y0];
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);
}
},
// http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line
computeDistanceBorder:function(polygon, point) {
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 = p2[0] - p1[0];
var dy = p2[1] - p1[1];
var d = Math.abs(dy * point[0] - dx * point[1] + p2[0]*p1[1] - p1[0]*p2[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
//
//
// in initial block 'point.nonClippedPolygon' was used instead of 'poly' in below code
var minDistance = this.computeDistanceBorder(poly, 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;
}
}
Raw
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment