Downsamples data to a given width and height using greedy binning.

downsample.ts

import { maxBy, minBy } from 'lodash'

// see https://gist.github.com/afraser/40a3a6e6f51343681a63d051d211d2f3
import rangeTransform from '@/utils/range-transform'

type Point = {
  x: number
  y: number
}

interface Args {
  data: Point[]
  xMin?: number
  xMax?: number
  yMin?: number
  yMax?: number
  width: number
  height: number
  shouldPreservePoint?: (point: Point) => boolean
}

/**
 * Downsamples data to a given width and height using greedy binning.
 *
 * This works by creating a grid of the given width and height, and then
 * greedily assigning points to the grid. If a point is already assigned to a
 * grid cell it is ignored.
 *
 * You may optionally provide a `shouldPreservePoint` function which will be
 * called for each point. If it returns true, the point will be preserved
 * regardless of whether it is already assigned to a grid cell.
 */
export default function downsample({
  data,
  xMin,
  xMax,
  yMin,
  yMax,
  width,
  height,
  shouldPreservePoint,
}: Args) {
  if (yMax == null) {
    yMax = maxBy(data, 'y')?.y || 0
  }
  if (yMin == null) {
    yMin = minBy(data, 'y')?.y || 0
  }
  if (xMax == null) {
    xMax = maxBy(data, 'x')?.x || 0
  }
  if (xMin == null) {
    xMin = minBy(data, 'x')?.x || 0
  }

  const outWidth = Math.ceil(width)
  const outHeight = Math.ceil(height)

  const a: Record<string, Point> = {}
  data.forEach((point) => {
    const { x, y } = point
    if (shouldPreservePoint && shouldPreservePoint(point)) {
      a[`${x},${y}`] = point
    } else {
      const xa = Math.floor(
        rangeTransform(x, [xMin!, xMax!], [0, outWidth - 1])
      )
      const ya = Math.floor(
        rangeTransform(y, [yMin!, yMax!], [0, outHeight - 1])
      )
      const key = `${xa},${ya}`
      if (!(key in a)) {
        a[key] = point
      }
    }
  })

  return Object.values(a)
}