Skip to content

Instantly share code, notes, and snippets.

@Kcnarf

Kcnarf/.block

Last active December 3, 2018 08:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Kcnarf/7a1361137880312120796c641c1887c9 to your computer and use it in GitHub Desktop.
Save Kcnarf/7a1361137880312120796c641c1887c9 to your computer and use it in GitHub Desktop.
Download ZIP
Voronoï playground : interactive weighted Voronoï study III (Multiple sites)
Raw
.block
license: gpl-3.0
Raw
README.md

This block experiments weighted Voronoï diagram (the 2D additive weighted power diagram variation) with many sites. This is a continuation of 2 and 1.

This is still a Work In Progress, as the code is not yet packaged/self-contained, and contains weird hacks. For a more up-to-date version of the code, please refer to the Weighted Voronoi Treemap in D3v4 block.

What are you seeing ?

  • there is 4 sites (two blue and two green), with their corresponding influence areas (i.e. cells)
  • if weights are big enough, circles around sites give a sense of the weight of each site

User interactions :

  • you can change the weight of a group of sites with the corresponding slider
  • you can drag and drop each site

Acknowledgments to :

Raw
ConvexHull.js
// ConvexHull.js
var epsilon = 1E-10;
function epsilonesque(n) {
return n === 0;
return n >= -epsilon && n <= epsilon;
}
// IN: vectors or vertices
// OUT: dot product
var dot = function(v1, v2) {
return (v1.x * v2.x) + (v1.y * v2.y) + (v1.z * v2.z);
}
// IN: Face face
var Plane3D = function(face) {
var p1 = face.verts[0];
var p2 = face.verts[1];
var p3 = face.verts[2];
this.a = p1.y * (p2.z-p3.z) + p2.y * (p3.z-p1.z) + p3.y * (p1.z-p2.z);
this.b = p1.z * (p2.x-p3.x) + p2.z * (p3.x-p1.x) + p3.z * (p1.x-p2.x);
this.c = p1.x * (p2.y-p3.y) + p2.x * (p3.y-p1.y) + p3.x * (p1.y-p2.y);
this.d = -1 * (p1.x * (p2.y*p3.z - p3.y*p2.z) + p2.x * (p3.y*p1.z - p1.y*p3.z) + p3.x * (p1.y*p2.z - p2.y*p1.z));
}
// OUT: int2D
Plane3D.prototype.getDualPointMappedToPlane = function() {
var nplane = this.getNormZPlane();
var dualPoint = new Point2D(nplane[0]/2, nplane[1]/2);
return dualPoint;
}
Plane3D.prototype.getNormZPlane = function() {
return [
-1 * (this.a / this.c),
-1 * (this.b / this.c),
-1 * (this.d / this.c)
];
}
// IN: doubles x and y
var Point2D = function(x, y) {
this.x = x;
this.y = y;
}
var ConflictListNode = function(face, vert) {
this.face = face;
this.vert = vert;
this.nextf = null;
this.prevf = null;
this.nextv = null;
this.prevv = null;
}
// IN: boolean forFace
var ConflictList = function(forFace) {
this.forFace = forFace;
this.head = null;
}
// IN: ConflictListNode cln
ConflictList.prototype.add = function(cln) {
if (this.head === null) {
this.head = cln;
} else {
if (this.forFace) { // Is FaceList
this.head.prevv = cln;
cln.nextv = this.head;
this.head = cln;
} else { // Is VertexList
this.head.prevf = cln;
cln.nextf = this.head;
this.head = cln;
}
}
}
ConflictList.prototype.isEmpty = function() {
return this.head === null;
}
// Array of faces visible
ConflictList.prototype.fill = function(visible) {
if (this.forFace) {
return;
}
var curr = this.head;
do {
visible.push(curr.face);
curr.face.marked = true;
curr = curr.nextf;
} while (curr !== null);
}
ConflictList.prototype.removeAll = function() {
if (this.forFace) { // Remove all vertices from Face
var curr = this.head;
do {
if (curr.prevf === null) { // Node is head
if (curr.nextf === null) {
curr.vert.conflicts.head = null;
} else {
curr.nextf.prevf = null;
curr.vert.conflicts.head = curr.nextf;
}
} else { // Node is not head
if (curr.nextf != null) {
curr.nextf.prevf = curr.prevf;
}
curr.prevf.nextf = curr.nextf;
}
curr = curr.nextv;
if (curr != null) {
curr.prevv = null;
}
} while (curr != null);
} else { // Remove all JFaces from vertex
var curr = this.head;
do {
if (curr.prevv == null) { // Node is head
if (curr.nextv == null) {
curr.face.conflicts.head = null;
} else {
curr.nextv.prevv = null;
curr.face.conflicts.head = curr.nextv;
}
} else { // Node is not head
if (curr.nextv != null) {
curr.nextv.prevv = curr.prevv;
}
curr.prevv.nextv = curr.nextv;
}
curr = curr.nextf;
if (curr != null)
curr.prevf = null;
} while (curr != null);
}
}
// IN: list of vertices
ConflictList.prototype.getVertices = function() {
var list = [],
curr = this.head;
while (curr !== null) {
list.push(curr.vert);
curr = curr.nextv;
}
return list;
}
// IN: coordinates x, y, z
var Vertex = function(x, y, z, weight, orig, isDummy) {
this.x = x;
this.y = y;
this.weight = epsilon;
this.index = 0;
this.conflicts = new ConflictList(false);
this.neighbours = null; // Potential trouble
this.nonClippedPolygon = null;
this.polygon = null;
this.originalObject = null;
this.isDummy = false;
if (orig !== undefined) {
this.originalObject = orig;
}
if (isDummy != undefined) {
this.isDummy = isDummy;
}
if (weight != null) {
this.weight = weight;
}
if (z != null) {
this.z = z;
} else {
this.z = this.projectZ(this.x, this.y, this.weight);
}
}
Vertex.prototype.setWeight = function(weight) {
this.weight = weight;
this.z = this.projectZ(this.x, this.y, this.weight);
}
Vertex.prototype.projectZ = function(x, y, weight) {
return ((x*x) + (y*y) - weight);
}
Vertex.prototype.subtract = function(v) {
return new Vertex(v.x - this.x, v.y - this.y, v.z - this.z);
}
Vertex.prototype.crossproduct = function(v) {
return new Vertex((this.y * v.z) - (this.z * v.y), (this.z * v.x) - (this.x * v.z), (this.x * v.y) - (this.y * v.x));
}
Vertex.prototype.equals = function(v) {
return (this.x === v.x && this.y === v.y && this.z === v.z);
}
// IN: coordinates x, y, z
var Vector = function(x, y, z) {
this.x = x;
this.y = y;
this.z = z;
}
Vector.prototype.negate = function() {
this.x *= -1;
this.y *= -1;
this.z *= -1;
}
// Normalizes X Y and Z in-place
Vector.prototype.normalize = function() {
var len = Math.sqrt((this.x * this.x) + (this.y * this.y) + (this.z * this.z));
if (len > 0) {
this.x /= len;
this.y /= len;
this.z /= len;
}
}
// IN: Vertices a, b, c
var Face = function(a, b, c, orient) {
this.conflicts = new ConflictList(true);
this.verts = [a, b, c];
this.marked = false;
var t = (a.subtract(b)).crossproduct(b.subtract(c));
this.normal = new Vector(-t.x, -t.y, -t.z);
this.normal.normalize();
this.createEdges();
this.dualPoint = null;
if (orient != undefined) {
this.orient(orient);
}
}
// OUT: Point2D
Face.prototype.getDualPoint = function() {
if (this.dualPoint == null) {
var plane3d = new Plane3D(this);
this.dualPoint = plane3d.getDualPointMappedToPlane();
}
return this.dualPoint;
}
Face.prototype.isVisibleFromBelow = function() {
return (this.normal.z < -1.4259414393190911E-9);
}
Face.prototype.createEdges = function() {
this.edges = [];
this.edges[0] = new HEdge(this.verts[0], this.verts[1], this);
this.edges[1] = new HEdge(this.verts[1], this.verts[2], this);
this.edges[2] = new HEdge(this.verts[2], this.verts[0], this);
this.edges[0].next = this.edges[1];
this.edges[0].prev = this.edges[2];
this.edges[1].next = this.edges[2];
this.edges[1].prev = this.edges[0];
this.edges[2].next = this.edges[0];
this.edges[2].prev = this.edges[1];
}
// IN: vertex orient
Face.prototype.orient = function(orient) {
if (!(dot(this.normal,orient) < dot(this.normal, this.verts[0]))){
var temp = this.verts[1];
this.verts[1] = this.verts[2];
this.verts[2] = temp;
this.normal.negate();
this.createEdges();
}
}
// IN: two vertices v0 and v1
Face.prototype.getEdge = function(v0, v1) {
for (var i = 0; i < 3; i++) {
if (this.edges[i].isEqual(v0, v1)) {
return this.edges[i];
}
}
return null;
}
// IN: Face face, vertices v0 and v1
Face.prototype.link = function(face, v0, v1) {
if (face instanceof Face) {
var twin = face.getEdge(v0, v1);
if (twin === null) {
console.log("ERROR: twin is null");
}
var edge = this.getEdge(v0, v1);
twin.twin = edge;
edge.twin = twin;
} else {
var e = face;
var edge = this.getEdge(e.orig, e.dest);
e.twin = edge;
edge.twin = e;
}
}
// IN: vertex v
Face.prototype.conflict = function(v) {
return (dot(this.normal, v) > dot(this.normal, this.verts[0]) + epsilon);
}
Face.prototype.getHorizon = function() {
for (var i = 0; i < 3; i++) {
if (this.edges[i].twin !== null && this.edges[i].twin.isHorizon()) {
return this.edges[i];
}
}
return null;
}
Face.prototype.removeConflict = function() {
this.conflicts.removeAll();
}
// IN: vertex orig, vertex dest, Face face
var HEdge = function(orig, dest, face) {
this.next = null;
this.prev = null;
this.twin = null;
this.orig = orig;
this.dest = dest;
this.iFace = face;
}
HEdge.prototype.isHorizon = function() {
return this.twin !== null && this.twin.iFace.marked && !this.iFace.marked;
}
// IN: array horizon
HEdge.prototype.findHorizon = function(horizon) {
if (this.isHorizon()) {
if (horizon.length > 0 && this === horizon[0]) {
return;
} else {
horizon.push(this);
this.next.findHorizon(horizon);
}
} else {
if (this.twin !== null) {
this.twin.next.findHorizon(horizon);
}
}
}
// IN: vertices origin and dest
HEdge.prototype.isEqual = function(origin, dest) {
return ((this.orig.equals(origin) && this.dest.equals(dest)) || (this.orig.equals(dest) && this.dest.equals(origin)));
}
var ConvexHull = {
points: [],
facets: [],
created: [],
horizon: [],
visible: [],
current: 0,
// IN: sites (x,y,z)
init: function(boundingSites, sites) {
this.points = [];
for (var i = 0; i < sites.length; i++) {
this.points[i] = new Vertex(sites[i].x, sites[i].y, sites[i].z, null, sites[i], false);
}
this.points = this.points.concat(boundingSites);
},
permutate: function() {
var pointSize = this.points.length;
for (var i = pointSize -1; i > 0; i--) {
var ra = Math.floor(Math.random() * i);
var temp = this.points[ra];
temp.index = i;
var currentItem = this.points[i];
currentItem.index = ra;
this.points.splice(ra, 1, currentItem);
this.points.splice(i, 1, temp);
}
},
prep: function() {
if (this.points.length <= 3) {
console.log("ERROR: Less than 4 points");
}
for (var i = 0; i < this.points.length; i++) {
this.points[i].index = i;
}
var v0, v1, v2, v3;
var f1, f2, f3, f0;
v0 = this.points[0];
v1 = this.points[1];
v2 = v3 = null;
for (var i = 2; i < this.points.length; i++) {
if (!(this.linearDependent(v0, this.points[i]) && this.linearDependent(v1, this.points[i]))) {
v2 = this.points[i];
v2.index = 2;
this.points[2].index = i;
this.points.splice(i, 1, this.points[2]);
this.points.splice(2, 1, v2);
break;
}
}
if (v2 === null) {
console.log("ERROR: v2 is null");
}
f0 = new Face(v0, v1, v2);
for (var i = 3; i < this.points.length; i++) {
if (dot(f0.normal, f0.verts[0]) !== dot(f0.normal, this.points[i])) {
v3 = this.points[i];
v3.index = 3;
this.points[3].index = i;
this.points.splice(i, 1, this.points[3]);
this.points.splice(3, 1, v3);
break;
}
}
if (v3 === null) {
console.log("ERROR: v3 is null");
}
f0.orient(v3);
f1 = new Face(v0, v2, v3, v1);
f2 = new Face(v0, v1, v3, v2);
f3 = new Face(v1, v2, v3, v0);
this.addFacet(f0);
this.addFacet(f1);
this.addFacet(f2);
this.addFacet(f3);
// Connect facets
f0.link(f1, v0, v2);
f0.link(f2, v0, v1);
f0.link(f3, v1, v2);
f1.link(f2, v0, v3);
f1.link(f3, v2, v3);
f2.link(f3, v3, v1);
this.current = 4;
var v;
for (var i = this.current; i < this.points.length; i++) {
v = this.points[i];
if (f0.conflict(v)) {
this.addConflict(f0, v);
}
if (f1.conflict(v)) {
this.addConflict(f1, v);
}
if (f2.conflict(v)) {
this.addConflict(f2, v);
}
if (f3.conflict(v)) {
this.addConflict(f3,v);
}
}
},
// IN: Faces old1 old2 and fn
addConflicts: function(old1, old2, fn) {
var l1 = old1.conflicts.getVertices();
var l2 = old2.conflicts.getVertices();
var nCL = [];
var v1, v2;
var i, l;
i = l = 0;
// Fill the possible new Conflict List
while (i < l1.length || l < l2.length) {
if (i < l1.length && l < l2.length) {
v1 = l1[i];
v2 = l2[l];
// If the index is the same, it's the same vertex and only 1 has to be added
if (v1.index === v2.index) {
nCL.push(v1);
i++;
l++;
} else if (v1.index > v2.index) {
nCL.push(v1);
i++;
} else {
nCL.push(v2);
l++;
}
} else if ( i < l1.length) {
nCL.push(l1[i++]);
} else {
nCL.push(l2[l++]);
}
}
// Check if the possible conflicts are real conflicts
for (var i = nCL.length - 1; i >= 0; i--) {
v1 = nCL[i];
if (fn.conflict(v1))
this.addConflict(fn, v1);
}
},
// IN: Face face, Vertex v
addConflict: function(face, vert) {
var e = new ConflictListNode(face, vert);
face.conflicts.add(e);
vert.conflicts.add(e);
},
// IN: Face f
removeConflict: function(f) {
f.removeConflict();
var index = f.index;
f.index = -1;
if (index === this.facets.length - 1) {
this.facets.splice(this.facets.length - 1, 1);
return;
}
if (index >= this.facets.length || index < 0)
return;
var last = this.facets.splice(this.facets.length - 1, 1);
last[0].index = index;
this.facets.splice(index, 1, last[0]);
},
// IN: Face face
addFacet: function(face) {
face.index = this.facets.length;
this.facets.push(face);
},
compute: function() {
this.prep();
while (this.current < this.points.length) {
var next = this.points[this.current];
if (next.conflicts.isEmpty()) { // No conflict, point in hull
this.current++;
continue;
}
this.created = []; // TODO: make sure this is okay and doesn't dangle references
this.horizon = [];
this.visible = [];
// The visible faces are also marked
next.conflicts.fill(this.visible);
// Horizon edges are orderly added to the horizon list
var e;
for (var jF = 0; jF < this.visible.length; jF++) {
e = this.visible[jF].getHorizon();
if (e !== null) {
e.findHorizon(this.horizon);
break;
}
}
var last = null, first = null;
// Iterate over horizon edges and create new faces oriented with the marked face 3rd unused point
for (var hEi = 0; hEi < this.horizon.length; hEi++) {
var hE = this.horizon[hEi];
var fn = new Face(next, hE.orig, hE.dest, hE.twin.next.dest);
fn.conflicts = new ConflictList(true);
// Add to facet list
this.addFacet(fn);
this.created.push(fn);
// Add new conflicts
this.addConflicts(hE.iFace, hE.twin.iFace, fn);
// Link the new face with the horizon edge
fn.link(hE);
if (last !== null)
fn.link(last, next, hE.orig);
last = fn;
if (first === null)
first = fn;
}
// Links the first and the last created JFace
if (first !== null && last !== null) {
last.link(first, next, this.horizon[0].orig);
}
if (this.created.length != 0) {
// update conflict graph
for (var f = 0; f < this.visible.length; f++) {
this.removeConflict(this.visible[f]);
}
this.current++;
this.created = [];
}
}
return this.facets;
},
// IN: two vertex objects, p1 and p2
// OUT: true if they are linearly dependent, false otherwise
linearDependent: function(p1, p2) {
if (p1.x == 0 && p2.x == 0) {
if (p1.y == 0 && p2.y == 0) {
if (p1.z == 0 && p2.z == 0) {
return true;
}
if (p1.z == 0 || p2.z == 0) {
return false;
}
return true;
}
if (p1.y == 0 || p2.y == 0) {
return false;
}
if (epsilonesque(p1.z/p1.y - p2.z/p2.y)) {
return true;
} else {
return false;
}
}
if (p1.x == 0 || p2.x == 0) {
return false;
}
if (epsilonesque(p1.y/p1.x - p2.y/p2.x) && epsilonesque(p1.z/p1.x - p2.z/p2.x)) {
return true;
} else {
return false;
}
},
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
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Voronoï playground : interactive weighted Voronoï study III (multiple sites)</title>
<meta name="description" content="Weighted Voronoï in D3.js">
<script src="https://d3js.org/d3.v4.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="d3-polygon-clip.js"></script>
<style>
#wip {
display: none;
position: absolute;
top: 200px;
left: 330px;
font-size: 40px;
text-align: center;
}
.control {
position: absolute;
top: 5px;
}
.control#control-0 {
left: 5px;
}
.control#control-1 {
right: 5px;
}
.control input {
width: 400px;
}
#drawing-area.dragging {
cursor: move;
}
#site-container {
clip-path: url("#clipper");
}
.seed {
fill: steelBlue;
}
.seed.dragging, .seed:hover {
fill: pink;
cursor: move;
}
.seed.group-green {
fill: green;
}
.seed.group-green.dragging, .seed.group-green:hover {
fill: pink;
cursor: move;
}
.unit-circle {
fill: none;
stroke: lightsteelBlue;
}
.unit-circle.group-green {
stroke: lightgreen;
}
.cell {
fill-opacity: 0.1;
fill: lightsteelBlue;
stroke: lightsteelBlue;
}
.cell.group-green {
fill: lightgreen;
stroke: lightgreen;
}
</style>
</head>
<body>
<div id="control-0" class="control">
Blue sites' weight :
<form>
<input id="weight" type="range" name="points" min="-10000" max="100000" value="0" oninput="weightUpdated()">
</form>
</div>
<div id="control-1" class="control">
Green sites' weight :
<form>
<input id="weight" type="range" name="points" min="-10000" max="100000" value="0" oninput="weightUpdated()">
</form>
</div>
<svg>
<defs>
<clipPath id="clipper">
<rect x="0" y="0" width="960" height="500" />
</clipPath>
</defs>
<g id="drawing-area">
<g id="cell-container"></g>
<g id="site-container"></g>
</g>
</svg>
<div id="wip">
Work in progress ...
</div>
</body>
<script>
var WITH_TRANSITION = true;
var WITHOUT_TRANSITION = false;
var duration = 250;
//begin: layout conf.
var svgWidth = 960,
svgHeight = 500,
margin = {top: 40, right: 10, bottom: 10, left: 10},
width = svgWidth - margin.left - margin.right,
height = svgHeight - margin.top - margin.bottom,
halfWidth = width/2,
halfHeight = height/2,
quarterWidth = width/4,
quarterHeight = height/4;
//end: layout conf.
//begin: voronoi stuff definitions
var blueSites = [{index: 0, group: "blue", x: halfWidth-100, y: halfHeight, weight: 0},
{index: 1, group: "blue", x: halfWidth+100, y: halfHeight, weight:0}],
greenSites = [{index: 2, group: "green", x: halfWidth-epsilon, y: halfHeight-100, weight:0},
{index: 3, group: "green", x: halfWidth, y: halfHeight+100, weight:0}],
sites = blueSites.concat(greenSites);
var clippingPolygon = [[0,0], [0,height], [width,height], [width,0]];
var cells = sites.map(function(s){ return []; }); // stores, for each site, each cell's verteces
//end: voronoi stuff definitions
//begin: utilities
function uc(w) { return (w<=0)? 0 : Math.sqrt(w); } //scale for unit-circles
var cellLiner = d3.line()
.x(function(d){ return d[0]; })
.y(function(d){ return d[1]; });
//end: utilities
//begin: reusable d3-selections
var svg = d3.select("svg"),
clipper = d3.select("#clipper>rect"),
drawingArea = d3.select("#drawing-area"),
cellContainer = d3.select("#cell-container"),
siteContainer = d3.select("#site-container");
//end: reusable d3-selections
//begin: user interaction handlers
function weightUpdated() {
var newWeights = [],
newWeigth,
group;
newWeights[0] = +d3.select("#control-0 input").node().value;
newWeights[1] = +d3.select("#control-1 input").node().value;
if (newWeights[0] !== blueSites[0].weight) {
newWeight = newWeights[0];
group = blueSites;
} else {
newWeight = newWeights[1];
group = greenSites;
}
group.forEach(function(s){ s.weight = newWeight });
computeAllCells();
redrawAllCells(WITHOUT_TRANSITION);
redrawUnitCircleOfGroup(group, WITHOUT_TRANSITION);
redrawWeightsOfGroup(group);
}
var dragSite = d3.drag()
.subject(function(d) { return d; })
.container(drawingArea.node())
.on("start", dragStarted)
.on("drag", draggingSite)
.on("end", dragEnded);
function dragStarted(d) {
d3.select(this).classed("dragging", true);
drawingArea.classed("dragging", true);
}
function dragEnded(d) {
d3.select(this).classed("dragging", false);
drawingArea.classed("dragging", false);
}
function draggingSite(d) {
var newX = Math.round(d3.event.x),
newY = Math.round(d3.event.y);
if (newX!==d.x || newY!==d.y) {
d.x = newX;
d.y = newY;
computeAllCells();
redrawAllCells(WITHOUT_TRANSITION);
redrawSite(d,WITHOUT_TRANSITION);
}
}
//end: user interaction handlers
computeAllCells();
initLayout();
redrawAllCells(WITHOUT_TRANSITION);
redrawAllUnitCircles(WITHOUT_TRANSITION);
redrawAllWeights();
redrawAllSites(WITHOUT_TRANSITION);
/***************/
/* Computation */
/***************/
function computeAllCells() {
//begin: map sites to the expected format of PowerDiagram
var formatedSites = sites.map(function(s) {
return new Vertex(s.x, s.y, null, s.weight, s, false);
})
var boundingSites = getBoundingSites();
//end: map sites to the expected format of PowerDiagram
cells = computePowerDiagramIntegrated(formatedSites, boundingSites, clippingPolygon);
}
function getBoundingSites() {
var siteBasedBounding = false; // when activated (as done in original code), resulting clipping is weird: losange-shaped clipping
var boundingSites = [],
xExtent, yExtent,
minX, maxX, minY, maxY,
x0, x1, y0, y1;
if (siteBasedBounding) {
xExtent = d3.extent(sites.map(function(s) {return s.x;}));
yExtent = d3.extent(sites.map(function(s) {return s.y;}));
} else {
xExtent = [0,width];
yExtent = [0,height];
}
minX = xExtent[0];
maxX = xExtent[1];
minY = yExtent[0];
maxY = yExtent[1];
x0 = minX - maxX;
x1 = 2 * maxX;
y0 = minY - maxY;
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++){
boundingSites.push( new Vertex(result[i][0], result[i][1], null, epsilon, new Vertex(result[i][0], result[i][1], null, epsilon, null, true), true));
}
return boundingSites;
}
/***********/
/* Drawing */
/***********/
function redrawAllSites(withTransition) {
sites.forEach(function(s){ redrawSite(s, withTransition); })
}
//redraw site = place site at adequate position
function redrawSite(site, withTransition) {
d3.select("#site-"+site.index).transition()
.duration(withTransition? duration : 0)
.attr("transform", function(d){ return "translate("+[d.x,d.y]+")"; });
}
function redrawAllWeights() {
sites.forEach(function(s){ redrawWeights(s); });
}
function redrawWeightsOfGroup(group) {
group.forEach(function(s){ redrawWeights(s); });
}
// redraw site's weight = update text
function redrawWeights(site) {
d3.select("#weight-"+site.index)
.text(function(d){ return "weight: " +d.weight; })
}
function redrawAllUnitCircles() {
sites.forEach(function(s){ redrawUnitCircle(s, WITHOUT_TRANSITION); });
}
function redrawUnitCircleOfGroup(group) {
group.forEach(function(s){ redrawUnitCircle(s, WITHOUT_TRANSITION); });
}
// redraw site's unit circle = update radius
function redrawUnitCircle(site, withTransition) {
d3.select("#unit-circle-"+site.index).transition()
.duration(withTransition? duration : 0)
.attr("r", function(d){ return uc(d.weight); })
}
function redrawAllCells(withTransition) {
var cellSelection = cellContainer.selectAll(".cell")
.data(cells, function(c){ return c.site.originalObject.index; });
cellSelection.enter()
.append("path")
.attr("class", function(d){ return "group-"+d.site.originalObject.group; })
.classed("cell", true)
.attr("id", function(d,i){ return "cell-"+d.site.originalObject.index; })
.merge(cellSelection)
.transition()
.duration(withTransition? duration : 0)
.attr("d", function(d){ return cellLiner(d)+"z"; });
cellSelection.exit().remove();
}
function initLayout () {
svg.attr("width", svgWidth)
.attr("height", svgHeight);
clipper.attr("x", 0)
.attr("y", 0)
.attr("width", width)
.attr("height", height);
drawingArea.attr("width", width)
.attr("height", height)
.attr("transform", "translate("+[margin.left, margin.top]+")");
//begin: draw sites
var drawnSites = siteContainer.selectAll(".site")
.data(sites)
.enter()
.append("g")
.attr("id", function(d){ return "site-"+d.index})
.classed("site", true);
drawnSites.append("circle")
.attr("id", function(d,i){ return "unit-circle-"+i; })
.attr("class", function(d){ return "group-"+d.group; })
.classed("unit-circle", true)
drawnSites.append("text")
.attr("id", function(d,i){ return "weight-"+i; })
.attr("transform", "translate("+[0,15]+")")
.attr("text-anchor", "middle");
drawnSites.append("circle")
.attr("id", function(d,i){ return "seed-"+i; })
.attr("class", function(d){ return "group-"+d.group; })
.classed("seed", true)
.attr("r", 4)
.call(dragSite);
//end: draw sites
//begin: draw cells
cellContainer.selectAll(".cell")
.data(cells)
.enter()
.append("path")
.attr("class", function(d){ return "group-"+d.site.originalObject.group; })
.classed("cell", true)
.attr("id", function(d,i){ return "cell-"+d.site.originalObject.index; });
//end: draw cells
}
</script>
</html>
Raw
PowerDiagram.js
// PowerDiagram.js - computePowerDiagramIntegrated() and subroutines
// IN: HEdge edge
function getFacesOfDestVertex(edge) {
var faces = [];
var previous = edge;
var first = edge.dest;
var site = first.originalObject;
var neighbours = [];
do {
previous = previous.twin.prev;
var siteOrigin = previous.orig.originalObject;
if (!siteOrigin.isDummy) {
neighbours.push(siteOrigin);
}
var iFace = previous.iFace;
if (iFace.isVisibleFromBelow()) {
faces.push(iFace);
}
} while (previous !== edge);
site.neighbours = neighbours;
return faces;
}
// IN: Omega = convex bounding polygon
// IN: S = unique set of sites with weights
// OUT: Set of lines making up the voronoi power diagram
function computePowerDiagramIntegrated(sites, boundingSites, clippingPolygon) {
ConvexHull.clear();
ConvexHull.init(boundingSites, sites);
var facets = ConvexHull.compute(sites);
var polygons = [];
var vertexCount = ConvexHull.points.length;
var verticesVisited = [];
var facetCount = facets.length;
for (var i = 0; i < facetCount; i++) {
var facet = facets[i];
if (facet.isVisibleFromBelow()) {
for (var e = 0; e < 3; e++) {
// go through the edges and start to build the polygon by going through the double connected edge list
var edge = facet.edges[e];
var destVertex = edge.dest;
var site = destVertex.originalObject;
if (!verticesVisited[destVertex.index]) {
verticesVisited[destVertex.index] = true;
if (site.isDummy) {
// Check if this is one of the sites making the bounding polygon
continue;
}
// faces around the vertices which correspond to the polygon corner points
var faces = getFacesOfDestVertex(edge);
var protopoly = [];
var lastX = null;
var lastY = null;
var dx = 1;
var dy = 1;
for (var j = 0; j < faces.length; j++) {
var point = faces[j].getDualPoint();
var x1 = point.x;
var y1 = point.y;
if (lastX !== null) {
dx = lastX - x1;
dy = lastY - y1;
if (dx < 0) {
dx = -dx;
}
if (dy < 0) {
dy = -dy;
}
}
if (dx > epsilon || dy > epsilon) {
protopoly.push([x1, y1]);
lastX = x1;
lastY = y1;
}
}
site.nonClippedPolygon = protopoly.reverse();
if (!site.isDummy && d3.polygonLength(site.nonClippedPolygon) > 0) {
var clippedPoly = d3.polygonClip(clippingPolygon, site.nonClippedPolygon);
site.polygon = clippedPoly;
clippedPoly.site = site;
if (clippedPoly.length > 0) {
polygons.push(clippedPoly);
}
}
}
}
}
}
return polygons;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment