|
<html lang="en"> |
|
<head> |
|
<meta charset="utf-8" /> |
|
<title>Voronoï playground: Voronoï map (study)</title> |
|
<meta name="description" content="Voronoi map in D3.js (study)"> |
|
<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: 220px; |
|
left: 120px; |
|
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 _PI = Math.PI, |
|
_2PI = 2*Math.PI, |
|
sqrt = Math.sqrt, |
|
sqr = function(d) { return Math.pow(d,2); } |
|
epsilon = 1; |
|
|
|
//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: voronoi treemap conf. |
|
var circlingPolygon = computeCyclingPolygon(), |
|
weightedVoronoi = d3.weightedVoronoi().clip(circlingPolygon), |
|
siteCount = 20, |
|
baseWeight = 2000, |
|
convergenceTreshold = 0.01, // 0.01 means 1% error |
|
totalArea = Math.abs(d3.polygonArea(circlingPolygon)), |
|
areaErrorTreshold = convergenceTreshold*totalArea, |
|
maxIterationCount = 100, |
|
useMaxIterationCount = true; |
|
var totalWeight, avgWeight; |
|
//end: voronoi treemap conf. |
|
|
|
function computeCyclingPolygon() { |
|
var circlingPolygon = []; |
|
for (a=0; a<_2PI; a+=_2PI/60) { |
|
circlingPolygon.push( |
|
[radius+0.5+(radius)*Math.cos(a), radius+0.5+(radius)*Math.sin(a)] |
|
) |
|
} |
|
return circlingPolygon; |
|
}; |
|
|
|
//begin: user interaction handlers |
|
function siteVisibilityUpdated() { |
|
drawSites = d3.select("#showSites").node().checked; |
|
}; |
|
|
|
function bgImgUpdated(newType) { |
|
bgType = newType; |
|
resetBackgroundImage() ; |
|
}; |
|
|
|
function cellsOrCirclesUpdated(type) { |
|
drawCellsOrCircles = type; |
|
}; |
|
//end: user interaction handlers |
|
|
|
function adapt(polygons, iterationCount) { |
|
var converged, adaptedTreemapPoints; |
|
|
|
adaptedTreemapPoints = adaptPlacementsAndWeights(polygons); |
|
polygons = weightedVoronoi(adaptedTreemapPoints); |
|
if (polygons.length<siteCount) { |
|
console.log("at least 1 site has no area, which is not supposed to arise"); |
|
debugger; |
|
} |
|
|
|
// below code is for experimentation purpose: draw iterimediate state |
|
// redraw(adaptedTreemapPoints, polygons); |
|
|
|
adaptedTreemapPoints = adaptWeights(polygons); |
|
polygons = weightedVoronoi(adaptedTreemapPoints); |
|
if (polygons.length<siteCount) { |
|
console.log("at least 1 site has no area, which is not supposed to arise"); |
|
debugger; |
|
} |
|
|
|
redraw(adaptedTreemapPoints, polygons); |
|
|
|
converged = overallConvergence(polygons); |
|
|
|
if (useMaxIterationCount && iterationCount===maxIterationCount) { |
|
console.log("Max iteration reached") |
|
setTimeout(reset, 1750); |
|
} else { |
|
if (converged) { |
|
console.log("Stopped at iteration "+iterationCount); |
|
setTimeout(reset, 1750); |
|
} else { |
|
setTimeout(function(){ |
|
adapt(polygons, iterationCount+1); |
|
}, 50); |
|
} |
|
} |
|
}; |
|
|
|
function adaptPlacementsAndWeights(polygons) { |
|
var newTreemapPoints = []; |
|
var polygon, treemapPoint, centroid, minDistance, adaptedWeight; |
|
|
|
for(var i=0; i<siteCount; i++) { |
|
polygon = polygons[i]; |
|
treemapPoint = polygon.site.originalObject; |
|
centroid = d3.polygonCentroid(polygon); |
|
|
|
// in original block, non clipped polygon was used, don't know why |
|
minDistance = minDistanceToBorders(polygon, centroid); |
|
|
|
adaptedWeight = Math.min(treemapPoint.weight, sqr(minDistance)); |
|
adaptedWeight = Math.max(adaptedWeight, epsilon); |
|
|
|
newTreemapPoints.push({ |
|
index: treemapPoint.index, |
|
targetedArea: treemapPoint.targetedArea, |
|
data: treemapPoint.data, |
|
x: centroid[0], |
|
y: centroid[1], |
|
weight: adaptedWeight |
|
}); |
|
} |
|
|
|
return newTreemapPoints; |
|
}; |
|
|
|
function adaptWeights(polygons) { |
|
var newTreemapPoints = []; |
|
var polygon, treemapPoint, currentArea, adaptRatio, maxDistance, adaptedWeight; |
|
|
|
for(var i=0; i<siteCount; i++) { |
|
polygon = polygons[i]; |
|
treemapPoint = polygon.site.originalObject; |
|
currentArea = d3.polygonArea(polygon); |
|
adaptRatio = treemapPoint.targetedArea/currentArea; |
|
|
|
adaptedWeight = treemapPoint.weight*sqr(adaptRatio); |
|
maxDistance = distanceToNearestNeighbour(polygons, polygon.site); |
|
|
|
adaptedWeight = Math.min(adaptedWeight, sqr(maxDistance)); |
|
|
|
newTreemapPoints.push({ |
|
index: treemapPoint.index, |
|
targetedArea: treemapPoint.targetedArea, |
|
data: treemapPoint.data, |
|
x: treemapPoint.x, |
|
y: treemapPoint.y, |
|
weight: adaptedWeight |
|
}); |
|
} |
|
|
|
return newTreemapPoints; |
|
}; |
|
|
|
// http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line |
|
function minDistanceToBorders(polygon, point) { |
|
var minDistanceToBorders; |
|
|
|
for (var i=0; i<polygon.length; i++) { |
|
var p1 = polygon[i]; |
|
var p2 = polygon[(i+1)%polygon.length]; |
|
|
|
var dx = p2[0] - p1[0]; |
|
var dy = p2[1] - p1[1]; |
|
|
|
var d = Math.abs(dy*point[0] - dx*point[1] + p2[0]*p1[1] - p1[0]*p2[1]) / Math.sqrt(dx*dx + dy*dy); |
|
|
|
if (i===0 || d<minDistanceToBorders) { |
|
minDistanceToBorders = d; |
|
} |
|
} |
|
|
|
return minDistanceToBorders; |
|
}; |
|
|
|
function distanceToNearestNeighbour(polygons, site) { |
|
// may be optimized by knowing neighbours of each site |
|
var minDistance = Infinity; |
|
var d; |
|
|
|
for (var i=0; i<siteCount; i++) { |
|
if (polygons[i].site!=site) { |
|
d = distance(polygons[i].site, site); |
|
if (d < minDistance) { |
|
minDistance = d; |
|
} |
|
} |
|
} |
|
return minDistance; |
|
}; |
|
|
|
function squaredDistance(s0, s1) { |
|
return sqr(s1.x - s0.x) + sqr(s1.y - s0.y); |
|
}; |
|
|
|
function distance(s0, s1) { |
|
return sqrt(squaredDistance(s0, s1)); |
|
}; |
|
|
|
function computeAreaError (polygons) { |
|
//convergence based on summation of all sites current areas |
|
var areaErrorSum = 0; |
|
var polygon, treemapPoint, currentArea, areaError; |
|
for(var i=0; i<siteCount; i++) { |
|
polygon = polygons[i]; |
|
treemapPoint = polygon.site.originalObject; |
|
currentArea = d3.polygonArea(polygon); |
|
areaError = Math.abs(treemapPoint.targetedArea-currentArea); |
|
areaErrorSum += areaError; |
|
} |
|
return areaErrorSum; |
|
}; |
|
|
|
function overallConvergence(polygons) { |
|
//convergence based on summation of all sites current areas |
|
var areaError = computeAreaError(polygons); |
|
console.log("error %: "+Math.round(areaError*100*1000/totalArea)/1000); |
|
return areaError < areaErrorTreshold; |
|
}; |
|
|
|
function reset() { |
|
var basePoints = []; |
|
var weight, treemapPoints, polygons; |
|
|
|
//begin: create points |
|
for (i=0; i<siteCount; i++) { |
|
weight = (0+1*sqr(Math.random()))*baseWeight; |
|
// if (i%10===0) { weight = 10*baseWeight; } |
|
// weight = (i+1)*maxWeight; //weights of 0 are not handled |
|
// weight = i+1; //weights of 0 are not handled |
|
basePoints.push({ |
|
index: i, |
|
weight: weight |
|
}); |
|
} |
|
//end: create points |
|
|
|
// create treemap-related points |
|
// (with targetArea, and initial placement) |
|
// choose among several inital placement policies: random/pie/sortedPie |
|
treemapPoints = createTreemapPoints(basePoints, 'random'); |
|
polygons = weightedVoronoi(treemapPoints); |
|
|
|
alphaContext.clearRect(0, 0, width, height); |
|
redraw(treemapPoints, polygons); |
|
setTimeout(function(){ |
|
adapt(polygons, 0); |
|
}, 1500); |
|
|
|
}; |
|
|
|
function createTreemapPoints(basePoints, initialPlacementPolicy) { |
|
var totalWeight = basePoints.reduce(function(acc, bp){ return acc+=bp.weight; }, 0); |
|
var avgWeight = totalWeight/siteCount; |
|
avgArea = totalArea/siteCount, |
|
defaultWeight = avgArea/2; |
|
|
|
if (initialPlacementPolicy === 'sortedPie') { |
|
var sortedBasePoints = basePoints.sort(function(bp0, bp1){ |
|
return bp0.weight < bp1.weight; |
|
}); |
|
|
|
return createTreemapPoints(sortedBasePoints, 'pie'); |
|
} |
|
else if (initialPlacementPolicy === 'pie') { |
|
var deltaRad = _2PI/siteCount; |
|
var rad; |
|
|
|
return basePoints.map(function(bp, i) { |
|
rad = deltaRad*i; |
|
|
|
return { |
|
index: bp.index, |
|
targetedArea: totalArea*bp.weight/totalWeight, |
|
data: bp, |
|
x: radius+halfRadius*Math.cos(rad)+Math.random(), |
|
y: radius+halfRadius*Math.sin(rad)+Math.random(), |
|
weight: defaultWeight |
|
} |
|
}) |
|
} else { |
|
var x,y; |
|
|
|
return basePoints.map(function(bp) { |
|
//use (x,y) instead of (r,a) for a better uniform placement of sites (ie. less centered) |
|
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(); |
|
} |
|
|
|
return { |
|
index: bp.index, |
|
targetedArea: totalArea*bp.weight/totalWeight, |
|
data: bp, |
|
x: x, |
|
y: y, |
|
weight: defaultWeight |
|
} |
|
}) |
|
} |
|
} |
|
|
|
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 |
|
resetBackgroundImage(); |
|
//end: set the initial background image |
|
} |
|
|
|
function resetBackgroundImage() { |
|
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==="cellsAndWeights") { |
|
alphaContext.globalAlpha = 0.5; |
|
polygons.forEach(function(polygon){ |
|
addCell(polygon); |
|
}); |
|
alphaContext.globalAlpha = 0.2; |
|
points.forEach(function(point){ |
|
addWeight(point); |
|
}); |
|
} else 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) { |
|
var radius = sqrt(point.weight); |
|
alphaContext.moveTo(point.x+radius, point.y); |
|
alphaContext.arc(point.x, point.y, radius, 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> |