Skip to content

Instantly share code, notes, and snippets.

Last active February 24, 2017 16:35
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
Voronoï playground : interactive weighted Voronoï study
license: lgpl-3.0

This block experiments weighted Voronoï diagram. Weighted Voronoï diagram comes in severall flavours (additive/multiplicative, powered/not-powered, 2D/3D and highier dimensions, ...), but this block focuses on the 2D additive weighted power diagram. It helps me to understand the basics (properties, underlying computations, meanings, ...) of such diagram.

From Wikipedia, the additively weighted power diagram is defined when positive weights are subtracted from the squared euclidian distances between points. The distance of a pixel from a site is the additive weighted power distance, further references as awp-distance. For any point of the 2D plan, the closest site is the one with the minimal awp-distance.

I choose this kind of weighted Voronoï diagram because the resulting tessellation is made of concave polygons/cells with straight borders, as the default Voronoï diagram does. Using non-squared distances results in hyperbolic borders.

What are you seeing ?

  • there is 2 sites (one blue and one green), with their corresponding influence areas (i.e. cells)
  • circles around sites are their respective unit-circles (awp-distance=1); they give a sense of the weight of each site
  • the matrix represents pixels and centers of pixels; for each pixel, I added the awp-distance from each site; if the awp-distance from the blue site is lower than the awp-distance from the green site, then the pixel is closer to the blue site and is part of the blue influence area (and vice-versa)

User interactions :

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

Unobvious things I've discovered :

  • the basic Voronoï diagram is obtained when all sites have the same weight; it could be 0 (default value used in Voronoï diagram algorithm), or anything else (you can experiment this by setting the exact same weight for the two sites; in this case, the border line remains at the center of the two sites)
  • when a site overweight the other (eg. when the unit-circle of the first site encloses the second site) the cell of the overweighted site still exists but the site is out of its cell (you can experiment this by maximizing the weight of one site, or drag a site inside the unit-circle of the other); if we extend the reasoning with a third site (or more), a site may no longer have any zone of influence !
  • when the two sites have the exact same position, then all depends on weights: the site with the highiest weight wins!
  • weights may be negative, but I'm not sure if this has any meaning

Acknowledgments to:

<meta charset="utf-8">
<title>Voronoï playground : interactive weighted Voronoï study</title>
<meta content="Studying Weigthed Voronoï Diagram with D3" name="description">
#under-construction {
display: none;
position: absolute;
top: 200px;
left: 250px;
font-size: 40px;
.control {
position: absolute;
top: 5px;
.control#control-0 {
left: 5px;
.control#control-1 {
right: 5px;
.control input {
width: 400px;
text {
font-size: 12px;
fill: grey;
#drawing-area.dragging {
cursor: move;
#pixel-matrix>circle {
fill: lightGrey;
stroke: none;
} text {
fill: lightsteelblue;
} text {
fill: lightgreen;
.legend path {
fill: none;
stroke: grey;
#legend-pixel-container circle {
fill: url("#radial-transparent");
.legend #legend-unit-circle-1 {
stroke: lightgreen
#site-container {
clip-path: url("#clipper");
.seed {
fill: steelBlue;
.seed.dragging, .seed:hover {
fill: pink;
cursor: move;
.seed#seed-1 {
fill: green;
.seed#seed-1.dragging, .seed#seed-1:hover {
fill: pink;
cursor: move;
.unit-circle {
fill: none;
stroke: lightsteelBlue;
.unit-circle#unit-circle-1 {
stroke: lightgreen;
.distance {
font-size: 10px;
fill: lightsteelBlue;
#site-distances-container-1>.distance {
fill: lightseagreen;
.cell {
fill-opacity: 0.1;
fill: lightsteelBlue;
stroke: lightsteelBlue;
.cell#cell-1 {
fill: lightgreen;
stroke: lightgreen;
<div id="control-0" class="control">
Blue site's weight :
<input id="weight" type="range" name="points" min="-10" max="100" value="0" oninput="weightUpdated()">
<div id="control-1" class="control">
Green site's weight :
<input id="weight" type="range" name="points" min="-10" max="100" value="0" oninput="weightUpdated()">
<clipPath id="clipper">
<rect x="0" y="0" width="960" height="500" />
<radialGradient id="radial-transparent">
<stop offset="0%" stop-color="white" stop-opacity="0"/>
<stop offset="60%" stop-color="white" stop-opacity="1"/>
<g id="drawing-area">
<g id="legend-container">
<g id="legend-pixel-container"></g>
<g id="legend-pixel-center-container"></g>
<g id="legend-unit-circle-container"></g>
<g id="pixel-matrix"></g>
<g id="cell-container"></g>
<g id="distances-container"></g>
<g id="site-container"></g>
<div id="under-construction">
<script src=""></script>
var duration = 250;
var sqrt = Math.sqrt;
function sqr(i) { return Math.pow(i, 2); };
//begin: layout conf.
var svgWidth = 960,
svgHeight = 500,
squareSize = 60, //distance between each point in the background
hSquareCount = Math.floor(svgWidth/squareSize),
vSquareCount = Math.floor(svgHeight/squareSize);
if ((hSquareCount%2)===0) { hSquareCount--; } //must be odd
if ((vSquareCount%2)===0) { vSquareCount--; } //must be odd
var hMargin = (svgWidth-hSquareCount*squareSize)/2, //2 for centering purpose
vMargin = (svgHeight-vSquareCount*squareSize)/2, //2 for centering purpose
margin = {top: vMargin, right: hMargin, bottom: vMargin, left: hMargin},
width = svgWidth - margin.left - margin.right,
height = svgHeight - - margin.bottom;
//end: layout conf.
//begin: voronoi stuff definitions
var sites = [{index: 0, x: 3, y: (vSquareCount-1)/2, weight: 0},
{index: 1, x: hSquareCount-4, y: (vSquareCount-1)/2, weight:0}];
var sitesDistances = [[],[]]; // stores, for each site, each pixel's distances
var cells = [[], []]; // stores, for each site, each cell's verteces
//end: voronoi stuff definitions
//begin: scales
function x(i) { return squareSize*i+squareSize/2; };
function y(j) { return x(j); }
function invX(x) { return (x-squareSize/2)/squareSize; };
function invY(y) { return invX(y); }
function uc(i) { return x(i)-squareSize/2; } //scale for unit-circles
var cellLiner = d3.line()
.x(function(d){ return x(d[0]); })
.y(function(d){ return y(d[1]); });
//end: scales
//begin: reusable d3-selections
var svg ="svg"),
clipper ="#clipper>rect"),
drawingArea ="#drawing-area"),
pixelMatrix ="#pixel-matrix"),
legendPixelCenterContainer ="#legend-pixel-center-container"),
legendPixelContainer ="#legend-pixel-container"),
legendUnitCircleContainer ="#legend-unit-circle-container"),
cellContainer ="#cell-container"),
distancesContainer ="#distances-container"),
siteContainer ="#site-container");
//end: reusable d3-selections
//begin: user interaction handlers
function weightUpdated() {
var newWeights = [],
newWeights[0] ="#control-0 input").node().value;
newWeights[1] ="#control-1 input").node().value;
if (newWeights[0] !== sites[0].weight) {
index = 0;
} else {
index = 1;
sites[index].weight = newWeights[index];
redrawUnitCircle(index, WITHOUT_TRANSITION);
var startX, startY;
var dragSite = d3.drag()
.subject(function(d) { return d; })
.on("start", dragStarted)
.on("drag", draggingSite)
.on("end", dragEnded);
function dragStarted(d) {"dragging", true);
drawingArea.classed("dragging", true);
startX = x(d.x);
startY = y(d.y);
function dragEnded(d) {"dragging", false);
drawingArea.classed("dragging", false);
function draggingSite(d) {
var newX = Math.round(invX(d3.event.x+startX)),
newY = Math.round(invY(d3.event.y+startY));
if (newX!==d.x || newY!==d.y) {
d.x = newX;
d.y = newY;
//end: user interaction handlers
/* Computation */
function computeAllSitesDistances() {
// compute the Additive Weighted Power Distance (awpd) of each pixel
// awpd allows to have straight lines as cells border
function computeSiteDistances (index) {
var site = sites[index],
distances = [];
distances.push({x: x, y: y, distance: awpd(x, y, site)});
sitesDistances[index] = distances;
// compute the Additive Weighted Power Distance (awpd)
// considering pixel P, site S with weight Ws,
// awpd(P,S,Ws) = ||P->S||^2 - Ws,
// where ||P->S|| is the Euclidian distance
function awpd(x, y, site) {
return sqr(x-site.x)+sqr(y-site.y)-site.weight;
//compute all cells = compute each vertex of each cell's polygon
function computeAllCells() {
var s0 = sites[0],
s1 = sites[1],
intersections = {};
//begin: handle same site's position
if (s0.x === s1.x && s0.y === s1.y) {
return true;
//end: handle same site's position
// below formula comes from ||P->S0||^2 - Ws0 = ||P->S1||^2 - Ws1
// where -> are vectors,
// and applying p->S0 = alpha*S0->S1, and p->S1 = (1-alpha)*S0->S1
var dx = s1.x-s0.x,
dy = s1.y-s0.y,
sqr_d = sqr(dx)+sqr(dy),
alpha = .5+(s0.weight-s1.weight)/(2*sqr_d),
border = {x: s0.x+alpha*dx, y: s0.y+alpha*dy, dx: -dy, dy: dx};
//begin: compute plan's bounding segments intersection with border
intersections["left"] = checkLineIntersection(border.x, border.y, border.x+border.dx, border.y+border.dy, -.5, -.5, -.5, vSquareCount-.5);
intersections["bottom"] = checkLineIntersection(border.x, border.y, border.x+border.dx, border.y+border.dy, -.5, vSquareCount-.5, hSquareCount-.5, vSquareCount-.5);
intersections["right"] = checkLineIntersection(border.x, border.y, border.x+border.dx, border.y+border.dy, hSquareCount-.5, vSquareCount-.5, hSquareCount-.5, -.5);
intersections["top"] = checkLineIntersection(border.x, border.y, border.x+border.dx, border.y+border.dy, hSquareCount-.5, -.5, -.5, -.5);
//end: compute plan's bounding segments intersection with border
computeCell(0, intersections);
computeCell(1, intersections);
// compute cell = compute each vertex of the cell's polygon
function computeCell (index, intersections) {
var s = sites[index],
sOther = sites[(index+1)%2],
defaultOrderedFullCellEdges = [
[[-.5,-.5], [-.5,vSquareCount-.5]],
[[-.5,vSquareCount-.5], [hSquareCount-.5, vSquareCount-.5]],
[[hSquareCount-.5, vSquareCount-.5], [hSquareCount-.5,-.5]],
[[hSquareCount-.5,-.5], [-.5,-.5]]
defaultOrderedEdgeTypes = ["left", "bottom", "right", "top"],
orderOffset = -1,
orderedEdgeTypes = [],
orderedFullCellEdges = [],
borderStarted = false,
borderAtCorner = false,
intersectionCount = Object.values(intersections).reduce(function (acc, intersect) { return (intersect.onSegment2)? ++acc : acc }, 0);
var cell, intersect;
//begin: handle case where cells' border is out of plan's bounding rect
if (intersectionCount===0) {
return true;
//end: handle case when cells' border is out of plan's bounding rect
if (intersectionCount===2) {
borderAtCorner = true;
//begin: find first vertex in cell
defaultOrderedFullCellEdges.forEach( function(edge, i) {
if (orderOffset === -1 && (awpd(edge[0][0], edge[0][1], s) < awpd(edge[0][0], edge[0][1], sOther))) {
orderOffset = i;
//end: find first vertex in cell
//begin: handle case when cell's boder is a corner or a plans's bounding segment
if (orderOffset===-1) {
return true;
//end: handle case when cell's boder is a corner or a plan's bounding segment
//begin: order D2 plan's bounding segments from first vertex in cell
defaultOrderedEdgeTypes.forEach(function(edgeType, i) {
//end: order D2 plan's bounding segments from first vertex in cell
//begin: walk through plan's bounding segments to compute cell's verteces
cell = [orderedFullCellEdges[0][0]];
orderedEdgeTypes.forEach( function(edgeType, i) {
intersect = intersections[edgeType];
if (intersect.onSegment2) {
if (!borderStarted) {
if (borderAtCorner || cell[cell.length-1][0]!==intersect.x || cell[cell.length-1][1]!==intersect.y) {
if (cell.length !== 1) {
cell.push([intersect.x, intersect.y]);
borderStarted = !borderStarted;
} else {
if (borderAtCorner || cell[cell.length-1][0]!==intersect.x || cell[cell.length-1][1]!==intersect.y) {
cell.push([intersect.x, intersect.y]);
borderStarted = !borderStarted;
} else {
if (!borderStarted) {
cells[index] = cell;
//end: walk through plan's bounding segments to compute cell's verteces
function computeEmptyAndFullCells () {
if (sitesDistances[0][0].distance < sitesDistances[1][0].distance) {
} else {
// compute full cell = cell verteces are the plan's bounding verteces
function computeFullCell (index) {
cells[index] = [[-.5,-.5], [-.5,vSquareCount-.5], [hSquareCount-.5, vSquareCount-.5], [hSquareCount-.5,-.5]];
// compute empty cell = cell verteces becomes empty
function computeEmptyCell (index) {
var s = sites[index];
cells[index] = [[s.x, s.y], [s.x, s.y], [s.x, s.y], [s.x, s.y]];
/* Drawing */
function initLayout () {
svg.attr("width", svgWidth)
.attr("height", svgHeight);
clipper.attr("x", x(-.5))
.attr("y", y(-.5))
.attr("width", (hSquareCount)*squareSize)
.attr("height", (vSquareCount)*squareSize);
drawingArea.attr("width", width)
.attr("height", height)
.attr("transform", "translate("+[margin.left,]+")");
//begin: draw pixel centers matrix
var pixelData = [];
pixelData.push({x: x, y: y});
.attr("r", 2)
.attr("cx", function(d){ return x(d.x); })
.attr("cy", function(d){ return y(d.y); });
//end: draw pixel centers matrix
//begin: draw sites
var drawnSites = siteContainer.selectAll(".site")
.attr("id", function(d){ return "site-"+d.index})
.classed("site", true);
.attr("id", function(d,i){ return "unit-circle-"+i; })
.classed("unit-circle", true)
.attr("id", function(d,i){ return "weight-"+i; })
.attr("transform", "translate("+[0,15]+")")
.attr("text-anchor", "middle");
.attr("id", function(d,i){ return "seed-"+i; })
.classed("seed", true)
.attr("r", 4)
//end: draw sites
//begin: draw distances
.classed("site-distances-container", true)
.attr("id", function(d,i){ return "site-distances-container-"+i;});
var textAnchor = (i===0)? "end" : "start";
var dx = (i===0)? -6 : 6;"#site-distances-container-"+i).selectAll("distance")
.classed("distance", true)
.attr("dx", dx)
.attr("dy", 3)
.attr("text-anchor", textAnchor);
//end: draw distances
//begin: draw cells
.classed("cell", true)
.attr("id", function(d,i){ return "cell-"+i; });
//end: draw cells
//begin: draw legends
legendPixelCenterContainer.attr("transform", "translate("+[x(4),y(vSquareCount-1)]+")");
var legend = legendPixelCenterContainer.append("g")
.classed("legend", true);
.attr("d", "M0,5v23");
.attr("y", 40)
.attr("text-anchor", "middle")
.text("center of a pixel");
legend = legendPixelCenterContainer.append("g")
.classed("legend site-0", true);
.attr("d", "M-10,7v45h-5");
.attr("y", 53)
.attr("x", -20)
.attr("text-anchor", "end")
.text("awp-distance from blue site");
legend = legendPixelCenterContainer.append("g")
.classed("legend site-1", true);
.attr("d", "M10,7v45h5");
.attr("y", 53)
.attr("x", 20)
.attr("text-anchor", "start")
.text("awp-distance from green site");
legendPixelContainer.classed("legend", true);
.attr("d", function(d) {
return "M"+[x(i-.5), y(vSquareCount-.5)]+"v-"+3*squareSize;
.attr("d", function(d) {
return "M"+[x(-.5), y(vSquareCount-i-.5)]+"h"+3*squareSize;
.attr("cx", x(-.5))
.attr("cy", y(vSquareCount-.5))
.attr("r", 5*squareSize);
.attr("d", "M"+[x(0),y(vSquareCount-.5)]+"v5");
.attr("x", x(0))
.attr("y", y(vSquareCount-.5)+15)
.attr("text-anchor", "middle")
.text("pixel matrix");
legendUnitCircleContainer.classed("legend", true)
.attr("transform", "translate("+[x(8),y(vSquareCount-.25)]+")");
.attr("cx", function(d) { return d*25; })
.attr("r", 10)
.classed("unit-circle", true)
.attr("id", function(d){ return "legend-unit-circle-"+d; });
.attr("transform", "translate("+[40,3]+")")
.text(": unit-circles, give a sense of the weight of each site")
//end: draw legends
function redrawAllSites(withTransition) {
redrawSite(0, withTransition);
redrawSite(1, withTransition);
//redraw site = place site at adequate position
function redrawSite(index, withTransition) {"#site-"+index).transition()
.duration(withTransition? duration : 0)
.attr("transform", function(d){ return "translate("+[x(d.x),y(d.y)]+")"; });
function redrawAllWeights() {
// redraw site's weight = update text
function redrawWeights(index) {"#weight-"+index)
.text(function(d){ return "weight: " +d.weight; })
function redrawAllUnitCircles() {
// redraw site's unit circle = update radius
function redrawUnitCircle(index, withTransition) {"#unit-circle-"+index).transition()
.duration(withTransition? duration : 0)
.attr("r", function(d){ return (d.weight>=-1)? uc(sqrt(d.weight+1)):0; })
function redrawAllSitesDistances() {
// redraw site's distances = redraw the distances to the site of each pixel
function redrawSiteDistances(index) {"#site-distances-container-"+index).selectAll(".distance")
.attr("x", function(d){ return x(d.x); })
.attr("y", function(d){ return x(d.y); })
.text(function(d){ return Math.round(d.distance); })
function redrawAllCells(withTransition) {
// redraw cells = redraw each polygon"#cell-container").selectAll(".cell")
.duration(withTransition? duration : 0)
.attr("d", function(d){ return cellLiner(d)+"z"; });
/* line-line intersection coordinates */
/* from */
function checkLineIntersection(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY) {
// if the lines intersect, the result contains the x and y of the intersection (treating the lines as infinite) and booleans for whether line segment 1 or line segment 2 contain the point
var denominator, a, b, numerator1, numerator2, result = {
x: null,
y: null,
onSegment1: false,
onSegment2: false
denominator = ((line2EndY - line2StartY) * (line1EndX - line1StartX)) - ((line2EndX - line2StartX) * (line1EndY - line1StartY));
if (denominator == 0) {
return result;
a = line1StartY - line2StartY;
b = line1StartX - line2StartX;
numerator1 = ((line2EndX - line2StartX) * a) - ((line2EndY - line2StartY) * b);
numerator2 = ((line1EndX - line1StartX) * a) - ((line1EndY - line1StartY) * b);
a = numerator1 / denominator;
b = numerator2 / denominator;
// if we cast these lines infinitely in both directions, they intersect here:
result.x = line1StartX + (a * (line1EndX - line1StartX));
result.y = line1StartY + (a * (line1EndY - line1StartY));
// it is worth noting that this should be the same as:
x = line2StartX + (b * (line2EndX - line2StartX));
y = line2StartY + (b * (line2EndY - line2StartY));
// if line1 is a segment and line2 is infinite, they intersect if:
if (a >= 0 && a <= 1) {
result.onSegment1 = true;
// if line2 is a segment and line1 is infinite, they intersect if:
if (b >= 0 && b <= 1) {
result.onSegment2 = true;
// if line1 and line2 are segments, they intersect if both of the above are true
return result;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment