timeline - FFT decomposition

This block is an experimentation of how to decompose a timeline thanks to an Fast Fourier Transform (FFT) algorithm.

Usages :

in the top graph, Drag & Drop points to update the timeline, or use the shortcuts below the graph

Notes:

I've done other bl.ocks dealing with timeline analyses:

another block highlights how important detrending is when trying to detect seasonality
another block experiments seasonality detection
another block experiments autocorrelation
another block experiments time series correlation
another block deals with the impact of seasonality when computing the trend of a timeline

Acknowledgments:

<!DOCTYPE html>
<meta charset="utf-8">
<title>timeline - FFT decomposition</title>
<meta content="Illustrating the FFT decomposition of a timeline with d3.js" name="description">
<style>
  
  body {
    position: relative;
    background-color: #ddd;
    margin: auto;
  }
  
  #under-construction {
    display: none;
    position: absolute;
    top: 200px;
    left: 300px;
    font-size: 40px;
  }
  
  .controls {
    position: absolute;
    font: 11px arial;
  }
  #controls1 {
    top: 300px;
    left: 10px;
  }
  #controls2 {
    top: 300px;
    left: 450px;
  }
  #controls3 {
    top: 300px;
    right: 10px;
    text-align: right;
  }
  
  .viz {
    position: absolute;
    background-color: white;
    border-radius: 10px;
    left: 5px;
  }
  .viz#timelines {
    top: 5px;
  }
  .viz#fft {
    top: 355px;
  }
  
  .flow {
    position: absolute;
    font-size: 30px;
    color: darkgrey;
    top: 320px;
  }
  
  .flow span {
    font-size: initial;
  }
  
  #flow-1 {
    left: 447px;
  }
  
  #flow-2 {
    display: none;
    right: 230px;
  }
  
  .axis path,
  .axis line {
    fill: none;
    stroke: black;
    shape-rendering: crispEdges;
  }
  .axis text {
    font-family: sans-serif;
    font-size: 11px;
    fill: black;
  }
  .grid>line, .grid>.intersect {
    fill: none;
    stroke: #ddd;
    shape-rendering: crispEdges;
    vector-effect: non-scaling-stroke;
  }
  .legend {
    font-size: 12px;
  }
  
  .dot {
    fill: steelblue;
    stroke: white;
    stroke-width: 3px;
  }
  .dot.draggable:hover, .dot.dragging {
    fill: pink;
    cursor: ns-resize;
  }
	
  .timeline {
    fill: none;
    stroke: lightsteelblue;
    stroke-width: 2px;
  }
  .timeline.draggable:hover, .timeline.dragging {
  	stroke: pink;
    opacity: 1;
    cursor: ns-resize;
  }
  
  .fft-bar {
    fill: grey;
  }

</style>
<body>
  <div id="timelines" class="viz">
    <div id="controls1" class="controls">
      update time serie with a seasonality's length of <a href="#" onclick="updateSeasonalityPeriod(2);">2</a> /<a href="#" onclick="updateSeasonalityPeriod(3);">3</a> / <a href="#" onclick="updateSeasonalityPeriod(4);">4</a> / <a href="#" onclick="updateSeasonalityPeriod(5);">5</a> / <a href="#" onclick="updateSeasonalityPeriod(6);">6</a> / <a href="#" onclick="updateSeasonalityPeriod(7);">7</a> / <a href="#" onclick="updateSeasonalityPeriod(8);">8</a> / <a href="#" onclick="updateSeasonalityPeriod(9);">9</a> / <a href="#" onclick="updateSeasonalityPeriod(10);">10</a> periods
    </div>
    <div id="controls2" class="controls">
      <a href="#" onclick="increaseSeasonOrderOfMagnitude();">increase</a> / <a href="#"  onclick="decreaseSeasonOrderOfMagnitude();">decrease</a> seasonality's order of magnitude
    </div>
    <div id="controls3" class="controls">
      <a href="#" onclick="increaseTrend();">increase</a> / <a href="#"  onclick="decreaseTrend();">decrease</a> timeline's trend
    </div>
  </div>
  <div id="fft" class="viz"></div>
  <div id="flow-1" class="flow"><span>FFT</span>&#8615;</div>
  <div id="flow-2" class="flow">&#8613;<span>iFFT of selected components</span></div>
  <div id="under-construction">
    UNDER CONSTRUCTION
  </div>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>
  var timeSerie = [];
  var randomness = [];
  var currentSeasonLength = 4;
  var currentSeasonOrderOfMagnitude = 8;
  var currentTrend = 1.4;
  var shouldDetrend = false;
  
  var fftComponents = [];
  var rebuildTimeSerie = [];
  
  var WITH_TRANSITION = true;
  var WITHOUT_TRANSITION = false;
	var duration = 500;
  var NEW_RANDOMNESS = true;
  var PRESERVE_RANDOMNESS = false;
  
  
  //begin: layout conf.
  var timelineVizDimension = {width: 960, height:340},
      fftVizDimension = {width: 960, height:160},
      vizMargin = 5,
      flowWidth = 20
  		legendHeight = 20,
  		xAxisLabelHeight = 10,
  		yAxisLabelWidth = 10,
  		margin = {top: 20, right: 20, bottom: 20, left: 20},
      timelineSvgWidth = timelineVizDimension.width - 2*vizMargin,
      timelineSvgHeight = timelineVizDimension.height - 2*vizMargin - flowWidth/2,
      fftSvgWidth = fftVizDimension.width - 2*vizMargin,
      fftSvgHeight = fftVizDimension.height - 2*vizMargin - flowWidth/2,
      timelineWidth = timelineSvgWidth - margin.left - margin.right - yAxisLabelWidth,
      timelineHeight = timelineSvgHeight - margin.top - margin.bottom - xAxisLabelHeight - 1.5*legendHeight,
      fftWidth = fftSvgWidth - margin.left - margin.right - yAxisLabelWidth,
      fftHeight = fftSvgHeight - margin.top - margin.bottom;
	//end: layout conf.
  
  var drag = d3.drag()
      .subject(function(d) { return d; })
      .on("start", dragStarted)
      .on("drag", dragged1)
      .on("end", dragEnded);
  
  var x = d3.scaleLinear()
				.domain([0, 16])
				.range([0, timelineWidth]);
  var y = d3.scaleLinear()
  			.domain([0, 50])
				.range([0, -timelineHeight]);
  
  var xFft = d3.scaleLinear()
  			.domain([0, 16])
				.range([0, fftWidth]);
  var yFft = d3.scaleLinear()
  			.domain([0, 1])
				.range([0, -fftHeight]);

var xAxisDef = d3.axisBottom()
  	.scale(x)
  	.ticks(16);
  var yAxisDef = d3.axisLeft()
  	.scale(y);
  
  var xAxisFftDef = d3.axisBottom()
  	.scale(xFft)
  	.tickValues(d3.range(0,16));
	var yAxisFftDef = d3.axisLeft()
  	.scale(yFft)
  	.ticks(3)
  	.tickFormat("");
  
  
  //being: build layout
  var svg = d3.select("#timelines").append("svg")
      .attr("width", timelineSvgWidth)
      .attr("height", timelineSvgHeight)
  	.append("g")
  		.attr("transform", "translate(" + [margin.left, margin.top] + ")");

function dragged1(d) {
    d.y += y.invert(d3.event.dy);
    
    computeFftComponents();
    
    redrawDots(WITHOUT_TRANSITION);
    redrawTimelines(WITHOUT_TRANSITION);
    redrawFftComponents(WITHOUT_TRANSITION);
  }

//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