Visual downsampling of graph data

common.js

export const binarySearchByField = function (data, field, value) {
    var r = data.length, l = -1, m;
    while (r - l > 1)
        if (data[m = r + l >> 1][field] < value) l = m
        else r = m

    return {l, r}
}

export const binarySearchByIndex0 = function (data, value) {
    return binarySearchByField(data, 0, value)
}

downsample.coffee

import {binarySearchByIndex0} from './common'

# data: [[x1, y1], [x2, y2], ...]
# min_x/max_x: X axis interval
# pnt_count: number of pixels [min_x, max_x] interval should map to

export default (data, [min_x, max_x], pnt_count) ->
    left  = binarySearchByIndex0(data, min_x).r
    right = binarySearchByIndex0(data, max_x).r

    data = data.slice(Math.max(left-1, 0), right+1)

    data_length = data.length
    return data if data_length <= pnt_count

    x_per_bucket = (max_x - min_x) / pnt_count
    bucket_l = min_x
    bucket_l -= bucket_l % x_per_bucket

    output = [data[0]]

    i = 0

    loop
        bucket_r = bucket_l + x_per_bucket

        max = null
        min = null
        first = last = null
        first_null = no
        last_null = no
        while data[i]? and i < data_length and data[i][0] < bucket_r
            if not max? or data[i][1] > max[1]
                max = data[i]
            if not min? or data[i][1] < min[1]
                min = data[i]
            if not first?
                if data[i][1] == null
                    first_null = yes
                first = data[i]
            last_null = data[i][1] == null
            last = data[i]
            i++


        if first_null
            output.push [bucket_l, null]
        else if first?
            output.push first

        if min? and max?
            if min[0] < max[0]
                if min[0] != first?[0]
                    output.push min
                if max[0] != last?[0]
                    output.push max
            else
                if max[0] != first?[0]
                    output.push max
                if min[0] != last?[0]
                    output.push min

        if last_null
            output.push [bucket_r-1, null]
        else if last?
            output.push last

        if i >= data_length
            break

        bucket_l += x_per_bucket

    return output