d3-voronoi-map-tween usage

.block

license: mit
border: no

README.md

This block illustrates the use of the d3-voronoi-map-tween plugin, which allows to smoothly animate back and forth between two d3-voronoi-map.

Considering the data coming from either the starting data set or the ending data set, each single datum has a corresponding cell in the starting Voronoï map and another in the ending Voronoï map. The objective of the plugin is to provide a way (i.e. an interpolator function) to smoothly interpolate between the starting cell and the ending cell of each data. To do so, we do not interpolate polygons associated to each single datum in order to no have a mess of overlapping cells (cf. this block for this easy-but-unsatisfying attempt). But we rather interpolate the characteristics of the sites producing each cell and then compute a Voronoï map of these interpolated sites (thanks to d3-weighted-voronoi). We also have to take care of cells found only in the starting Voronoï map (data only available in the startingd ata set) or found only in the ending Voronoï map (data only in the ending data set)..

What are you seeing :

• blue cells are cells available in both the starting and ending Voronoï maps, i.e. data both in the starting and ending sets; these cells smoothly evolve in order to reflect their starting and ending weights, which may be distinct
• red cells are cells available only in the starting Voronoï map, i.e. data only in the starting data set; these cells smoothly disappear
• green cells are cells available only in the ending Voronoï map, i.e. data only in the ending data set; these cells smoothly appear
• when activated, show internals gives some visual explanations on what is going on. It displays the state of each site (see below to understand what are sites and what are they used to). The radius of each site encodes the correponding interpolated datum's value (as the cells area do). In the starting voronoï map, a disk shows the starting value of a datum; in the ending Voronoï map, it shows the ending value of the datum; in an intermediate Voronoï map, it shows the interpolated value inbetween the starting and ending values.

The algorithm is the following:

1. compute the starting Voronoï map of the starting data set; it requires some (undisplayed) iterations, and the final tessellation allows to retrieve starting sites' positions and weights; those starting sites allow to recompute the starting Voronoï map in 1 iteration using the d3-weightedVoronoï plugin
2. (quite similar to 1.) compute the ending Voronoï map of the ending data set; the final tessellation allows to retrieve ending sites' coords and weights; those ending sites allow to recompute the ending Voronoï map in 1 iteration using the d3-weightedVoronoï plugin.
3. compute the interpolated Voronoï tessellation (between the starting tessellation and the ending tessellation) for a particular interpolation amount :
4. if interpolation amount is 0, return a tessellation similar to the starting one (appearing green cells should be nullified)
5. else, if interpolation amount is 1, return a tessellation similar to the ending one (disappearing red cells should be nullified)
6. else, 331. interpolate each site's position and weight (a simple LERP function is used); be careful on disappearing cells and appearing cells 332. compute the interpolated Voronoï map, using d3-weighted-voronoi with these interpolated positions and weights

User interactions :

• use the slider to see the intermediate Voronoï maps, from the starting one (at left) to the ending one (at right).
• evolving overall size demonstrates that the plugin can handle animation between disks of distinct sizes; enabling it makes the ending overall disk smaller than the starting disk
• evolving overall shape demonstrates that the plugin can handle animation between distinct shapes; enabling it makes the ending overall shape a pentagone; the smooth interpolation between the two shapes is handled with flubber
• show internals gives some visual explanations on what is going on, by displaying the status of each site.

Acknowledgments to :

• D3.js (v.6)
• d3-weighted-voronoi plugin
• flubber
• blockbuilder.org

index.html

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>Voronoï playground: animating the addition/removing of data on a Voronoï map</title>
    <meta name="description" content="Transitioning from one Voronoï map to another with some addition and removal of data, using D3.js + d3-voronoiMap plugin + d3-weighted-voronoi plugin">
    <script src="https://d3js.org/d3.v6.min.js" charset="utf-8"></script>
    <script src="https://rawcdn.githack.com/Kcnarf/d3-weighted-voronoi/v1.1.0/build/d3-weighted-voronoi.js"></script>
    <script src="https://rawcdn.githack.com/Kcnarf/d3-voronoi-map/v2.1.0/build/d3-voronoi-map.js"></script>
    <script src="https://rawcdn.githack.com/Kcnarf/d3-voronoi-map-tween/master/build/d3-voronoi-map-tween.js"></script>
    <script src="https://unpkg.com/flubber@0.3.0"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/seedrandom/2.4.3/seedrandom.min.js"></script>
    <style>
      #wip {
        display: none;
        position: absolute;
        top: 200px;
        left: 330px;
        font-size: 40px;
        text-align: center;
      }
      
      #layouter {
        text-align: center;
        position: relative;
      }
      .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 .rangeLabel {
        width: 100px;
      }
      .control input[type="range"] {
        width: 257px;
      }

      svg {
        position: absolute;
        top: 25px;
        left: 15px;
        margin: 1px;
        border-radius: 1000px;
        box-shadow: 2px 2px 6px grey;
      }


      .seed {
        fill: steelblue;
      }
      .seed.group-enter {
        fill: lightgreen;
      }
      .seed.group-exit {
        fill: pink;
      }
      .seed.hide {
        display: none;
      }


      .cell {
        fill-opacity: 0.1;
        fill: lightsteelBlue;
        stroke: lightsteelBlue;
      }
      .cell.group-enter {
        fill: lightgreen;
        stroke: lightgreen;
      }
      .cell.group-exit {
        fill: pink;
        stroke: pink;
      }
    </style>
  </head>
  <body>
    <div id="layouter">
      <svg>
        <g id="drawing-area">
          <g id="cell-container"></g>
          <g id="site-container"></g>
          <g id="vertex-container"></g>
        </g>
      </svg>

      <div class="control top left">
        <span class="rangeLabel">Starting Voronoï map</span>
        <input id="interpolationValue" type="range" name="interpolationValue" min="0" max="1" value="0" step="0.01" oninput="interpolationValueUpdated()">
        <span class="rangeLabel">Ending Voronoï map</span>
      </div>
      <div class="control bottom left">
				<div>
          <input id="evolvingSize" type="checkbox" name="evolvingSize" onchange="evolvingSizeUpdated()"> evolving overall size
        </div>
        <div>
          <input id="evolvingShape" type="checkbox" name="evolvingShape" onchange="evolvingShapeUpdated()"> evolving overall shape
        </div>
      </div>
      <div class="control bottom right">
        <input id="siteVisibility" type="checkbox" name="siteVisibility" onchange="siteVisibilityUpdated()">
        <span>Show internals</span>
      </div>
      
      <div id="wip">
        Work in progress ...
      </div>
    </div>
  </body>

  <script>
    var WITH_TRANSITION = true;
    var WITHOUT_TRANSITION = false;
    var duration = 250;
    var PI = Math.PI;
    var halfPI = Math.PI/2;
    var twicePI = 2*Math.PI;
    var cos = Math.cos;
    var sin = Math.sin;
    var sqrt = Math.sqrt;
    var repeatableRandomness = true;
    var floor = Math.floor;
    
    var random;
    resetRandom();

    //begin: layout conf.
    var totalWidth = 550,
    		totalHeight = 500,
        controlsHeight = 30,
        svgRadius = (totalHeight-controlsHeight)/2,
        svgbw = 1, //svg border width
        svgHeight = 2*svgRadius,
    		svgWidth = 2*svgRadius,
        radius = svgRadius-svgbw,
        halfRadius = radius/2,
        width = 2*svgRadius,
        height = 2*svgRadius,
        halfRadius = radius/2
        halfWidth = halfRadius,
        halfHeight = halfRadius,
        quarterRadius = radius/4,
        quarterWidth = quarterRadius,
        quarterHeight = quarterRadius,
        evolvingSize = false,
        evolvingShape = false,
        siteOpacity = 0,
        showPolygonVerteces = false;
    //end: layout conf.
    
    //begin: data definition
    var baseDataCount = 12,
        bigDataCount = 3,
        exitingDataCount = 2,
        enteringDataCount = 2;
    var baseValue = 10,
        bigValue = 5*baseValue;
    var startingData = [],	// store data for the starting Voronoï map
        endingData = []; // store data for the ending Voronoï map
    var startingValue, endingValue;
    
    //create the starting data set and the ending data set
    for (i=0; i<baseDataCount; i++) {
      if (i < bigDataCount) {
	      startingValue = bigValue;
	      endingValue = bigValue;
      } else {
        startingValue = (0.5+random())*baseValue;
      	endingValue = (0.5+random())*baseValue;
      }
      startingData.push({
        index: i,
        value: startingValue
      });
      endingData.push({
        index: i,
        value: endingValue
      })
    }
    //add new data to the ending data set
    for (i=baseDataCount; i<baseDataCount+enteringDataCount; i++) {
      endingValue = (0.5+random())*baseValue;
      endingData.push({
        index: i,
        value: endingValue
      })
    }
    //delete data from the ending data set
    endingData = endingData.slice(exitingDataCount);
    //end: data definition

    //begin: utilities
    var key = (d)=>d.index; //mapping between starting and ending data
    var cellLiner = d3.line()
      .x(function(d){ return d[0]; })
      .y(function(d){ return d[1]; });
    var siteRadiusScale = d3.scaleSqrt()
    	.domain([0, bigValue])
    	.range([0,10]);
    function resetRandom() {
      random = repeatableRandomness ? new Math.seedrandom('seed2') : Math.random;
    }
    //end: utilities

    //begin: reusable d3-selections
    var layouter = d3.select("#layouter"),
        svg = d3.select("svg"),
        drawingArea = d3.select("#drawing-area"),
        cellContainer = d3.select("#cell-container"),
        vertexContainer = d3.select("#vertex-container"),
        siteContainer = d3.select("#site-container");
    //end: reusable d3-selections
    initLayout();

    //begin: user interaction handlers
    function interpolationValueUpdated() {
      var interpolationValue = +d3.select("#interpolationValue").node().value;

      var interpolationEasing = d3.easeLinear;
      // just for fun, choose the easing effect by uncommenting the adequate loc
      // interpolationEasing = d3.easeSinInOut;
      // interpolationEasing = d3.easeElasticInOut;
      //interpolationEasing = d3.easeBounceInOut;
      interpolationValue = interpolationEasing(interpolationValue);
      interpolatedCells = voronoiMapInterpolator(interpolationValue);
      interpolatedSites = interpolatedCells.map(function(c) {return c.site.originalObject; });
      redrawCells(WITHOUT_TRANSITION);
      redrawSites(WITHOUT_TRANSITION);
    }
    
    function evolvingSizeUpdated() {
      evolvingSize = d3.select("#evolvingSize").node().checked? 1:0;
     	voronoiMapInterpolator = buildVoronoiMapInterpolator();
      interpolationValueUpdated();
    }
    
    function evolvingShapeUpdated() {
      evolvingShape = d3.select("#evolvingShape").node().checked? 1:0;
      voronoiMapInterpolator = buildVoronoiMapInterpolator();
      interpolationValueUpdated();
    }
    
    function siteVisibilityUpdated() {
      siteOpacity = d3.select("#siteVisibility").node().checked? 1:0;
      redrawSites();
    }
    //end: user interaction handlers

    //begin: voronoi stuff definitions
    var clippingPolygon; 
    var voronoiMapInterpolator = buildVoronoiMapInterpolator();
    
    var interpolatedSites = []; // store interpolated sites
    var interpolatedCells = []; // store cells
    //end: voronoi stuff definitions
    
    interpolatedCells = voronoiMapInterpolator(0);
    interpolatedSites = interpolatedCells.map(function(c) {return c.site.originalObject; });
    redrawCells(WITHOUT_TRANSITION);
    redrawSites(WITHOUT_TRANSITION);

    /***************/
    /* Computation */
    /***************/
    
    function buildVoronoiMapInterpolator() {
      clippingPolygon = computeClippingPolygon(0);
      var startingSimulation = computeVoronoiPolygons(startingData, null);
      var startingPolygons = startingSimulation.state().polygons;
      var endingSimulation = computeVoronoiPolygons(endingData, startingPolygons)
      var endingPolygons = endingSimulation.state().polygons;

      var voronoiMapTween = d3.voronoiMapTween(startingSimulation, endingSimulation)
          .startingKey(key)
          .endingKey(key)
          .clipInterpolator(buildClipInterpolator());
      return voronoiMapTween.mapInterpolator();
    }

    // clipping polygon interpolator using Flubber
    // see it in action by modifying the computeClippingPolygon, so that the starting and ending polygons are distinct
    function buildClipInterpolator() {
      if (!evolvingShape) {
        if (!evolvingSize) {
          var staticClippingPolygon = computeClippingPolygon(0);
          return function (iv) { return staticClippingPolygon; }
        } else {
          return computeClippingPolygon; // with a static shape, this function is capable of making intermediate clipping polygons/disk
        }
      } else {
        // when the shape evolves, we use Flubber to have a smooth clip interpolator
        var flubberInterpolator = flubber.interpolate(computeClippingPolygon(0), computeClippingPolygon(1), {string: false, maxSegmentLength: 100}); // 100 for not having too many points added by flubber
        function distance(v0,v1) {
          return Math.pow(Math.pow(v1[0]-v0[0],2) + Math.pow(v1[1]-v0[1],2),0.5);
        }
        var derivedFlubberInterpolator = function(iv) {
          var flubberizedClip = flubberInterpolator(iv);
          var simplifiedFlubberizedClip = []
          for(vertexI=0; vertexI<flubberizedClip.length; vertexI++) {
            if (distance(flubberizedClip[vertexI], flubberizedClip[(vertexI+1)%flubberizedClip.length]) > 1) {
              // remove duplicate and close verteces
              simplifiedFlubberizedClip.push(flubberizedClip[vertexI]);
            }
          }

          return simplifiedFlubberizedClip;
        }
        return derivedFlubberInterpolator;
    	}
    }
    
    //uses d3-voronoi-map to compute a Voronoï map where each cell's area encodes a particular datum's value.
    //Param 'previousPolygons' allows to reuse coords and weights of a previously computed Voronoï tessellation, in order for updated data to produce cells in the same region.
    function computeVoronoiPolygons(data, previousPolygons) {
      var simulation, k;
      
      resetRandom();
      
      if (previousPolygons) {
        var previousSites = previousPolygons.map(d=>d.site),
        		previousSiteByKey = {},
            previousTotalWeight = 0;
        previousSites.forEach((s)=>{
          k = key(s.originalObject.data.originalData);
          previousSiteByKey[k]=s;
          previousTotalWeight += s.weight;
        });
        var previousAverageWeight = previousTotalWeight/previousSites.length;
        
        var intialPositioner = function(d) {
          var previousSite = previousSiteByKey[key(d)];
          var newSitePosition;
          if (previousSite) {
            newSitePosition = [previousSite.x/2, previousSite.y/2];
          } else {
            //return nearClippingCirclePerimeter();
            newSitePosition = nearAnyPreviousPartitioningVertex(previousPolygons);
            
          }
          return [newSitePosition[0]/2, newSitePosition[1]/2];
          // dividing by 2 ensure to position site inside ending polygon
          // even when size is smaller, or/and shape is smaller
        }
      	var intialWeighter = function(d) {
          var previousSite = previousSiteByKey[key(d)];
          var newSiteWeight;
          if (previousSite) {
            newSiteWeight = previousSite.weight/4;
          } else {
            newSiteWeight = previousAverageWeight/4;
          }
          return newSiteWeight/4;
          // as new site position is divided by 2 along x and y axes
          // we divide the weight by pow(2,2) to preserve cell aspects
        }
        simulation = d3.voronoiMapSimulation(data)
        	.clip(computeClippingPolygon(1))
      		.weight((d)=>d.value)
        	.initialPosition(intialPositioner)
        	.initialWeight(intialWeighter)
        	.prng(random)
        	.stop();
      } else {
        simulation = d3.voronoiMapSimulation(data)
          .clip(computeClippingPolygon(0))
      		.weight((d)=>d.value)
        	.prng(random)
          .stop();
      }
      
      var state = simulation.state();	// retrieve the simulation's state, i.e. {ended, polygons, iterationCount, convergenceRatio}

      //begin: manually launch each iteration until the simulation ends
      while (!state.ended) {
        simulation.tick();
        state = simulation.state();
      }
      //end:manually launch each iteration until the simulation ends
      
      return simulation;
    }
    
    // return a position corresponding to a vertex separating 2 cells (not a vertex of a border cell due to the clipping polygon)
    function nearAnyPreviousPartitioningVertex(previousPolygons) {
			var vertexNearClippingPolygon = true;
      var i, previouscell, previousVertex;
      
      // begin: redo until choosen vertex is not one of the clipping polygon
      while (vertexNearClippingPolygon) {
        // pick a random previous cell
        i = floor(previousPolygons.length*random());
        previouscell = previousPolygons[i];
        // pick a random vertex
        i = floor(previouscell.length*random());
        previousVertex = previouscell[i];
        vertexNearClippingPolygon = nearAClippingPolygonVertex(previousVertex);
      }
      // end: redo until choosen vertex is not one of the clipping polygon
      
      // add some randomness if the choosen vertex is picked several times due to several addition of data, checking that the coords are still in the clipping polygon
      var coordsInClippingPolygon = false;
      var xRandomness, yRandomness, coords;
      while (!coordsInClippingPolygon) {
        xRandomness = random()-0.5; // -0.5 for a central distribution
        yRandomness = random()-0.5;
      	coords = [previousVertex[0]+xRandomness, previousVertex[1]+yRandomness];
        coordsInClippingPolygon = d3.polygonContains(clippingPolygon, coords);
      }
      
      // begin: debug: display position of added sites (i.e. added data)
      // siteContainer.append('circle').attr('r', 3).attr('cx', coords[0]).attr('cy', coords[1]).attr('fill', 'red');
      // end: debug
      
      return coords;
    }
    
    function nearAClippingPolygonVertex (v) {
      var near = 1;
      var dx, dy, d;
      var isVertexOfClippingPolygon = false;
      clippingPolygon.forEach(cv=>{
        if (!isVertexOfClippingPolygon) {
          dx = v[0] - cv[0];
          dy = v[1] - cv[1];
          d = sqrt(dx**2+dy**2);
          isVertexOfClippingPolygon = d<near;
        }
      })
      return isVertexOfClippingPolygon;
    }
    
    function computeClippingPolygon(interpolationValue) {
      var iv = interpolationValue // smaller name
      var interpolatedRadius = radius;
      var clipVertexNumber = 60;
      
      if (evolvingSize) {
        interpolatedRadius = radius - iv*20;
        // raidus is 20 pixel smaller at end
      }
      if (evolvingShape) {
        clipVertexNumber = 60 - Math.floor(55*iv);
        // circle-like 60-gone at start
        // pentagone at end
      }
      var angleIncrement = twicePI/clipVertexNumber;
      var i=0,
          angle=-halfPI, // horizontal bottom for odd-gones
          circlingPolygon = [];
      for (i=0; i<clipVertexNumber; i++) {
        angle += angleIncrement;
        circlingPolygon.push([
          (interpolatedRadius)*cos(angle),
          (interpolatedRadius)*sin(angle)
        ])
      }

      return circlingPolygon;
    };

    /***********/
    /* Drawing */
    /***********/
    
    function initLayout () {
      layouter.style("width", totalWidth+"px")
        .style("height", totalHeight+"px");
      
      svg.attr("width", svgWidth)
        .attr("height", svgHeight)
      	.attr("transform", "translate("+(totalWidth/2-radius)+",0)");

      drawingArea.attr("width", width)
        .attr("height", height)
        .attr("transform", "translate("+[radius+svgbw, radius+svgbw]+")");
    }
    
    function redrawSites() {
      var siteSelection = siteContainer.selectAll(".seed")
      	.data(interpolatedSites, function(s){ return s.key; });
      
      siteSelection
      	.enter()
        	.append("circle")
            .attr("class", function(d){ return "group-"+d.tweenType; })
            .classed("seed", true)
      	.merge(siteSelection)
            .attr("r", (d)=> siteRadiusScale(d.interpolatedDataWeight))
            .attr("opacity", siteOpacity)
            .attr("transform", (d)=>{ return "translate("+[d.interpolatedSiteX,d.interpolatedSiteY]+")"; });
      
      siteSelection.exit().remove();
    }

    function redrawCells(withTransition) {
      var cellSelection = cellContainer.selectAll(".cell")
        .data(interpolatedCells, function(c){ return c.site.originalObject.key; });
       
      cellSelection.enter()
        .append("path")
          .attr("class", function(d){ return "group-"+d.site.originalObject.tweenType; })
          .classed("cell", true)
          .attr("id", function(d,i){ return "cell-"+d.site.originalObject.key; })
      	.merge(cellSelection)
      		.transition()
            .duration(withTransition? duration : 0)
            .attr("d", function(d){ return cellLiner(d)+"z"; });
      
      cellSelection.exit().remove();
      
      if (showPolygonVerteces) {
        var verteces = interpolatedCells.reduce( function(acc, p) { return acc.concat(p); }, []);
        var vertexSelection = vertexContainer.selectAll(".vertex")
          .data(verteces);
        vertexSelection.enter()
          .append("circle")
            .classed("vertex", true)
            .attr("r", 2)
          .merge(vertexSelection)
            .attr("cx", function(v) { return v[0]; })
            .attr("cy", function(v) { return v[1]; });
        vertexSelection.exit().remove();
      }
    }
  </script>
</html>

thumbnail.png