Voronoï playground: animating addition/removing of data

This block experiments how to animate the addition/removal of data in a Voronoï map.

This experimentation leads to the d3-voronoi-map-tween plugin. A more recent bl.ocks uses this plugin.

In the starting Voronoï map, red cells correspond to removed/exiting data (i.e. cells not appearing in the ending Voronoï map). In the ending Voronoï map, green cells correspond to added/entering data (i.e. cells not existing in the starting Voronoï map). Blue cells correspond to updated data, i.e. cells existing in both the starting and ending Voronoï maps. Areas of blue cells evolve because the corresponding data values evolve.

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 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 interpolation value between the starting and ending values.

The algorithm is the following:

compute the starting Voronoï map of the starting data set; it requires some (undisplayed) iterations, and the final tessellation allows to retrieve starting sites' coords and weights; those starting sites allow to recompute the starting Voronoï map in 1 iteration using the d3-weightedVoronoï plugin
(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.
compute the interpolated Voronoï tessellation (between the starting tessellation and the ending tessellation) for a particular interpolation amount :
if interpolation amount is 0, return starting tessellation (appearing green cells should be nullified)
else, if interpolation amount is 1, return ending tessellation (disappearing red cells should be nullified)
else,
interpolate each site's coords and weight (a simple LERP function is used); be careful on disappearing cells and appearing cells
compute the interpolated Voronoï map, using d3-weighted-voronoi with these interpolated coords 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).
show internals gives some visual explanations on what is going on, by displaying the status of each site.

Acknowledgments to :

<!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.0.1/build/d3-weighted-voronoi.js"></script>
    <script src="https://rawcdn.githack.com/kcnarf/d3-voronoi-map/v2.0.1/build/d3-voronoi-map.js"></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;
      }

.control {
        position: absolute;
      }
      .control#control-0 {
        left: 5px;
        top: 5px;
        text-align: center;
      }
      .control#control-1 {
        left: 5px;
        bottom: 5px;
      }
      .control span {
        width: 100px;
      }
      .control input[type="range"] {
        width: 210px;
      }

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="wip">
      Work in progress ...
    </div>
  </body>

//begin: layout conf.
    var totalHeight = 500,
        controlsHeight = 30,
        svgRadius = (totalHeight-controlsHeight)/2,
        svgbw = 1, //svg border width
        svgHeight = 2*svgRadius,
    		svgWidth = 2*svgRadius,
        radius = svgRadius-svgbw,
        width = 2*svgRadius,
        height = 2*svgRadius,
        halfRadius = radius/2
        halfWidth = halfRadius,
        halfHeight = halfRadius,
        quarterRadius = radius/4;
        quarterWidth = quarterRadius,
        quarterHeight = quarterRadius
        siteOpacity = 0;
    //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 X_ACCESSOR = (d) => d.interpolatedX; // x accessor of interpolated data
  	var Y_ACCESSOR = (d) => d.interpolatedY; // y accessor of interpolated data
  	var WEIGHT_ACCESSOR = (d) => d.interpolatedWeight; // weight accessor of interpolated 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]);
    //end: utilities

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

//begin: user interaction handlers
    function interpolationValueUpdated() {
      var interpolationValue = +d3.select("#control-0 input").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 siteVisibilityUpdated() {
      siteOpacity = d3.select("#control-1 input").node().checked? 1:0;
      redrawSites();
    }
    //end: user interaction handlers

//begin: voronoi stuff definitions
    var clippingPolygon = computeClippingPolygon();
    var startingSimulation = computeVoronoiPolygons(startingData, null);
    var startingPolygons = startingSimulation.state().polygons;
    var endingSimulation = computeVoronoiPolygons(endingData, startingPolygons)
    var endingPolygons = endingSimulation.state().polygons;
    
    var voronoiMapInterpolator = buildVoronoiMapInterpolator();
    
    var weightedVoronoi = d3.weightedVoronoi()
    			.x(X_ACCESSOR)
    			.y(Y_ACCESSOR)
    			.weight(WEIGHT_ACCESSOR)
    			.clip(clippingPolygon);
    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 */
    /***************/

// returns a function that is the interpolator, taking starting and ending tessellations as inputs
    function buildVoronoiMapInterpolator() {
      var startingSites = startingPolygons.map((p)=>p.site),
          endingSites = endingPolygons.map((p)=>p.site);
      var startingSiteByKey = {},
          endingSiteByKey = {},
          allSiteKeys = new Set();
      var k;
      
      startingSites.forEach((s)=>{
        k = key(s.originalObject.data.originalData);
        startingSiteByKey[k]=s;
        allSiteKeys.add(k)
      });
      endingSites.forEach((s)=>{
        k = key(s.originalObject.data.originalData);
        endingSiteByKey[k]=s;
        allSiteKeys.add(k);
      });
      
      var siteTweeningData = [];
      var startingSite, startingData, startingX, startingY, startingWeight, startingValue,
      endingSite, endingData, endingX, endingY, endingWeight, endingValue,
      tweenType;
      
      
      //find correspondance between starting and ending cells/sites/data; handle entering and exiting cells
      allSiteKeys.forEach((k)=>{
        startingSite = startingSiteByKey[k];
        endingSite = endingSiteByKey[k];
        if (startingSite && endingSite) {
          // a startingSite and an endingSite corresponding to the same datum
          startingData = startingSite.originalObject.data.originalData;
          endingData = endingSite.originalObject.data.originalData;
          startingX = startingSite.x;
          endingX = endingSite.x;
          startingY = startingSite.y;
          endingY = endingSite.y;
          startingWeight = startingSite.weight;
          endingWeight = endingSite.weight;
          startingValue = startingData.value;
          endingValue = endingData.value;
          tweenType = 'update';
        } else if (endingSite) {
          // no startingSite, i.e. datum not in starting sites
          // no coords interpolation (site fixed to ending position), weight interpolated FROM underweighted weight, and value interpolated FROM 0
          startingData = null;
          endingData = endingSite.originalObject.data.originalData;
          startingX = endingSite.x;
          endingX = endingSite.x;
          startingY = endingSite.y;
          endingY = endingSite.y;
          startingWeight = computeUnderweight(endingSite, startingPolygons);
          endingWeight = endingSite.weight;
          startingValue = 0;
          endingValue = endingData.value;
          tweenType = 'enter';
        } else {
          //no endingSite, i.e. datum not in ending sites
          //no coords interpolation (site fixed to starting position), weight interpolated TO underweighted weight, and data interpolated TO 0
          startingData = startingSite.originalObject.data.originalData;
          endingData = null;
          startingX = startingSite.x;
          endingX = startingSite.x;
          startingY = startingSite.y;
          endingY = startingSite.y;
          startingWeight = startingSite.weight;
          endingWeight = computeUnderweight(startingSite, endingPolygons);
          startingValue = startingData.value;
          endingValue = 0;
          tweenType = 'exit';
        }
        
        siteTweeningData.push({
          startingData: startingData,
          endingData: endingData,
          key: k,
          startingX: startingX,
          endingX: endingX,
          startingY: startingY,
          endingY: endingY,
          startingWeight: startingWeight,
          endingWeight: endingWeight,
          startingValue: startingValue,
          endingValue: endingValue,
          tweenType: tweenType,
        })
      });
      
      // Produces a Voronoï tessellation inbetween a starting tessellation and an ending tessellation.
      // Currently uses a LERP interpollation. Param 'interpolationValue' gives the interpolation amount: 0->starting tessellation, 1->ending tessellation
      return function voronoiTesselationInterpolator(interpolationValue) {
        var iv = interpolationValue; // just a smaller identifer
        
        // [STEP 1] interpolate each coords and weights
        interpolatedSites = siteTweeningData.map((std)=>{
          return {
            key: std.key,
            interpolatedX: lerp(std.startingX, std.endingX, iv),
            interpolatedY: lerp(std.startingY, std.endingY, iv),
            interpolatedWeight: lerp(std.startingWeight, std.endingWeight, iv),
            interpolatedValue: lerp(std.startingValue, std.endingValue, iv),
            tweenType: std.tweenType
          };
        });
				
        // [STEP 2] use d3-weighted-voronoi to compute the interpolated tessellation
        return weightedVoronoi(interpolatedSites);
      }
    }
    
    // linear interpolation between a starting value and an ending value
    function lerp(startingValue, endingValue, interpolationValue) {
      var iv = interpolationValue, // just a smaller identifer
          sv = startingValue,
          ev = endingValue;
      
      return (1-iv)*sv + iv*ev;
    }
    
    // when interpolating, all sites/data (entering, updated, exiting) are mapped to an interpolated site in order to produce an interpolated Voronoï tesselation; when interpolation value is 0, we want the interpolated tessellation looks like the starting tessellation (even with the added entering sites/data), and don't want the entering sites/data to produce a cell; in the same way, when interpolation value is 1, we want the interpolated tessellation looks like the ending tessellation (even with the exiting sites/data), and don't want the exiting sites/data to produce a cell
    // using a default value such (as 0) doesn't insure this desired behavior (a site with weight 0 can produce a cell)
    // using a very low default value (as -1000) will do the trick for first/starting and last/ending tessellation, BUT the interpolated weights during animation of tessellations may be weird because entering and exiting sites/data appear/disappear too quickly
    // so the below function
    
    // returns an underweighted weight so that the entering (or exiting) site/data is completly overweighted by the starting sites (or ending sites)
    // algo:
    //	[STEP 1] find the starting cell where the entering/exiting site/data comes in/out
    //	[STEP 2] compute the underweighted weight (depending on farest vertex from polygon's site and polygon's site's weight)
    function computeUnderweight(site, polygons) {
      var polygon = null;
      
      // [STEP 1] find the starting cell where the entering site/data comes in
      polygons.forEach(p => {
        if (!polygon) {
          if (d3.polygonContains(p, [site.x, site.y])) {
            polygon = p;
          }
        }
      })
      
      // [STEP 2] compute the overweighted weight (depending on farest vertex from polygon's site and polygon's site's weight)
      var pSite = polygon.site,
          squaredFarestDistance = -Infinity;
      var squaredD;
      polygon.forEach(v=> {
        squaredD = (pSite.x-v[0])**2 + (pSite.y-v[1])**2;
        if (squaredD > squaredFarestDistance) {
          squaredFarestDistance = squaredD;
        }
      })
      
      var underweight = - squaredFarestDistance + pSite.weight ;
      return underweight;
    }
    
    //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;
      
      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)];
          if (previousSite) {
            return [previousSite.x, previousSite.y];
          } else {
            //return nearClippingCirclePerimeter();
            return nearAnyPreviousPartitioningVertex(previousPolygons);
          }
        }
      	var intialWeighter = function(d) {
          var previousSite = previousSiteByKey[key(d)];
          if (previousSite) {
            return previousSite.weight;
          } else {
            return previousAverageWeight;
          }
        }
        
        simulation = d3.voronoiMapSimulation(data)
        	.clip(clippingPolygon)
      		.weight((d)=>d.value)
        	.initialPosition(intialPositioner)
        	.initialWeight(intialWeighter)
        	.stop();
      } else {
        simulation = d3.voronoiMapSimulation(data)
          .clip(clippingPolygon)
      		.weight((d)=>d.value)
          .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 near circle's perimeter, at random angle
    // /!\ DON'T USE IT, not that good policy, because the returned coords can be inside a big cell (i.e. inside a cell corresponding to a big value to encode), so that the resulting site may be overweighted, which lead to not producing any cell (error 'Cannot read property 'site' of undefined' in 'adpatPositions' function of d3-vornoi-map)
    // prefer next policy
    function nearClippingCirclePerimeter() {
      var angle = _2PI*random(),
          d = (radius-10); // -10 ensure the new point is inside the clipping circle
      var x = radius + d*cos(angle), 
          y = radius + d*sin(angle);
      var xRandomness = (random()-0.5), // -0.5 for a central distribution
          yRandomness = (random()-0.5);
      var coords = [x + xRandomness, y + yRandomness]; // raise an error without randomness, don't understand why ...
      
      // begin: debug: display position of added sites (i.e. added data)
      // siteContainer.append('circle').attr('r', 3).attr('cx', coords[1]).attr('cy', coords[1]).attr('fill', 'red');
      // end: debug
      
      return coords;
    }
    
    // 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() {
      var circlingPolygon = [];
      for (a=0; a<_2PI; a+=_2PI/60) {
        circlingPolygon.push(
          [radius + (radius)*cos(a), radius + (radius)*sin(a)]
        )
      }

return circlingPolygon;
    };

/***********/
    /* Drawing */
    /***********/
    
    function initLayout () {
      svg.attr("width", svgWidth)
        .attr("height", svgHeight);

drawingArea.attr("width", width)
        .attr("height", height)
        .attr("transform", "translate("+[svgbw, 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.interpolatedValue))
            .attr("opacity", siteOpacity)
            .attr("transform", (d)=>{ return "translate("+[d.interpolatedX,d.interpolatedY]+")"; });
      
      siteSelection.exit().remove();
    }

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

Updated missing url https://rawcdn.githack.com/Kcnarf/d3-voronoi-map/v2.0.1/build/d3-voronoi-map.js to https://rawcdn.githack.com/kcnarf/d3-voronoi-map/v2.0.1/build/d3-voronoi-map.js

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

https://rawcdn.githack.com/Kcnarf/d3-weighted-voronoi/v1.0.1/build/d3-weighted-voronoi.js

https://rawcdn.githack.com/Kcnarf/d3-voronoi-map/v2.0.1/build/d3-voronoi-map.js

https://cdnjs.cloudflare.com/ajax/libs/seedrandom/2.4.3/seedrandom.min.js