Voronoï playground: Voronoï treemap (study)

This block experiments how to produce a hierarchical Voronoï treemap based on hierarchical/nested data (cf. d3.hierarchy). It uses the d3-voronoi-map plugin which compute one-level Voronoï maps.

Notes :

the algorithm, initiated with the root node and the clipping polygon, is as follow:
if node as children, compute the one-level Voronoï map of the clipping polygon and the children's data, thanks to the d3-voronoi-map
repeat for each child with children and child-related computed polygon
this is a layered algorithm: the Voronoï map of a particular node must be computed/stabilized before computing nested Voronoï maps of nested data; this approach ensures that clipping polygons remain the same when computing nested Voronoï maps; otherwise, the algorithm should handle sites that may become out of clipping polygons

User interactions :

you can choose to draw the Weighted Voronoï Diagram (default), the weights (visualized as circles), or both.
you can hide/show sites.

Acknowledgments to :

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

<html lang="en">
  <head>
    <meta charset="utf-8" />
    <title>Voronoï playground: Voronoï treemap (study 3)</title>
    <meta name="description" content="Hierarchical Voronoi treemap in D3.js (study 3)">
    <script src="https://d3js.org/d3.v4.min.js"></script>
    <script src="https://d3js.org/d3-scale-chromatic.v1.min.js"></script>
    <script src="https://raw.githack.com/kcnarf/d3-weighted-voronoi/v1.0.0/build/d3-weighted-voronoi.js"></script>
    <script src="https://raw.githack.com/kcnarf/d3-voronoi-map/v1.2.0/build/d3-voronoi-map.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;
      }

svg {
        margin: 1px;
        border-radius: 1000px;
        box-shadow: 2px 2px 6px grey;
      }
      
      .cell {
        fill: none;
        fill-opacity: 0.5;
        stroke: darkgrey;
      }
      
      .weight {
        fill: none;
        stroke: lightgrey;
        stroke-width: 1px;
      }
      
      .site {
        fill: none;
        stroke: lightgrey;
        stroke-width: 2px;
      }
    </style>
  </head>
  <body>
    <div id="layouter">
      <svg id="svg"></svg>

<div id="control0" class="control top left">
        <div>
          <input id="cellsOrWeights" type="radio" name="cellsOrWeights" value="cells" checked onchange="cellsOrWeightsUpdated('cells')"> Weighted Voronoï 
        </div>
        <div>
          <input id="cellsOrWeights" type="radio" name="cellsOrWeights" value="circles" onchange="cellsOrWeightsUpdated('weights')"> Weights
        </div>
        <div>
          <input id="cellsOrWeights" type="radio" name="cellsOrWeights" value="circles" onchange="cellsOrWeightsUpdated('cellsAndWeights')"> Both
        </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="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); };
      
      //begin: layout conf.
      var totalWidth = 550,
          totalHeight = 500,
          controlsHeight = 0,
          svgbw = 1, // canvas border width
          svgbs = 8, // canvas box-shadow
          radius = (totalHeight-controlsHeight-svgbs-2*svgbw)/2,
          width = 2*radius,
          height = 2*radius,
          halfRadius = radius/2
          halfWidth = halfRadius,
          halfHeight = halfRadius,
          quarterRadius = radius/4;
          quarterWidth = quarterRadius,
          quarterHeight = quarterRadius;
      //end: layout conf.
      
      //begin: drawing conf.
      var drawSites = false,
      		drawCellsOrWeights = "cells",
          colorScale = d3.scaleOrdinal(d3.schemeSet1);;
      //end: drawing conf.
      
      //begin: reusable d3Selection
      var cellContainer, weightContainer, siteContainer;
      //end: reusable d3Selection
      initLayout()
      
      //begin: voronoi treemap conf.
      var clippingPolygon = computeClippingPolygon(),
          maxHierarchyLevel = 3,	//0 is root node
          minSiteCountPerLevel = 3,
          maxSiteCountPerLevel = 10,
          deltaSiteCountPerLevel = maxSiteCountPerLevel - minSiteCountPerLevel,
          hierarchyRatio = 0.3,
          baseWeight = 2000,
          outlierRatio = 0.1,
          outlierWeight = 3*baseWeight;
      var	_voronoiMap = d3.voronoiMap()
      											.weight(function(d){ return d.value; })
      											.minWeightRatio(0.01)
      											.maxIterationCount(50)
      											.convergenceRatio(0.01);
      var root;	// hierarchy, perodically reseted
      //end: voronoi treemap conf.
			
      function computeClippingPolygon() {
        var circlingPolygon = [];
        for (a=0; a<_2PI; a+=_2PI/60) {
          circlingPolygon.push(
            [radius + (radius-1)*Math.cos(a), radius + (radius-1)*Math.sin(a)]
          )
        }
        
      	return circlingPolygon;
      };
      
      
      //begin: user interaction handlers
      function siteVisibilityUpdated() {
        drawSites = d3.select("#showSites").node().checked;
        redraw(root);
      };
      
      function cellsOrWeightsUpdated(type) {
        drawCellsOrWeights = type;
        redraw(root);
      };
      //end: user interaction handlers
      
      renew();
      
      function renew() {
        root = createD3Hierarchy().sum(function(d){ return d.weight; })
        voronoiTreemap(root, clippingPolygon);
        redraw(root);
        setTimeout(function(){
          renew();
        }, 4000);
      };
      
      function voronoiTreemap(node, clippingPolygon) {
        var res;
        
        //assign polygon to node
        node.polygon = clippingPolygon;
        
        if (node.height!=0) {
          //compute one-level Voronoi map of children
          res = _voronoiMap.clip(clippingPolygon)(node.children);
          //begin: recurse on children
          res.polygons.forEach(function(cp){
            voronoiTreemap(cp.site.originalObject.data.originalData, cp);
          })
          //end: recurse on children
        }
      }
      
      function createD3Hierarchy() {
        var hierarchyData = createHierarchyData(0, undefined),
            hierarchy = d3.hierarchy(hierarchyData);
        return hierarchy;
      }
      
      function createHierarchyData(level, color) {
        var childCount, children, child, node;
        
        if (level===0 ||
            (level<maxHierarchyLevel && Math.random()<hierarchyRatio)
           ) {
          childCount = minSiteCountPerLevel+deltaSiteCountPerLevel*Math.random();
          childCount = Math.round(childCount);
          children = [];
          //begin: create sub-hierarchy
          for (var i=0; i<childCount; i++) {
            if (level===0) {
              color = colorScale(i);
            }
						children.push(createHierarchyData(level+1, color));
          }
          //end: create sub-hierarchy
          node = {color: color, children: children};
        } else {
          node = createLeafData(color);
        }
        return node;
      };
      
      function createLeafData(color) {
        var weight;
        if (Math.random() < outlierRatio ) {
          weight = outlierWeight;
        } else {
          weight = (0+1*sqr(Math.random()))*baseWeight;
        }
        return {weight: weight, color: color};
      }
      
      function initLayout() {
        var svg;
        
        d3.select("#layouter").style("width", totalWidth+"px").style("height", totalHeight+"px");
        svg = d3.select("svg").attr("width", width).attr("height", height);
        cellContainer = svg.append("g").attr("id", "cell-container");
        weightContainer = svg.append("g").attr("id", "weight-container");
        siteContainer = svg.append("g").attr("id", "site-container");
      }

//redraw all polygons/data, except root which has no site
      function redraw(root) {
        var nodes = root.descendants();
        nodes.shift(); // remove root
        
        cellContainer.selectAll(".cell").remove();
        weightContainer.selectAll(".weight").remove();
        siteContainer.selectAll(".site").remove();
        
        //begin: add the new tessellation/weights
        if (drawCellsOrWeights==="cells" || drawCellsOrWeights==="cellsAndWeights") {
          redrawCells(nodes);
        }
        if (drawCellsOrWeights==="weights" || drawCellsOrWeights==="cellsAndWeights") {
          redrawWeights(nodes);
        }
				//begin: add the new tessellation/weights
        
        if (drawSites) {
          //begin: add sites
          redrawSites(nodes);
          //begin: add sites
        }
      }
      
      function redrawCells(nodes) {
        var cells = cellContainer.selectAll(".cell")
        	.data(nodes)
        	.enter()
        		.append("path")
        			.classed("cell", true)
        			.attr("d", function(d){ return "M"+d.polygon.join(",")+"z"; })
        			.style("stroke-width", function(d){
                return 1.5*(maxHierarchyLevel - d.depth)+2;
              })
        			.style("fill", function(d){
                return d.data.color;
              });
      }
      
      function redrawWeights(nodes) {
        weightContainer.selectAll(".weight")
        	.data(nodes)
        	.enter()
        		.append("circle")
        			.classed("weight", true)
        			.attr("cx", function(d){ return d.polygon.site.x; })
        			.attr("cy", function(d){ return d.polygon.site.y; })
        			.attr("r", function(d){ return sqrt(d.polygon.site.weight); });
      }
      
      function redrawSites(nodes) {
        siteContainer.selectAll(".site")
        	.data(nodes)
        	.enter()
        		.append("circle")
        			.classed("site", true)
        			.attr("cx", function(d){ return d.polygon.site.x; })
        			.attr("cy", function(d){ return d.polygon.site.y; })
        			.attr("r", function(d){
          			return 4*(maxHierarchyLevel - d.depth)+1;
        			});
      }
    </script>
  </body>
</html>

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

Updated missing url https://raw.githack.com/Kcnarf/d3-voronoi-map/v1.2.0/build/d3-voronoi-map.js to https://raw.githack.com/kcnarf/d3-voronoi-map/v1.2.0/build/d3-voronoi-map.js

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

https://d3js.org/d3-scale-chromatic.v1.min.js

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

https://raw.githack.com/Kcnarf/d3-voronoi-map/v1.2.0/build/d3-voronoi-map.js