impl/python.py

import math
from typing import List, Sequence

from .charts_downsample_types import Sample


def downsample(points: Sequence[Sample], threshold: int) -> List[Sample]:
    """Largest-Triangle-Three-Buckets (Steinarsson 2013).

    Same bucket arithmetic, in the same order, as the TypeScript and Rust
    versions and the reference implementation. See the README.
    """
    if isinstance(threshold, bool) or not isinstance(threshold, int) or threshold < 3:
        raise ValueError("threshold must be a whole number of at least 3, received %r" % (threshold,))
    n = len(points)
    if threshold >= n:
        return list(points)

    every = (n - 2) / (threshold - 2)
    sampled = [points[0]]
    a = 0
    for i in range(threshold - 2):
        avg_start = math.floor((i + 1) * every) + 1
        avg_end = min(math.floor((i + 2) * every) + 1, n)
        avg_x = 0.0
        avg_y = 0.0
        for j in range(avg_start, avg_end):
            avg_x += points[j].x
            avg_y += points[j].y
        avg_x /= avg_end - avg_start
        avg_y /= avg_end - avg_start

        start = math.floor(i * every) + 1
        stop = math.floor((i + 1) * every) + 1
        ax = points[a].x
        ay = points[a].y
        max_area = -1.0
        nxt = start
        for j in range(start, stop):
            area = abs((ax - avg_x) * (points[j].y - ay) - (ax - points[j].x) * (avg_y - ay))
            if area > max_area:
                max_area = area
                nxt = j
        sampled.append(points[nxt])
        a = nxt
    sampled.append(points[n - 1])
    return sampled