LTTB 最大三角形三桶法详解

LTTB 全称 Largest Triangle Three Buckets（最大三角形三桶法），是一种专为时间序列 / 折线图可视化设计的高效降采样算法。

它能在把 10 万 + 数据点压缩到几百～2000 点的同时，最大程度保留曲线的视觉特征（峰值、谷值、趋势拐点），比'每桶取平均''每桶取最大/最小'效果好得多，常用于 uPlot、Highcharts、TradingView 等大图表库。

为什么需要 LTTB？

• 直接绘制 10 万点 → Canvas 渲染性能受限（浏览器渲染瓶颈）
• 简单平均采样 → 容易'平滑处理'导致尖峰抹平，视觉失真严重
• LTTB 的优势：几何学驱动，优先保留'对整体形状贡献最大'的点

核心思想（Three Buckets）

算法每次同时考虑3 个桶：

1. 前一个桶 → 用上一次选中的点 prev 代表
2. 当前桶 → 遍历桶内所有候选点
3. 下一个桶 → 用平均点（avg）代表

对当前桶的每个点 c，计算三角形 prev — c — avg 的面积，选择面积最大的点作为当前桶的代表点。

数学公式：三角形面积（叉积法）

[ \text{Area} = \frac{1}{2} \left| (x_2 - x_1)(y_3 - y_1) - (x_3 - x_1)(y_2 - y_1) \right| ] 其中：

• $(x_1, y_1)$ = 前一个已选点 prev
• $(x_2, y_2)$ = 当前桶候选点 c
• $(x_3, y_3)$ = 下一个桶的平均点 avg

标准算法流程（伪代码）

function lttb(data: Point[], threshold: number): Point[] {
  const n = data.length;
  if (n <= threshold) return data;

  const sampled: Point[] = [data[0]];           // 永远保留第一个点
  const every = (n - 2) / (threshold - 2);      // 桶大小

  let a = 0;                                    // 上一个选中点的索引

  for (let i = 0; i < threshold - 2; i++) {
    // 计算下一个桶的平均点
    const avgRangeStart = Math.floor((i + 1) * every) + 1;
    const avgRangeEnd = Math.min(Math.floor((i + 2) * every) + 1, n);
    let avgX = 0, avgY = 0;
    for (let j = avgRangeStart; j < avgRangeEnd; j++) {
      avgX += data[j].x;
      avgY += data[j].y;
    }
    const avgRangeLength = avgRangeEnd - avgRangeStart;
    avgX /= avgRangeLength;
    avgY /= avgRangeLength;

    // 在当前桶里找面积最大的点
    let maxArea = -1;
    let nextA = 0;
    const rangeOffs = Math.floor((i + 1) * every) + 1;
    const rangeTo = Math.min(Math.floor((i + 2) * every) + 1, n);

    for (let j = rangeOffs; j < rangeTo; j++) {
      const area = Math.abs(
        (data[a].x - avgX) * (data[j].y - data[a].y) -
        (data[a].x - data[j].x) * (avgY - data[a].y)
      ) * 0.5;

      if (area > maxArea) {
        maxArea = area;
        nextA = j;
      }
    }

    sampled.push(data[nextA]);
    a = nextA;   // 更新为下一次的前驱
  }

  sampled.push(data[n - 1]);  // 永远保留最后一个点
  return sampled;
}

时间复杂度：O(n) —— 非常高效，10 万点在浏览器里 < 10ms 就能完成。

在实际功耗数据点渲染中的应用

• 功耗曲线 10 万 + 点 → 设置 threshold = 2000
• 缩放 / 平移时，只对当前 viewport 内的原始数据再跑一次 LTTB（动态重采样）
• 结合 uPlot 的 setData + requestAnimationFrame，实现流畅交互