Skip to content

Instantly share code, notes, and snippets.

@Kcnarf

Kcnarf/.block

Last active September 13, 2019 10:29
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save Kcnarf/8854eacb4843a33e21688ee3f54c314d to your computer and use it in GitHub Desktop.
Save Kcnarf/8854eacb4843a33e21688ee3f54c314d to your computer and use it in GitHub Desktop.
Download ZIP
model-based transition on timelines
Raw
.block
license: gpl-3.0
border: yes
Raw
README.md

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:

  1. simplification: transition from the initial path to its simplified version
  2. simple morphing: transition from the simplified version of the initial path to a simplified version of the final path; this step eases human comprehension
  3. 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:

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

Acknowledgments:

Raw
index.html
<!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);
var a = -2*Math.PI;
for(var k = 0; k < hN; ++k)
{
if(!(even[k] instanceof Complex))
even[k] = new Complex(even[k], 0);
if(!(odd[k] instanceof Complex))
odd[k] = new Complex(odd[k], 0);
var p = k/N;
var t = new Complex(0, a * p);
t.cexp(t).mul(odd[k], t);
amplitudes[k] = even[k].add(t, odd[k]);
amplitudes[k + hN] = even[k].sub(t, even[k]);
}
return amplitudes;
}
/*
basic complex number arithmetic from
http://rosettacode.org/wiki/Fast_Fourier_transform#Scala
*/
function Complex(re, im)
{
this.re = re;
this.im = im || 0.0;
}
Complex.prototype.add = function(other, dst)
{
dst.re = this.re + other.re;
dst.im = this.im + other.im;
return dst;
}
Complex.prototype.sub = function(other, dst)
{
dst.re = this.re - other.re;
dst.im = this.im - other.im;
return dst;
}
Complex.prototype.mul = function(other, dst)
{
//cache re in case dst === this
var r = this.re * other.re - this.im * other.im;
dst.im = this.re * other.im + this.im * other.re;
dst.re = r;
return dst;
}
Complex.prototype.cexp = function(dst)
{
var er = Math.exp(this.re);
dst.re = er * Math.cos(this.im);
dst.im = er * Math.sin(this.im);
return dst;
}
Complex.prototype.log = function()
{
/*
although 'It's just a matter of separating out the real and imaginary parts of jw.' is not a helpful quote
the actual formula I found here and the rest was just fiddling / testing and comparing with correct results.
http://cboard.cprogramming.com/c-programming/89116-how-implement-complex-exponential-functions-c.html#post637921
*/
if( !this.re )
console.log(this.im.toString()+'j');
else if( this.im < 0 )
console.log(this.re.toString()+this.im.toString()+'j');
else
console.log(this.re.toString()+'+'+this.im.toString()+'j');
}
</script>
Raw
timeserie.csv
x y random
1 3 -1
2 10 -1
3 10 1
4 17 0
5 3 1
6 10 2
7 10 0
8 17 -1
9 3 0
10 10 0
11 10 -1
12 17 1
13 3 0
14 10 -1
15 10 1
16 17 0
17 3 2
18 10 1
19 10 -1
20 17 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment