Kcnarf · December 19, 2017 14:06
diff --git a/.block b/.block
 license: gpl-3.0
 border: no
diff --git a/README.md b/README.md
diff --git a/index.html b/index.html
 <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>
diff --git a/thumbnail.png b/thumbnail.png
	<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(dypoint[0] - dxpoint[1] + p2[0]p1[1] - p1[0]p2[1]) / Math.sqrt(dxdx + dydy);

	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(areaError1001000/totalArea)/1000);
	return areaError < areaErrorTreshold;
	};

	function reset() {
	var basePoints = [];
	var weight, treemapPoints, polygons;

	//begin: create points
	for (i=0; i<siteCount; i++) {
	weight = (0+1sqr(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, 2radius, 2radius);

	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>