들어가며

하이닉스에 파견가기 전, 기술적으로 여러가지 준비물이 필요한 상황이 되었다. 그 중 하나가 바로 데이터시각화 기술이다. 나는 처음에는 D3에 대해 배웠으니 이제 api 데이터만 뿌리면 되는거 아닌가? 하는 생각이 있었으나 데이터가 많아질 경우도 고려를 해야했고 이를 해결해줄 알고리즘이 바로 LTTB였다.

LTTB란

왜 LTTB가 필요하지?

데이터를 차트위에 그릴 때 수십만개의 점을 그대로 그리면 브라우저가 느려지고, 픽셀 수 보다 많은 점은 무의미하다. 그래서 점 개수를 줄이면서 선이 비슷하게 보이도록 다운샘플링을 해야한다.

핵심 아이디어

데이터를 n개의 버킷으로 나누고, 각 버킷에서 "삼각형 넓이가 가장 큰" 점을 선택한다.

삼각형 넓이가 크다는 뜻은 A와 C를 잇는 선 AC와 가장 멀리 떨어져 있다는 뜻이고 이는 가장 두드러지는, 시각적으로 눈에 잘 띈다는 뜻이다. 그 외 다른 점들은 버려도 차트 모양이 크게 변하지 않으니 버리게 된다.

TypeScript 구현

TS에서 구현은 다음과 같다.


TYPESCRIPT
1type Point = [number, number]; // [x, y]
2
3function lttb(data: Point[], threshold: number): Point[] {
4  const dataLength = data.length;
5
6  // 포인트 수가 목표 이하면 그대로 반환
7  if (threshold >= dataLength || threshold === 0) {
8    return data;
9  }
10
11  const sampled: Point[] = [];
12  
13  // 첫 번째 포인트는 항상 포함
14  sampled.push(data[0]);
15
16  // 실제 데이터 구간을 (threshold - 2)개 버킷으로 나눔
17  // 첫/마지막 포인트는 고정이라 제외
18  const bucketSize = (dataLength - 2) / (threshold - 2);
19
20  let prevSelectedIndex = 0; // 이전 버킷에서 선택된 포인트의 인덱스
21
22  for (let bucketIndex = 0; bucketIndex < threshold - 2; bucketIndex++) {
23    // 현재 버킷의 범위 계산
24    const bucketStart = Math.floor((bucketIndex + 0) * bucketSize) + 1;
25    const bucketEnd   = Math.floor((bucketIndex + 1) * bucketSize) + 1;
26
27    // 다음 버킷의 평균 포인트(C) 계산
28    const nextBucketStart = bucketEnd;
29    const nextBucketEnd   = Math.min(
30      Math.floor((bucketIndex + 2) * bucketSize) + 1,
31      dataLength
32    );
33
34    let avgX = 0, avgY = 0;
35    const nextBucketSize = nextBucketEnd - nextBucketStart;
36    for (let i = nextBucketStart; i < nextBucketEnd; i++) {
37      avgX += data[i][0];
38      avgY += data[i][1];
39    }
40    avgX /= nextBucketSize;
41    avgY /= nextBucketSize;
42
43    // A: 이전 버킷에서 선택된 포인트
44    const [ax, ay] = data[prevSelectedIndex];
45
46    // 현재 버킷에서 삼각형 넓이가 최대인 포인트(B) 찾기
47    let maxArea = -1;
48    let selectedIndex = bucketStart;
49
50    for (let i = bucketStart; i < bucketEnd; i++) {
51      const [bx, by] = data[i];
52
53      // 삼각형 넓이 = |ax(by - cy) + bx(cy - ay) + cx(ay - by)| / 2
54      // 비교 목적이므로 / 2는 생략 가능
55      const area = Math.abs(
56        (ax - avgX) * (by - ay) -
57        (bx - ax) * (avgY - ay)
58      );
59
60      if (area > maxArea) {
61        maxArea = area;
62        selectedIndex = i;
63      }
64    }
65
66    sampled.push(data[selectedIndex]);
67    prevSelectedIndex = selectedIndex;
68  }
69
70  // 마지막 포인트는 항상 포함
71  sampled.push(data[dataLength - 1]);
72
73  return sampled;
74}

삼각형을 만들어나가는 과정이 익숙치 않았지만 한번 이해하고 정립하니 구현은 생각보다 어렵지 않았다.

LTTB 알고리즘

들어가며

LTTB란

왜 LTTB가 필요하지?

핵심 아이디어

TypeScript 구현