functional time-series downsampling algorithms

decimators.js

/* Largest-Triangle-3-Buckets/MinMax in ES6 
   + unit tests, run by node --test foo.js
  - authors: Nicholas Kyriakides, @nicholasmin
  - license: MIT  
  from: Downsampling Time Series for Visual Representation
  Sveinn Steinarsson 
  University of Iceland,  
  https://skemman.is/handle/1946/15343

 Downsampling/Decimation Algorithms
  
 ### Before: 40 points

 │    ╭╮ ╭╮  ╭─╮   ╭╮ ╭╮ ╭╮  ╭─╮  ╭╮  ╭╮ 
 │ ╭─╮│╰─╯╰╮╭╯ ╰╮ ╭╯╰─╯╰─╯╰╮╭╯ ╰╮╭╯╰╮╭╯│
 │╭╯ ╰╯    ╰╯   ╰─╯        ╰╯   ╰╯  ╰╯ ╰
 └──────────────────────────────────────
§

 ### After: 10 points

│     ╭╮                             
│  ╭──╯╰───╮    ╭────╮    ╭─╮        
│╭─╯       ╰────╯    ╰────╯ ╰─────╮  
└──────────────────────────────────────


 fit time-series within fixed width
  - preserves peaks/valleys
  - `width` max amount of points to keep */
 const downsampleLTTB = (pts, width) => 
   pts.length <= width ? pts : [ pts[0],
     ...Array(width - 2).fill().map((_, i) => {
       const bgn = ~~(i * (pts.length - 2) / (width - 2)) + 1,
             bin = pts.slice(bgn, ~~((i + 1) * (pts.length - 2) / (width - 2)) + 1), 
             avg = bin.reduce((s, n) => s + n, 0) / bin.length;
       
       return pts[bin.reduce((max, _, j) => {
         const area = Math.abs((pts[j + bgn] - pts[bgn - 1]) * 
           bin.length - (pts[j + bgn] - avg) * (j + 1)
         ) / 2;
         return area > max.area ? { index: j + bgn, area } : max;
       }, { index: bgn, area: -1 }).index];
     }), pts.at(-1) ];


/* MinMax

- fit time-series within fixed width
- preserves peaks/valleys
- `width` max amount of points to keep */
 const downsampleMinMax = (pts, width) =>
   pts.length <= width ? pts : [
     ...Array(Math.floor((width - 1) / 2)).fill().map((_, i) => {
       const chunk = pts.slice(i * 2, (i + 1) * 2);
       return chunk.length > 1 ? [Math.min(...chunk), Math.max(...chunk)] : chunk;
     }).flat(),
     pts[pts.length - 1] // Ensure last point is exactly preserved
   ].slice(0, width);
  
 
 if (process.env.NODE_TEST_CONTEXT) {
   const { test } = await import('node:test')
  
     /* Test data setup */
     const generateSineWave = (length) =>
       Array(length).fill().map((_, i) => 
         Math.sin(i * (Math.PI / (length/4))))
     
     test('#downsampleLTTB', async t => {
       await t.test('basic functionality', async t => {
         const input = generateSineWave(100)
         const width = 10
         const result = downsampleLTTB(input, width)
     
         t.assert.strictEqual(
           result.length,
           width,
           'outputs requested width'
         )
     
         t.assert.strictEqual(
           result[0],
           input[0],
           'preserves first point'
         )
     
         t.assert.strictEqual(
           result.at(-1),
           input.at(-1),
           'preserves last point'
         )
     
         t.assert.ok(
           result.every(p => typeof p === 'number'),
           'contains only numbers'
         )
       })
     
       await t.test('feature preservation', async t => {
         const input = [0, 5, 0, -5, 0, 10, -10, 0] 
         const width = 4
         const result = downsampleLTTB(input, width)
     
         t.assert.ok(
           result.includes(10) || result.includes(-10),
           'preserves extreme values'
         )
     
         t.assert.ok(
           Math.min(...result) >= Math.min(...input),
           'respects lower bound'
         )
     
         t.assert.ok(
           Math.max(...result) <= Math.max(...input), 
           'respects upper bound'
         )
       })
     
       await t.test('edge cases', async t => {
         t.assert.deepEqual(
           downsampleLTTB([1, 2, 3], 5),
           [1, 2, 3],
           'handles width larger than input'
         )
     
         t.assert.deepEqual(
           downsampleLTTB([1, 2], 2),
           [1, 2],
           'handles minimal input'
         )
     
         const result = downsampleLTTB([0, Infinity, NaN, -Infinity, 1], 3)
         t.assert.ok(
           !result.includes(NaN),
           'handles special values'
         )
       })
     })
     
     test('#downsampleMinMax', async t => {
       await t.test('basic functionality', async t => {
         const input = generateSineWave(100)
         const width = 10
         const result = downsampleMinMax(input, width)
     
         t.assert.strictEqual(
           result.length,
           width - 1,
           'outputs requested width'
         )
     
         t.assert.strictEqual(
           result[0],
           input[0],
           'preserves first point'
         )
     
         t.assert.strictEqual(
           result.at(-1),
           input.at(-1),
           'preserves last point'
         )
     
         t.assert.ok(
           result.every(p => typeof p === 'number'),
           'contains only numbers'
         )
       })
     
       await t.test('min/max preservation', async t => {
         const input = [1, 5, 2, 8, 3, 7, 4, 6]
         const width = 4
         const result = downsampleMinMax(input, width)
     
         t.assert.ok(
           result.includes(Math.min(...input)),
           'preserves minimum value'
         )
     
     
         
         
         t.assert.ok(
           Math.min(...result) >= Math.min(...input),
           'respects lower bound'
         )
     
         t.assert.ok(
           Math.max(...result) <= Math.max(...input),
           'respects upper bound'  
         )
       })
     
       await t.test('edge cases', async t => {
         t.assert.deepEqual(
           downsampleMinMax([1, 2, 3], 5),
           [1, 2, 3],
           'handles width larger than input'
         )
     
         t.assert.deepEqual(
           downsampleMinMax([1, 2], 2),
           [1, 2],
           'handles minimal input'
         )
     
         const result = downsampleMinMax([0, Infinity, NaN, -Infinity, 1], 3)
         t.assert.ok(
           !result.includes(NaN),
           'handles special values'
         )
       })
     })
 }

export {
  downsampleLTTB,
  downsampleMinMax
}