Skip to content

Instantly share code, notes, and snippets.

@mkedwards

mkedwards/ConvexHull.js

Forked from mbostock/.block
Last active January 25, 2017 08:55
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save mkedwards/759e719eefe36cf9c8ab to your computer and use it in GitHub Desktop.
Save mkedwards/759e719eefe36cf9c8ab to your computer and use it in GitHub Desktop.
Download ZIP
Treemap
Raw
README.md

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
activity.csv
process by activity_name read-server query-server purifier string-server-aggregator string-server-leaf merge-server /opt/interana/backend/import_server/jsonfilters/suppress_column_internal3 backstop addlabel
addEvents_Lookup_organize_rows 0 0 2021169 0 0 0 0 0 0
pause 205998151 0 0 0 0 0 0 0 0
detectNewColumns 0 0 4711044573 0 0 0 0 0 0
start 7395298952 0 0 0 0 0 0 0 0
wait_for_semaphore 0 0 33121568694 0 0 0 0 0 0
add_lookup_entries 0 40081760115 0 0 0 0 0 0 0
map_populate 0 0 40943141018 0 0 0 1452795250 0 0
addEvents_Lookup_shard 0 0 46268857899 0 0 0 0 0 0
cancel 1331285802 63832879838 0 0 0 0 0 0 0
holding_semaphore 0 0 67744510733 0 0 0 0 0 0
addEvents_send 0 0 73765356948 0 0 0 0 0 0
translateEvents 0 0 84527154243 0 0 0 0 0 0
thread_group_interrupt_all 0 0 40622383195 3444867 0 0 1436939702 64720622524 1058454593
parseJson 0 0 129160685807 0 0 0 0 0 0
thrift_server_serve 0 0 0 141810422074 0 0 0 0 0
addEvents_table_copy 0 0 215826257800 0 0 0 0 0 0
addEvents_deferred_split_sort_folder 0 216283120342 0 0 0 0 0 0 0
buildColumns 339769913545 0 0 0 0 0 0 0 0
funnel_read_cache_range 352632980309 0 0 0 0 0 0 0 0
executeAll_thread 445085117902 0 0 0 0 0 0 0 0
complexity 1123618262827 0 0 0 0 0 0 0 0
computeFunnels 1423868198121 0 0 0 0 0 0 0 0
split_guess_median 0 1490535677839 0 0 0 0 0 0 0
getTopValuesSubstr 0 0 0 1516896247737 485368763923 0 0 0 0
addEvents_Event_organize_rows 0 0 2259647845726 0 0 0 0 0 0
getIds_shard 0 0 0 2531980390243 0 0 0 0 0
getStrings 0 0 0 388923515373 2162273371382 0 0 0 0
periodic_update 0 0 0 0 3299069464193 0 0 0 0
transformChunk 0 0 0 0 0 0 4063306491760 0 0
scan 4084336821993 0 0 0 0 0 0 0 0
getIds 0 0 0 3909310598344 224126525231 0 0 0 0
computeSessions 5334543902000 0 0 0 0 0 0 0 0
getWriteTasks_shard 0 0 0 5465543075776 0 0 0 0 0
translateStrings 0 0 10302149954394 0 0 0 0 0 0
getResult 12789209029194 0 0 0 0 0 0 0 0
thread_group_join_all 0 0 8791877145869 4559026714967 0 0 1082493593 33824118824 869355690
query 2950952431443 0 0 0 0 17009826818351 0 0 0
addStrings_shard 0 0 0 23451328891936 0 0 0 0 0
apply_init_portions 23922016183368 0 0 0 0 0 0 0 0
isSortedByShardKey 27225247541516 0 0 0 0 0 0 0 0
funnels_folder_code 34455662146115 0 0 0 0 0 0 0 0
getReadTasks_shard 0 0 0 42470271286175 0 0 0 0 0
synchronizeState 0 0 0 0 64990101565764 0 0 0 0
getFullState 0 0 0 0 74791568434817 0 0 0 0
addStrings 0 0 0 49605175811520 35478949394137 0 0 0 0
getMatchingIds 0 0 0 83231970832451 11808036645568 0 0 0 0
getNewColumnThread_chunk 0 0 97446076872771 0 0 0 0 0 0
apply_init_time_block 98163371163790 0 0 0 0 0 0 0 0
funnel_write_cache_range 98378741753992 0 0 0 0 0 0 0 0
apply_folder_code 104050618656686 0 0 0 0 0 0 0 0
funnel_compute_range 120980532402168 0 0 0 0 0 0 0 0
computeCohorts 125440159264612 0 0 0 0 0 0 0 0
query_shard 135487040470005 0 0 0 0 0 0 0 0
registerQuery 153554105402935 0 0 0 0 0 0 0 0
addEvents_organize_by_folder 0 162405598124085 0 0 0 0 0 0 0
buildEntriesLinks 184288190066519 0 0 0 0 0 0 0 0
wait_for_any 0 0 240706927054733 0 0 0 0 0 0
scan_range 245179723441206 0 0 0 0 0 0 0 0
append_events 0 255579010092680 0 0 0 0 0 0 0
addEvents_folder 0 279718300280582 0 0 0 0 0 0 0
addEvents_Event_shard 0 0 301546648930132 0 0 0 0 0 0
thrift_connection_open 432269063354 83627534492893 263837935818871 30793338311753 19747845516549 160038193762 0 0 0
fetchStrings 0 0 411877288787603 0 0 0 0 0 0
funnels_no_time_locality 486589067107954 0 0 0 0 0 0 0 0
funnels_final_partial_sort 552626008823122 0 0 0 0 0 0 0 0
funnels_portion_code 624892549404523 0 0 0 0 0 0 0 0
apply_loadTimes 683190008986779 0 0 0 0 0 0 0 0
thrift_call 286120253379 23194208156236 620395243995479 45656707888917 44001247200369 2866417583408 0 0 0
apply_init_column_blocks 1032101874807008 0 0 0 0 0 0 0 0
threaded_tasks 0 0 1158873111619073 0 0 0 0 0 0
funnels_has_time_locality 1284764989397429 0 0 0 0 0 0 0 0
apply_bucketize 1402912695410081 0 0 0 0 0 0 0 0
apply_folder 2208314392090181 0 0 0 0 0 0 0 0
split_folder 0 2404599690615102 0 0 0 0 0 0 0
sort_folder 0 3251743673447235 0 0 0 0 0 0 0
apply_portion_code 3446277516332896 0 0 0 0 0 0 0 0
apply_load_derived_column 5749259856418669 0 0 0 0 0 0 0 0
parseJson_chunk 0 0 8628074031538751 0 0 0 0 0 0
apply_load 9006294865820002 0 0 0 0 0 0 0 0
addEventsNoTokenCheck 0 19945534315670412 0 0 0 0 0 0 0
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
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;
}
}
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>Voronoi Treemap</title>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
<script src="//d3js.org/d3.v3.min.js" charset="utf-8"></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>
</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>
<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 = 1000;
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(nodes){
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_all_depths = nodes.map(function(x) {return x.depth});
var nodes_max_depth = Math.max.apply(null, nodes_all_depths);
var color_d3_linear = d3.scale.linear().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.scale.category20c();
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);
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 newnodes;
function compute() {
var select_polygon = get_selected_polygon();
var vt = d3.layout.voronoitreemap()
.root_polygon(select_polygon)
.value(function(d) {return d.size; })
.iterations(100);
d3.json("flare.json", function(error, flare) {
if (error) throw error;
newnodes = vt(flare);
paint(newnodes);
});
}
// yeah...should probably update on all input changes
// nope...only the fast ones!
d3.select("#checkbox_stroke").on("click", function() {paint(newnodes)});
d3.select("#select_color").on("change", function() {paint(newnodes)});
d3.select("#checkbox_leaf_centroids").on("click", function() {paint(newnodes)});
d3.select("#select_max_depth").on("change", function() {paint(newnodes)});
d3.select("#button_compute").on("click", function() {compute();});
</script>
</body></html>
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 = 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 = d3.geom.polygon(protopoly.reverse());
if (!site.isDummy && site.nonClippedPolygon.length > 0) {
var clippedPoly = clippingPolygon.clip(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 = 1; i < list.length; i++) {
if (list[i] > max){
max = list[i];
}
}
return max;
},
min: function(list){
var min = null;
for (var i = 1; i < list.length; i++) {
if (list[i] < min){
min = list[i];
}
}
return min;
},
setClipPolygon: function(polygon){
this.clipPolygon = d3.geom.polygon(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 = this.clipPolygon.area(); // 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 = poly.centroid();
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 = poly.area();
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 = this.clipPolygon.area();
var currentArea = poly.area();
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 = poly.area();
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, 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.layout.voronoitreemap = function() {
var hierarchy = d3.layout.hierarchy().sort(null),
root_polygon = [[0,0],[500,0],[500,500],[0,500]], // obviously stupid...set somehow
iterations = 100,
somenewvariable = 0;
function voronoitreemap(d, depth) {
var nodes = hierarchy(d),
root = nodes[0];
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 nodes;
}
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;
};
return d3_layout_hierarchyRebind(voronoitreemap, hierarchy);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment