Skip to content

Instantly share code, notes, and snippets.

@afraser
Last active May 11, 2024 00:38
Show Gist options
  • Save afraser/e8deca8de071402e98949519e7e9bff8 to your computer and use it in GitHub Desktop.
Save afraser/e8deca8de071402e98949519e7e9bff8 to your computer and use it in GitHub Desktop.
Downsamples data to a given width and height using greedy binning.
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment