Kcnarf/.block

## .block
license: gpl-3.0
border: no

## README.md

      
    Raw
  

              README.md
            
          
    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


## index.html
<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>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<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+1sqr(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>