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;                                    

   ( i = ; i < threshold - ; i++) {
    
     avgRangeStart = .((i + ) * every) + ;
     avgRangeEnd = .(.((i + ) * every) + , n);
     avgX = , avgY = ;
     ( j = avgRangeStart; j < avgRangeEnd; j++) {
      avgX += data[j].;
      avgY += data[j].;
    }
     avgRangeLength = avgRangeEnd - avgRangeStart;
    avgX /= avgRangeLength;
    avgY /= avgRangeLength;

    
     maxArea = -;
     nextA = ;
     rangeOffs = .((i + ) * every) + ;
     rangeTo = .(.((i + ) * every) + , n);

     ( j = rangeOffs; j < rangeTo; j++) {
       area = .(
        (data[a]. - avgX) * (data[j]. - data[a].) -
        (data[a]. - data[j].) * (avgY - data[a].)
      ) * ;

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

    sampled.(data[nextA]);
    a = nextA;   
  }

  sampled.(data[n - ]);  
   sampled;
}