charts.downsample

import { type Sample } from "./charts_downsample_types.ts";

/**
 * Largest-Triangle-Three-Buckets (Steinarsson 2013).
 *
 * Keeps the first and last points; splits the rest into threshold - 2
 * buckets and from each keeps the point that makes the largest triangle with
 * the point kept before it and the average of the next bucket. Peaks and dips
 * survive, which taking every nth point or averaging each bucket would lose.
 * Bucket bounds are computed as floor((i + 1) * every) + 1 with a float
 * `every`, exactly as the reference implementation does, so the choice of
 * points matches it.
 */
export function downsample(points: readonly Sample[], threshold: number): readonly Sample[] {
  if (!Number.isInteger(threshold) || threshold < 3) {
    throw new RangeError(`threshold must be a whole number of at least 3, received ${threshold}`);
  }
  const n = points.length;
  if (threshold >= n) return points.slice();

  const every = (n - 2) / (threshold - 2);
  const sampled: Sample[] = [points[0]];
  let a = 0;
  for (let i = 0; i < threshold - 2; i++) {
    // The average of the next bucket stands in for the point not chosen yet.
    const avgStart = Math.floor((i + 1) * every) + 1;
    const avgEnd = Math.min(Math.floor((i + 2) * every) + 1, n);
    let avgX = 0;
    let avgY = 0;
    for (let j = avgStart; j < avgEnd; j++) {
      avgX += points[j].x;
      avgY += points[j].y;
    }
    avgX /= avgEnd - avgStart;
    avgY /= avgEnd - avgStart;

    const from = Math.floor(i * every) + 1;
    const to = Math.floor((i + 1) * every) + 1;
    const ax = points[a].x;
    const ay = points[a].y;
    let maxArea = -1;
    let next = from;
    for (let j = from; j < to; j++) {
      // Twice the triangle's area; halving it would not change which is largest.
      const area = Math.abs((ax - avgX) * (points[j].y - ay) - (ax - points[j].x) * (avgY - ay));
      // Strictly greater: on a tie the earlier point wins.
      if (area > maxArea) {
        maxArea = area;
        next = j;
      }
    }
    sampled.push(points[next]);
    a = next;
  }
  sampled.push(points[n - 1]);
  return sampled;
}