Palette from Image — TypeScript source

// Pure palette extraction — median-cut quantization over RGBA pixels.
// No React, no DOM; deterministic (stable sorts only).

export interface Swatch {
  r: number;
  g: number;
  b: number;
  population: number;
}

interface Pixel {
  r: number;
  g: number;
  b: number;
}

/** Down-sample so large images quantize in bounded time. */
const MAX_SAMPLES = 16384;

/** Median-cut quantization: split the widest channel at the median, repeat. */
export function extractPalette(rgba: Uint8Array, maxColors = 8): Swatch[] {
  const total = Math.floor(rgba.length / 4);
  if (total === 0) return [];

  const pixels: Pixel[] = [];
  const stride = Math.max(1, Math.floor(total / MAX_SAMPLES));
  for (let i = 0; i < total; i += stride) {
    const o = i * 4;
    if (rgba[o + 3] === 0) continue;
    pixels.push({ r: rgba[o], g: rgba[o + 1], b: rgba[o + 2] });
  }
  if (pixels.length === 0) return [];

  let buckets: Pixel[][] = [pixels];
  while (buckets.length < maxColors) {
    // Widest-range bucket with more than one distinct value wins the split.
    let bestIdx = -1;
    let bestRange = 1; // Range 1 (exact duplicates only) never splits further.
    for (let i = 0; i < buckets.length; i++) {
      const range = channelRange(buckets[i]);
      if (range > bestRange) {
        bestRange = range;
        bestIdx = i;
      }
    }
    if (bestIdx === -1) break;
    const bucket = buckets.splice(bestIdx, 1)[0];
    buckets.push(...splitBucket(bucket));
  }

  return buckets
    .filter((bucket) => bucket.length > 0)
    .map((bucket) => ({
      r: Math.round(bucket.reduce((s, p) => s + p.r, 0) / bucket.length),
      g: Math.round(bucket.reduce((s, p) => s + p.g, 0) / bucket.length),
      b: Math.round(bucket.reduce((s, p) => s + p.b, 0) / bucket.length),
      population: bucket.length,
    }))
    .sort((a, b) => b.population - a.population);
}

function channelRange(bucket: Pixel[]): number {
  let minR = 255, maxR = 0, minG = 255, maxG = 0, minB = 255, maxB = 0;
  for (const p of bucket) {
    if (p.r < minR) minR = p.r;
    if (p.r > maxR) maxR = p.r;
    if (p.g < minG) minG = p.g;
    if (p.g > maxG) maxG = p.g;
    if (p.b < minB) minB = p.b;
    if (p.b > maxB) maxB = p.b;
  }
  return Math.max(maxR - minR, maxG - minG, maxB - minB);
}

function splitBucket(bucket: Pixel[]): Array<Pixel[]> {
  let minR = 255, maxR = 0, minG = 255, maxG = 0, minB = 255, maxB = 0;
  for (const p of bucket) {
    if (p.r < minR) minR = p.r;
    if (p.r > maxR) maxR = p.r;
    if (p.g < minG) minG = p.g;
    if (p.g > maxG) maxG = p.g;
    if (p.b < minB) minB = p.b;
    if (p.b > maxB) maxB = p.b;
  }
  const ranges = { r: maxR - minR, g: maxG - minG, b: maxB - minB };
  const channel = (['r', 'g', 'b'] as const).reduce((a, c) => (ranges[c] > ranges[a] ? c : a), 'r');

  const sorted = [...bucket].sort((a, b) => a[channel] - b[channel]); // stable, deterministic
  const mid = Math.floor(sorted.length / 2);
  return [sorted.slice(0, mid), sorted.slice(mid)];
}

/** Format a swatch as #rrggbb. */
export function toHex({ r, g, b }: Swatch): string {
  return `#${[r, g, b].map((v) => v.toString(16).padStart(2, '0')).join('')}`;
}