Voronoï playground: Voronoï map (study)

This block is a Work In Progress, which tries to implements a Voronoï map (i.e., one-level treemap) based on the algorithm presented in Computing Voronoi Treemaps - Faster, Simpler, and Resolution-independent. Because this algorithm requires the computation of weighted Voronoï, this block uses the d3-weighted-voronoi plugin.

Without going into details (cf. the scientific paper), at each iteration :

the weighted voronoi diagram is computed based on each weighted sites
then, each site is re-position at the center of its influence area
then, another weighted voronoi diagram is computed based on each weighted relocated sites
then, each site is re-weighted in order to fit its expected influence area

The algorithm stops when each site is no longer moved or re-weighted (more exactly, when each site is moved or is re-weighted below a certain treshold), or if a certain number of iterations is reached.

Notes :

only one level, no nested hierarchy
as stated in the scientifc paper, the algorithm reaches a stable state at approximatively 15%-20% of error (sum of differences between computed areas and expected areas is about 15%-20% of the total available area)
experiments show that near-zero weights are difficult to handle, causing flickering

User interactions :

you can choose to draw the Weighted Voronoï Diagram (default) or the weights (visualized as circles).
you can hide/show sites
you can choose among different rendering (greyscale, radial rainbow, or conical rainbow (default, having hard-&-fun time to implement it because canvas don't provides conical gradient)).

Acknowledgments to :

D3.js (v.4)
d3-weighted-voronoi plugin
blockbuilder.org
(part of) https://github.com/ArlindNocaj/Voronoi-Treemap-Library for a Java implementation

forked from Kcnarf's block: Voronoï playground: Voronoï map (study)

<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;
      };
      
      // https://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 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);
        }
      }

Updated missing url https://raw.githack.com/Kcnarf/d3-weighted-voronoi/master/build/d3-weighted-voronoi.js to https://raw.githack.com/kcnarf/d3-weighted-voronoi/master/build/d3-weighted-voronoi.js

https://d3js.org/d3.v4.min.js

https://raw.githack.com/Kcnarf/d3-weighted-voronoi/master/build/d3-weighted-voronoi.js