Skip to content

Instantly share code, notes, and snippets.

@Kcnarf

Kcnarf/.block

Last active July 19, 2019 20:52
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save Kcnarf/7d7f60ef86a77851c38c51904f4c8d39 to your computer and use it in GitHub Desktop.
Save Kcnarf/7d7f60ef86a77851c38c51904f4c8d39 to your computer and use it in GitHub Desktop.
Download ZIP
Voronoï playground: Voronoï transitioning thanks to weighted Voronoï
Raw
.block
license: mit
border: no
Raw
README.md

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

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

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

User interactions :

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

Acknowledgments to :

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.y/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: Voronoï transitioning thanks to weighted Voronoï</title>
<meta name="description" content="Transitioning from one Voronoï tessellation to another thanks to Weighted Voronoï, using D3.js and the d3-weighted-voronoi plugin">
<script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script>
<script src="https://rawcdn.githack.com/Kcnarf/d3-weighted-voronoi/v1.0.0/build/d3-weighted-voronoi.js"></script>
<style>
#wip {
display: none;
position: absolute;
top: 200px;
left: 330px;
font-size: 40px;
text-align: center;
}
.control {
position: absolute;
top: 5px;
}
.control#control-0 {
left: 5px;
text-align: center;
}
.control#control-1 {
left: 5px;
top: 25px;
}
.control#control-2 {
right: 460px;
top: 25px;
}
.control span {
width: 100px;
}
.control input[type="range"] {
width: 210px;
}
svg {
position: absolute;
top: 25px;
left: 15px;
margin: 1px;
border-radius: 1000px;
box-shadow: 2px 2px 6px grey;
}
#site-container {
clip-path: url("#clipper");
}
.seed {
fill: steelblue;
}
.seed.group-green {
fill: lightgreen;
}
.seed.hide {
display: none;
}
.cell {
fill-opacity: 0.1;
fill: lightsteelBlue;
stroke: lightsteelBlue;
}
.cell.group-green {
fill: lightgreen;
stroke: lightgreen;
}
</style>
</head>
<body>
<svg>
<defs>
<clipPath id="clipper">
<rect x="0" y="0" width="960" height="500" />
</clipPath>
</defs>
<g id="drawing-area">
<g id="cell-container"></g>
<g id="site-container"></g>
</g>
</svg>
<div id="control-0" class="control">
<span>Voronoï of blue sites</span>
<input id="weight" type="range" name="points" min="-5000" max="5000" value="0" oninput="weightUpdated()">
<span>Voronoï of green sites</span>
</div>
<div id="control-1" class="control">
<span>Show blue sites</span>
<input id="weight" type="checkbox" name="showSites" onchange="blueSiteVisibilityUpdated()">
</div>
<div id="control-2" class="control">
<input id="weight" type="checkbox" name="showSites" onchange="greenSiteVisibilityUpdated()">
<span>Show green sites</span>
</div>
<div id="wip">
Work in progress ...
</div>
</body>
<script>
var WITH_TRANSITION = true;
var WITHOUT_TRANSITION = false;
var duration = 250;
var _2PI = 2*Math.PI;
//begin: layout conf.
var totalHeight = 500,
controlsHeight = 30,
svgRadius = (totalHeight-controlsHeight)/2,
svgbw = 1, //svg border width
svgHeight = 2*svgRadius,
svgWidth = 2*svgRadius,
radius = svgRadius-svgbw,
width = 2*svgRadius,
height = 2*svgRadius,
halfRadius = radius/2
halfWidth = halfRadius,
halfHeight = halfRadius,
quarterRadius = radius/4;
quarterWidth = quarterRadius,
quarterHeight = quarterRadius;
//end: layout conf.
//begin: voronoi stuff definitions
var siteCount = 120,
quarterSiteCount = siteCount/4;
var blueSites = [],
greenSites = [];
var baseWeight = 10000,
x, y;
for (i=0; i<quarterSiteCount; i++) {
//use (x,y) instead of (r,a) for a better uniform (ie. less centered) placement of sites
x = width*Math.random();
y = height*Math.random();
while (Math.sqrt(Math.pow(x-radius,2)+Math.pow(y-radius,2))>radius) {
x = width*Math.random();
y = height*Math.random();
}
blueSites.push({index: i, group: "blue", x: x, y: y, weight: baseWeight});
[0,1,2].forEach(function () {
x = width*Math.random();
y = height*Math.random();
while (Math.sqrt(Math.pow(x-radius,2)+Math.pow(y-radius,2))>radius) {
x = width*Math.random();
y = height*Math.random();
}
greenSites.push({index: i+siteCount, group: "green", x: x, y: y, weight: baseWeight});
})
}
var sites = blueSites.concat(greenSites);
var clippingPolygon = [[0,0], [0,height], [width,height], [width,0]];
var weightedVoronoi = d3.weightedVoronoi().clip(clippingPolygon);
var cells = sites.map(function(s){ return []; }); // stores, for each site, each cell's verteces
//end: voronoi stuff definitions
//begin: utilities
var cellLiner = d3.line()
.x(function(d){ return d[0]; })
.y(function(d){ return d[1]; });
//end: utilities
//begin: reusable d3-selections
var svg = d3.select("svg"),
clipper = d3.select("#clipper>rect"),
drawingArea = d3.select("#drawing-area"),
cellContainer = d3.select("#cell-container"),
siteContainer = d3.select("#site-container");
//end: reusable d3-selections
//begin: user interaction handlers
function weightUpdated() {
var deltaWeight,
newBlueWeigth,
newGreenWeight;
deltaWeight = +d3.select("#control-0 input").node().value;
newBlueWeigth = baseWeight - deltaWeight;
newGreenWeight = baseWeight + deltaWeight;
blueSites.forEach(function(s){ s.weight = newBlueWeigth });
greenSites.forEach(function(s){ s.weight = newGreenWeight });
computeAllCells();
redrawAllCells(WITHOUT_TRANSITION);
}
function blueSiteVisibilityUpdated() {
visibility = d3.select("#control-1 input").node().checked? 1:0;
redrawGroup("blue", visibility , WITH_TRANSITION);
}
function greenSiteVisibilityUpdated() {
visibility = d3.select("#control-2 input").node().checked? 1:0;
redrawGroup("green", visibility, WITH_TRANSITION);
}
//end: user interaction handlers
computeAllCells();
initLayout();
redrawAllCells(WITHOUT_TRANSITION);
/***************/
/* Computation */
/***************/
function computeAllCells() {
cells = weightedVoronoi(sites);
}
/***********/
/* Drawing */
/***********/
//redraw group = show/hide sites of particular group
function redrawGroup(color, finalOpacity, withTransition) {
siteContainer.selectAll(".seed").filter(function(d){ return d.group === color; })
.transition()
.duration(withTransition? duration : 0)
.attr("opacity", finalOpacity);
}
function redrawAllCells(withTransition) {
var cellSelection = cellContainer.selectAll(".cell")
.data(cells, function(c){ return c.site.originalObject.index; });
cellSelection.enter()
.append("path")
.attr("class", function(d){ return "group-"+d.site.originalObject.group; })
.classed("cell", true)
.attr("id", function(d,i){ return "cell-"+d.site.originalObject.index; })
.merge(cellSelection)
.transition()
.duration(withTransition? duration : 0)
.attr("d", function(d){ return cellLiner(d)+"z"; });
cellSelection.exit().remove();
}
function initLayout () {
svg.attr("width", svgWidth)
.attr("height", svgHeight);
clipper.attr("x", 0)
.attr("y", 0)
.attr("width", width)
.attr("height", height);
drawingArea.attr("width", width)
.attr("height", height)
.attr("transform", "translate("+[svgbw, svgbw]+")");
//begin: draw sites
var drawnSites = siteContainer.selectAll(".site")
.data(sites)
.enter()
.append("g")
.attr("id", function(d){ return "site-"+d.index})
.classed("site", true);
drawnSites.append("circle")
.attr("id", function(d,i){ return "seed-"+i; })
.attr("class", function(d){ return "group-"+d.group; })
.classed("seed", true)
.attr("r", 2)
.attr("opacity", 0)
.attr("transform", function(d){ return "translate("+[d.x,d.y]+")"; });;
//end: draw sites
//begin: draw cells
cellContainer.selectAll(".cell")
.data(cells)
.enter()
.append("path")
.attr("class", function(d){ return "group-"+d.site.originalObject.group; })
.classed("cell", true)
.attr("id", function(d,i){ return "cell-"+d.site.originalObject.index; });
//end: draw cells
}
</script>
</html>
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