This block experiments the Lloyd’s relaxation algorithm on weighted sites.
This block is an adaptation of veltam‘s Voronoi relaxation block, which applies the algorithm to basic, non-weigthed, sites.
At each iteration
The algorithm stops when each site no longer moves (more exactly, when each site moves below a certain treshold).
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<title>Voronoï playground: weighted Voronoï relaxation</title>
<meta name="description" content="Lloyd's algorithm applied to weighted sites, using D3.js and the d3-weighted-voronoi plugin">
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://raw.githack.com/Kcnarf/d3-weighted-voronoi/master/build/d3-weighted-voronoi.js"></script>
<style>
#layouter {
text-align: center;
position: relative;
}
#wip {
display: none;
position: absolute;
top: 200px;
left: 330px;
font-size: 40px;
text-align: center;
}
.control {
position: absolute;
}
.control.top{
top: 5px;
}
.control.bottom {
bottom: 5px;
}
.control.left{
left: 5px;
}
.control.right {
right: 5px;
}
.control.right div{
text-align: right;
}
.control.left div{
text-align: left;
}
.control .separator {
height: 5px;
}
canvas {
margin: 1px;
border-radius: 1000px;
box-shadow: 2px 2px 6px grey;
}
canvas#background-image, canvas#alpha {
display: none;
}
</style>
</head>
<body>
<div id="layouter">
<canvas id="background-image"></canvas>
<canvas id="alpha"></canvas>
<canvas id="colored"></canvas>
<div id="control0" class="control top left">
<div>
<input id="cellsOrCircles" type="radio" name="cellsOrCircles" value="cells" checked onchange="cellsOrCirclesUpdated('cells')"> Weighted Voronoï
</div>
<div>
<input id="cellsOrCircles" type="radio" name="cellsOrCircles" value="circles" onchange="cellsOrCirclesUpdated('circles')"> Weights
</div>
</div>
<div id="control1" class="control bottom left">
<div>
<input id="showSites" type="checkbox" name="showSites" onchange="siteVisibilityUpdated()"> Show sites
</div>
</div>
<div id="control2" class="control bottom right">
<div>
Grey <input id="bgImgGrey" type="radio" name="bgImg" onchange="bgImgUpdated('grey')">
</div>
<div>
Radial rainbow <input id="bgImgRadialRainbow" type="radio" name="bgImg" onchange="bgImgUpdated('radialRainbow')">
</div>
<div>
Canonical rainbow <input id="bgImgCanonicalRainbow" type="radio" name="bgImg" checked onchange="bgImgUpdated('canonicalRainbow')">
</div>
</div>
<div id="wip">
Work in progress ...
</div>
</div>
<script>
var _2PI = 2*Math.PI,
sqrt = Math.sqrt,
sqr = function(d) { return Math.pow(d,2); };
//begin: layout conf.
var totalWidth = 550,
totalHeight = 500,
controlsHeight = 0,
canvasRadius = (totalHeight-controlsHeight)/2,
canvasbw = 1, //canvas border width
canvasHeight = 2*canvasRadius,
canvasWidth = 2*canvasRadius,
radius = canvasRadius-canvasbw,
width = 2*canvasRadius,
height = 2*canvasRadius,
halfRadius = radius/2
halfWidth = halfRadius,
halfHeight = halfRadius,
quarterRadius = radius/4;
quarterWidth = quarterRadius,
quarterHeight = quarterRadius;
//end: layout conf.
//begin: drawing conf.
var drawSites = false,
bgType = "canonicalRainbow",
drawCellsOrCircles = "cells",
bgImgCanvas, alphaCanvas, coloredCanvas,
bgImgContext, alphaContext, coloredContext,
radialGradient;
//end: drawing conf.
//begin: init layout
initLayout()
//end: init layout
//begin: weighted voronoi conf.
var siteCount = 100,
maxWeight = 2000,
convergenceTreshold = 0.1;
var circlingPolygon = [];
for (a=0; a<_2PI; a+=_2PI/60) {
circlingPolygon.push([(radius+1)*(1+Math.cos(a)), (radius+1)*(1+Math.sin(a))])
}
var weightedVoronoi = d3.weightedVoronoi().clip(circlingPolygon);
//end: weighted voronoi conf.
//begin: user interaction handlers
function siteVisibilityUpdated() {
drawSites = d3.select("#showSites").node().checked;
}
function bgImgUpdated(newType) {
bgType = newType;
setBackgroundImage();
}
function cellsOrCirclesUpdated(type) {
drawCellsOrCircles = type;
}
//end: user interaction handlers
function relax(points) {
var polygons = weightedVoronoi(points),
centroids = polygons.map(d3.polygonCentroid),
pointIdToPolyAndCenter = {},
someOverweightedPoints = (points.length > polygons.length),
converged;
polygons.forEach(function(polygon) {
pointIdToPolyAndCenter[polygon.site.originalObject.index] = {
point: polygon.site.originalObject,
polygon: polygon,
centroid: d3.polygonCentroid(polygon)
}
});
if (someOverweightedPoints) {
console.log("Overweighted points: "+(points.length-polygons.length));
//insert overweighted points at a random corner of a random polygon
for(var i=0; i<siteCount; i++) {
if (pointIdToPolyAndCenter[i] === undefined) {
someOverweightedPoints = true;
randPoly = polygons[Math.floor(polygons.length*Math.random())];
randCorner = randPoly[Math.floor(randPoly.length*Math.random())]
pointIdToPolyAndCenter[i] = {
point: points[i],
polygon: null,
centroid: randCorner
}
}
}
converged = false;
} else {
console.log("No overweighted point");
converged = polygons.every(function(p, i){
return distance(p.site.originalObject, centroids[i]) < convergenceTreshold;
});
}
redraw(points, polygons);
if (converged) {
setTimeout(reset, 750);
} else {
setTimeout(function(){
var newPoints = [];
for(i=0;i<siteCount; i++) {
data = pointIdToPolyAndCenter[i];
newPoints.push({
index: data.point.index,
x: data.centroid[0],
y: data.centroid[1],
weight: data.point.weight,
sqrtWeight: data.point.sqrtWeight
});
}
relax(newPoints);
}, 50);
}
}
function distance(p, c) {
return sqrt(sqr(p.x - c[0], 2) + sqr(p.y - c[1], 2));
}
function reset() {
var points = [];
var x, y, weight;
for (i=0; i<siteCount; 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 (sqrt(sqr(x-radius)+sqr(y-radius))>radius) {
x = width*Math.random();
y = height*Math.random();
}
weight = sqr(Math.random()) * maxWeight
points.push({
index: i,
x: x,
y: y,
weight: weight,
sqrtWeight: sqrt(weight)
});
}
alphaContext.clearRect(0, 0, width, height);
redraw(points, weightedVoronoi(points));
setTimeout(function(){
relax(points);
}, 750);
};
reset();
/********************************/
/* Drawing functions */
/* Playing with canvas :-) */
/* */
/* Experiment to draw */
/* with a uniform color, */
/* or with a radial gradient, */
/* or over a background image */
/********************************/
function initLayout() {
d3.select("#layouter").style("width", totalWidth+"px").style("height", totalHeight+"px");
d3.selectAll("canvas").attr("width", canvasWidth).attr("height", canvasHeight);
bgImgCanvas = document.querySelector("canvas#background-image");
bgImgContext = bgImgCanvas.getContext("2d");
alphaCanvas = document.querySelector("canvas#alpha");
alphaContext = alphaCanvas.getContext("2d");
coloredCanvas = document.querySelector("canvas#colored");
coloredContext = coloredCanvas.getContext("2d");
//begin: set a radial rainbow
radialGradient = coloredContext.createRadialGradient(radius, radius, 0, radius, radius, radius);
var gradientStopNumber = 10,
stopDelta = 0.9/gradientStopNumber;
hueDelta = 360/gradientStopNumber,
stop = 0.1,
hue = 0;
while (hue<360) {
radialGradient.addColorStop(stop, d3.hsl(Math.abs(hue+160), 1, 0.45));
stop += stopDelta;
hue += hueDelta;
}
//end: set a radial rainbow
//begin: set the background image
setBackgroundImage();
//end: set the initial background image
}
function setBackgroundImage() {
if (bgType==="canonicalRainbow") {
//begin: make conical rainbow gradient
var imageData = bgImgContext.getImageData(0, 0, 2*radius, 2*radius);
var i = -radius,
j = -radius,
pixel = 0,
radToDeg = 180/Math.PI;
var aRad, aDeg, rgb;
while (i<radius) {
j = -radius;
while (j<radius) {
aRad = Math.atan2(j, i);
aDeg = aRad*radToDeg;
rgb = d3.hsl(aDeg, 1, 0.45).rgb();
imageData.data[pixel++] = rgb.r;
imageData.data[pixel++] = rgb.g;
imageData.data[pixel++] = rgb.b;
imageData.data[pixel++] = 255;
j++;
}
i++;
}
bgImgContext.putImageData(imageData, 0, 0);
//end: make conical rainbow gradient
} else if (bgType==="radialRainbow") {
bgImgContext.fillStyle = radialGradient;
bgImgContext.fillRect(0, 0, canvasWidth, canvasHeight);
} else {
bgImgContext.fillStyle = "grey";
bgImgContext.fillRect(0, 0, canvasWidth, canvasHeight);
}
}
function redraw(points, polygons) {
// At each iteration:
// 1- update the 'alpha' canvas
// 1.1- fade 'alpha' canvas to simulate passing time
// 1.2- add the new tessellation/weights to the 'alpha' canvas
// 2- blend 'background-image' and 'alpha' => produces colorfull rendering
alphaContext.lineWidth= 2;
fade();
alphaContext.beginPath();
//begin: add the new tessellation/weights (to the 'grey-scale' canvas)
if (drawCellsOrCircles==="cells") {
alphaContext.globalAlpha = 0.5;
polygons.forEach(function(polygon){
addCell(polygon);
});
} else {
alphaContext.globalAlpha = 0.2;
points.forEach(function(point){
addWeight(point);
});
}
//begin: add the new tessellation/weights (to the 'grey-scale' canvas)
if (drawSites) {
//begin: add sites (to 'grey-scale' canvas)
alphaContext.globalAlpha = 1;
points.forEach(function(point){
addSite(point);
});
//begin: add sites (to 'grey-scale' canvas)
}
alphaContext.stroke();
//begin: use 'background-image' to color pixels of the 'grey-scale' canvas
coloredContext.clearRect(0, 0, canvasWidth, canvasHeight);
coloredContext.globalCompositeOperation = "source-over";
coloredContext.drawImage(bgImgCanvas, 0, 0);
coloredContext.globalCompositeOperation = "destination-in";
coloredContext.drawImage(alphaCanvas, 0, 0);
//begin: use 'background-image' to color pixels of the 'grey-scale' canvas
}
function addCell(polygon) {
alphaContext.moveTo(polygon[0][0], polygon[0][1]);
polygon.slice(1).forEach(function(vertex){
alphaContext.lineTo(vertex[0], vertex[1]);
});
alphaContext.lineTo(polygon[0][0], polygon[0][1]);
}
function addWeight(point) {
alphaContext.moveTo(point.x+point.sqrtWeight, point.y);
alphaContext.arc(point.x, point.y, point.sqrtWeight, 0, _2PI);
}
function addSite(point) {
alphaContext.moveTo(point.x, point.y);
alphaContext.arc(point.x, point.y, 1, 0, _2PI);
}
function fade() {
var imageData = alphaContext.getImageData(0, 0, canvasWidth, canvasHeight);
for (var i = 3, l = imageData.data.length; i < l; i += 4) {
imageData.data[i] = Math.max(0, imageData.data[i] - 10);
}
alphaContext.putImageData(imageData, 0, 0);
}
</script>
</body>
</html>