model-based transition on timelines

This block experiments a way to make transitions between erratic pathes easier to understand/follow. The idea is to use simplified versions of the paths in order to ease the human comprehension of the transition. Simplified versions of paths are computed thanks to some models.

Hence, the transition from an intial path to a final path takes 3 stages:

simplification: transition from the initial path to its simplified version
simple morphing: transition from the simplified version of the initial path to a simplified version of the final path; this step eases human comprehension
complexification: transition from the simplified version of the final path to the final path

This block uses two models to compute the simplified versions of paths:

a Fast Fourier Transform (FFT) and inverse Fast Fourier Transform (iFFT) algorithms
a Moving Average algorithm

Acknowledgments:

<!DOCTYPE html>
<meta charset="utf-8">
<title>FFT-based transition on timelines</title>
<meta content="Experimenting a FFT-based transitioning system between timelines in d3.js" name="description">
<style>
  
  body {
    position: relative;
    margin: auto;
  }
  
  #under-construction {
    display: none;
    position: absolute;
    top: 200px;
    left: 300px;
    font-size: 40px;
  }
  
  .path {
    fill: none;
    stroke: steelblue;
    stroke-width: 2px;
  }
  
  .progresses path,
  .progresses line {
    fill: none;
    stroke: black;
    shape-rendering: crispEdges;
  }
  .progresses text, text.small {
    font-family: sans-serif;
    font-size: 11px;
    fill: black;
  }
  
  .progresses .indicator {
    fill: none;
    stroke-width: 1;
    stroke: black;
  }
</style>
<body onload="initData()">
  <svg></svg>
  <div id="under-construction">
    UNDER CONSTRUCTION
  </div>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>
  var WITH_TRANSITION = true;
  var WITHOUT_TRANSITION = false;
	var duration = 3000;
  
  var radix2 = 7,
      pathDataCount = Math.pow(2,radix2),	// FFT only on data of length 2-radix
      currentPathData = [],
      newPathData = [],
      ease = d3.easeLinear,
      tweenCPs = [0.3, 0.7];							// timing of simplified paths; in ]0,1[
  
  //begin: fft-based conf.
  var	mainComponentCount = 2*radix2+1,			// simplification strength
      currentFftComponents = [],
      currentFftMainComponents = [],
      currentFftSimplifiedPathData = [],
      newFftComponents = [],
      newFftMainComponents = [],
      newFftSimplifiedPathData = [];
  //end: fft-based conf.
  
  //begin: moving average conf.
  var windowSize = (radix2%2===0)? radix2+1 : radix2,
      halfWindowSize = Math.floor(windowSize/2),
      currentMovingAvgSimplifiedPathData = [],
      newMovingAvgSimplifiedPathData = [];
  //end: moving average conf.
  
  //begin: layout conf.
  var margin = {top: 20, right: 20, bottom: 20, left: 20},
      svgWidth = 960,
      svgHeight = 500,
      width = svgWidth - margin.left - margin.right,
      height = svgHeight - margin.top - margin.bottom;
	//end: layout conf.
  
  var x = d3.scaleLinear()
				.domain([0, pathDataCount-1])
				.range([0, width]);
  var y = d3.scaleLinear()
  			.domain([0, 1])
				.range([10, height/3-10]);
  
  var xProgress = d3.scaleLinear()
				.domain([0, 1])
				.range([0, width]);
  
  var line = d3.line()
  							.x(function(d,i){ return x(i); })
  							.y(function(d){ return y(d); })
  							.curve(d3.curveBasis);
  
  
  //begin: init layout and define reusable d3 selections
  d3.select("svg")
      .attr("width", svgWidth)
      .attr("height", svgHeight);
  var drawingArea = d3.select("svg").append("g")
  		.attr("class", "drawing-area")
  		.attr("transform", "translate(" + [margin.left, margin.top] + ")");
  
  var basicPath = drawingArea
  									.append("g")
  										.classed("transition-container", true)
  										.append("path")
  										.classed("path", true);
  var fftPath = drawingArea
  								.append("g")
  									.classed("transition-container", true)
                  	.attr("transform", "translate("+[0,height/3]+")")
                  	.append("path")
                  		.classed("path", true);
  var movingAvgPath = drawingArea
  								.append("g")
  									.classed("transition-container", true)
                  	.attr("transform", "translate("+[0,2*height/3]+")")
                  	.append("path")
                  		.classed("path", true);
  
  var delta = 5;
  var progresses = drawingArea.append("g")
  		.classed("progresses", true)
  		.attr("transform", "translate("+[0,height/3]+")");
  
  progresses.append("path")
    .attr("d", "M"+[0,delta]+"h"+width);
  progresses.append("path")
    .attr("d", "M"+[0,-delta]+"h"+width);
  progresses.selectAll(".tick")
  	.data([0,tweenCPs[0],tweenCPs[1],1])
  	.enter()
  		.append("path")
  		.attr("d", function(d,i) {
    		var x=xProgress(d);
    		if (i%3===0) {
          return "M"+[x,-delta-4]+"v8M"+[x,delta-4]+"v8";
        } else {
          return "M"+[x,delta-4]+"v8";
        }
      });
  
  progresses.append("text")
    .attr("transform", "translate("+[xProgress(0),-delta-7]+")")
    .attr("text-anchor", "begin")
    .text("initial path");
  progresses.append("text")
    .attr("transform", "translate("+[xProgress(tweenCPs[0]),delta+15]+")")
    .attr("text-anchor", "middle")
    .text("simplified initial path");
  progresses.append("text")
    .attr("transform", "translate("+[xProgress(tweenCPs[1]),delta+15]+")")
    .attr("text-anchor", "middle")
    .text("simplified final path");
  progresses.append("text")
    .attr("transform", "translate("+[xProgress(1),-delta-7]+")")
    .attr("text-anchor", "end")
    .text("final path");
  
  var basicProgressIndicator = progresses.append("circle")
  			.classed("indicator", true)
  			.attr("r", 3)
  			.attr("cy", -5)
  			.attr("cx", xProgress(0));
  var modelBasedProgressIndicator = progresses.append("circle")
  			.classed("indicator", true)
  			.attr("r", 3)
  			.attr("cy", 5)
  			.attr("cx", xProgress(0));
  
  drawingArea.append("text")
  	.text("D3's path transition");
  drawingArea.append("text")
  	.classed("small", true)
  	.attr("transform", "translate("+[130,0]+")")
  	.text("("+pathDataCount+" points per path)");
  drawingArea.append("text")
  	.attr("transform", "translate("+[0,2*height/3]+")")
  	.text("Path transition using simplified versions of paths for easier human comprehension (fft-based model, "+mainComponentCount+" components retained)");
  drawingArea.append("text")
  	.attr("transform", "translate("+[0,height]+")")
  	.text("Path transition using simplified versions of paths for easier human comprehension (moving average model, "+windowSize+" points)");
	//end: build layout and define reusable d3 selections
  
  function initData() {
    computeNewPathData();
		computeNewFftComponents();
    computeNewFftMainComponents();
    computeNewFftSimplifiedPathData();
    computeNewMovingAvgSimplifiedPathData();
    
    drawPaths();
  }
  
  //begin: main loop
  d3.interval(function(elapsed) {
    prepareLoop();
    computeNewPathData();
    computeNewFftComponents();
    computeNewFftMainComponents();
    computeNewFftSimplifiedPathData();
    computeNewMovingAvgSimplifiedPathData();
    
    redrawPaths(WITH_TRANSITION);
    animateTweenIndicators()
  }, duration+1000);
  //end: main loop
  
  function computeNewPathData() {
    var pathData = [];
    var i;
    
    for (i=0; i<pathDataCount; i++) {
      pathData.push(Math.random());
    }
    newPathData = pathData;
  }
  
  //computeNewFftComponents: computes FFT's components of the newPathData
  function computeNewFftComponents() {
    var complexPathData = newPathData.map(function(d,i) {
      return new Complex(i, d);
    })
    newFftComponents = cfft(complexPathData);
  }
  
  //computeNewFftMainComponents: retains only main FFT's components
  function computeNewFftMainComponents() {
    var fftMainComponents = [],
        apks,
        mainIndices;
    
    apks = newFftComponents.map(function(c,i){ return {f: i, apk: apk(c)}; });
    apks.sort(function(apk0, apk1){ return apk1.apk-apk0.apk; });
    mainIndices = apks.slice(0,mainComponentCount).map(function(apk){ return apk.f; });
    
    newFftComponents.forEach(function(c,i){
      if (mainIndices.includes(i)) {
        fftMainComponents.push(new Complex(c.re, c.im));
      } else {
        fftMainComponents.push(new Complex(0, 0));
      }
    })
		newFftMainComponents = fftMainComponents;
  }
  
  //computeNewFftSimplifiedPathData: compute path data from retained FFT's components
  function computeNewFftSimplifiedPathData() {
    var fftSimplifiedPathData = icfft(newFftMainComponents);
    
    newFftSimplifiedPathData = fftSimplifiedPathData.map(function(d){ return d.im; });
  }
  
  function apk(c) { return Math.pow(c.re,2)+Math.pow(c.im,2); };
  
  function computeNewMovingAvgSimplifiedPathData() {
    var movingAvgSimplifiedPathData = [],
    		cumul = 0,
        j;
    
    newPathData.map(function(d,i) {
      cumul += d;
      if (i===windowSize-1) {
        for(j=0; j<halfWindowSize; j++) {
          movingAvgSimplifiedPathData.push(cumul/windowSize);
        }
        movingAvgSimplifiedPathData.push(cumul/windowSize);
      }
      if (i>=windowSize) {
        cumul -= newPathData[i-windowSize];
        movingAvgSimplifiedPathData.push(cumul/windowSize);
      }
    })
    for(j=0; j<halfWindowSize; j++) {
      movingAvgSimplifiedPathData.push(cumul/windowSize);
    }
    newMovingAvgSimplifiedPathData = movingAvgSimplifiedPathData;
  }
  
  function drawPaths(withTransition) {
    basicPath.transition()
      .attr("d", line(newPathData));
		fftPath.transition()
      .attr("d", line(newPathData));
    movingAvgPath.transition()
      .attr("d", line(newPathData));
  }
  
  function redrawPaths(withTransition) {
		basicPath.transition()
      .duration(withTransition? duration : 0)
      .attr("d", line(newPathData));
    fftPath.transition()
      .duration(withTransition? duration : 0)
    	.ease(ease)
    	.attrTween("d", fftTween());
    movingAvgPath.transition()
      .duration(withTransition? duration : 0)
    	.ease(ease)
    	.attrTween("d", movingAvgTween());
  }
  
  //call modelBasedTween with FFT-based interim patData
  function fftTween() {
    return modelBasedTween(currentFftSimplifiedPathData, newFftSimplifiedPathData);
  }
  
  //call modelBasedTween with movingAvg-based interim patData
  function movingAvgTween() {
    return modelBasedTween(currentMovingAvgSimplifiedPathData, newMovingAvgSimplifiedPathData);
  }
  
  //modelBasedTween: separate transition in 3 stages:
  	// stage 1: simplification: from (erratic) initial path to simplified version
  	// stage 2: simple morphing: transition from simplified initial path to simplified final path
  	// stage 3: complexification: from simplified final path to (erratic) final path
  function modelBasedTween(currentSimplifiedPathData, newSimplifiedPathData) {
    return function() {
      var stage1Interpolators = [],
      		stage2Interpolators = [],
          stage3Interpolators = [],
          current, currentSimplified, newSimplified;
      
      newPathData.forEach(function(d,i) {
        current = currentPathData[i];
        currentSimplified = currentSimplifiedPathData[i];
        newSimplified = newSimplifiedPathData[i];
        stage1Interpolators.push(d3.interpolate(current,currentSimplified));
        stage2Interpolators.push(d3.interpolate(currentSimplified,newSimplified));
        stage3Interpolators.push(d3.interpolate(newSimplified,d));
      });
      
      return function(t) {
        var t1,
            stageInterpolators,
        		interimFftComponents,
            interimComplexData,
            pathData;
        
        if (t<1) {
          if (t<tweenCPs[0]) {
            t1 = d3.easeCubicInOut(t/tweenCPs[0]);
            stageInterpolators = stage1Interpolators;
          } else if (t<tweenCPs[1]) {
            t1 = d3.easeCubicInOut((t-tweenCPs[0])/(tweenCPs[1]-tweenCPs[0]));
            stageInterpolators = stage2Interpolators;
          } else {
            t1 = d3.easeCubicInOut((t-tweenCPs[1])/(1-tweenCPs[1]));
            stageInterpolators = stage3Interpolators;
          }
          pathData = stageInterpolators.map(function(i) { return i(t1); })
        } else {
        	pathData = newPathData;
        }
        
        return line(pathData);
      };
    }; 
  }
  
  function animateTweenIndicators() {
    basicProgressIndicator
    	.attr("cx", 0)
    	.transition()
    		.duration(duration)
    		.attr("cx", xProgress(1));
    modelBasedProgressIndicator
      .attr("cx", 0)
    	.transition()
    		.duration(duration)
    		.ease(function(t) {
      		var t1;
      		
      		if (t<tweenCPs[0]) {
            t1 = d3.easeCubicInOut(t/tweenCPs[0]);
            t1 = t1*tweenCPs[0];
          } else if (t<tweenCPs[1]) {
            t1 = d3.easeCubicInOut((t-tweenCPs[0])/(tweenCPs[1]-tweenCPs[0]));
            t1 = t1*(tweenCPs[1]-tweenCPs[0])+tweenCPs[0];
          } else {
            t1 = d3.easeCubicInOut((t-tweenCPs[1])/(1-tweenCPs[1]));
            t1 = t1*(1-tweenCPs[1])+tweenCPs[1];
          }
		      return t1;
    		})
    		.attr("cx", xProgress(1));
  }
  
  function prepareLoop() {
    currentPathData = newPathData;
    currentFftComponents = newFftComponents;
    currentFftMainComponents = newFftMainComponents;
    currentFftSimplifiedPathData = newFftSimplifiedPathData;
    currentMovingAvgSimplifiedPathData = newMovingAvgSimplifiedPathData;
  }
  
  /******************************************************************/
  /* complex fast fourier transform and inverse from                */
  /* https://rosettacode.org/wiki/Fast_Fourier_transform#JavaScript */
  /******************************************************************/
  function icfft(amplitudes)
  {
    var N = amplitudes.length;
    var iN = 1 / N;

//conjugate if imaginary part is not 0
    for(var i = 0 ; i < N; ++i)
      if(amplitudes[i] instanceof Complex)
        amplitudes[i].im = -amplitudes[i].im;

//apply fourier transform
    amplitudes = cfft(amplitudes)

for(var i = 0 ; i < N; ++i)
    {
      //conjugate again
      amplitudes[i].im = -amplitudes[i].im;
      //scale
      amplitudes[i].re *= iN;
      amplitudes[i].im *= iN;
    }
    return amplitudes;
  }

function cfft(amplitudes)
  {
    var N = amplitudes.length;
    if( N <= 1 )
      return amplitudes;

var hN = N / 2;
    var even = [];
    var odd = [];
    even.length = hN;
    odd.length = hN;
    for(var i = 0; i < hN; ++i)
    {
      even[i] = amplitudes[i*2];
      odd[i] = amplitudes[i*2+1];
    }
    even = cfft(even);
    odd = cfft(odd);

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