Pixel-perfect Downsampling — идеальная отрисовка 50 миллионов точек без потерь

[dom1n1k]

Я правильно понимаю, что основная идея LTTB очень похожа на Дугласа-Пейкера?
Отличие по-видимому в том, что последний не подходит для потоковой обработки.

[gearquicker]

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

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

Чисто технически, алгоритм Дугласа-Пейкера можно запаковать так, чтобы обрабатывать потоки данных. Но это будет неэффективно, разумеется. Для задач работы с временными рядами он плохо подходит, зато, наверно, он хорошо подходит для 2d задач, например сжатия контура карт или любой другой плоской непрерывной геометрии.