Удалить лишние точки для линейного графика

Question

Я пытаюсь построить большое количество точек, используя какую-то библиотеку.Точки упорядочены по времени, и их значения можно считать непредсказуемыми.

В настоящее время моя проблема заключается в том, что из-за большого количества точек библиотека отдает слишком много времени на визуализацию.Многие из точек являются избыточными (то есть - они находятся «на одной линии», как определено функцией y = ax + b).Есть ли способ обнаружить и удалить лишние точки, чтобы ускорить рендеринг?

Спасибо за потраченное время.

Answer 1

Ниже приведен вариант алгоритма Ramer-Douglas-Peucker для графиков 1,5d:

1. Вычисление линейного уравнения между первой и последней точкой
2. Проверьте все остальные точки, чтобы найти то, что наиболее удалено от линии
3. Если наихудшая точка находится ниже требуемого допуска, то выведите один сегмент
4. В противном случае вызовите рекурсивно с учетом двух подмассивов, используя наихудшую точку в качестве сплиттерабыть неочевидным:
   • x[a:b] - это часть массива от индекса a до индекса b (исключено)
   • x[n:] - это массив, созданный с использованием элементовx от индекса n до конца
   • x[:n] - массив, созданный с использованием первых n элементов x
   • a+b при a и b - массивы означает конкатенацию
   • x[-1] - последний элемент массива

   Пример результатов выполнения этой реализации на графике с 100 000 точек с возрастающими значениями eps можно увидеть здесь .

Answer 2

Я бы, вероятно, применил алгоритм "наименьших квадратов", чтобы получить линию наилучшего соответствия. Затем вы можете пройти через свои точки и отфильтровать последовательные точки, лежащие рядом с линией. Вам нужно только построить выбросы и точки, которые возвращают кривую к линии наилучшего соответствия.

Редактировать: Возможно, вам не нужно использовать «наименьших квадратов»; если ожидается, что ваш ввод будет колебаться вокруг "y = ax + b", как вы говорите, то это уже ваша линия наилучшего соответствия, и вы можете просто использовать ее. :)