Выборка меньшего набора точек линейного графика без потери трендов

Question

Учитывая набор координат X / Y ([(x, y)] с увеличением X (представляющего временную метку) и Y, представляющего значение / измерение в той временной метке.

Этот набор может возможно быть огромным, и я хотел бы не возвращать каждую точку в наборе для отображения, а вместо этого найти меньшее подмножество, которое представляло бы общую тенденцию измерения (некоторый уровень потери точности в линейном графике будет приемлемым).

До сих пор я пробовал простую равномерную выборку точек пропуска измерений с одинаковым интервалом, а затем добавлял максимальное / минимальное значение измерения к подмножеству. Хотя это просто, он не очень хорошо учитывает локальные пики или впадины, если измерения часто колеблются.

Мне интересно, существуют ли какие-либо стандартные алгоритмы, которые решают этот тип проблем на стороне сервера?

Оцените, если кто-нибудь решил это или знает о какой-либо полезности / общие библиотеки, решающие такие проблемы. Я на Java, но если есть какая-либо ссылка на стандартную alg orithms я мог бы попытаться реализовать один в Java.

Answer 1

Трудно дать общий ответ на этот вопрос. Все зависит от того, как хранятся ваши точки данных, какими свойствами обладает ваша диаграмма, как она отображается и т. Д. c.

Но, как подсказал @dmuir, вам следует проверить алгоритм Дугласа-Пекера. Другой подход, который я только что придумал, может состоять в том, чтобы разделить входные данные на куски некоторого размера (возможно, соответствующие одному горизонтальному пикселю), а затем использовать некоторую статистику c (мин, макс или среднее) для рендеринга порции. Если вы используете статистику выполнения при добавлении точек данных в блок, это должно быть O (n), так что это не дороже, чем чтение ваших точек данных.