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

Question

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

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

Спасибо за ваше время.

Answer 1

Следующая вариация на тему алгоритма Ramer-Douglas-Peucker для 1.5D графов:

1. Compute уравнение линии между первой и последней точкой
2. Проверьте все другие точки, чтобы найти то, что является самым отдаленным от линия
3. Если худшая точка находится ниже допуска вы хотите, то выход один сегмент
4. в противном случае вызова рекурсивно рассматривают два подмассивы, используя худший момент в качестве разветвителя

В Python это может быть

def simplify(pts, eps): 
    if len(pts) < 3: 
     return pts 
    x0, y0 = pts[0] 
    x1, y1 = pts[-1] 
    m = float(y1 - y0)/float(x1 - x0) 
    q = y0 - m*x0 
    worst_err = -1 
    worst_index = -1 
    for i in xrange(1, len(pts) - 1): 
     x, y = pts[i] 
     err = abs(m*x + q - y) 
     if err > worst_err: 
      worst_err = err 
      worst_index = i 
    if worst_err < eps: 
     return [(x0, y0), (x1, y1)] 
    else: 
     first = simplify(pts[:worst_index+1], eps) 
     second = simplify(pts[worst_index:], eps) 
     return first + second[1:] 

print simplify([(0,0), (10,10), (20,20), (30,30), (50,0)], 0.1) 

Выход [(0, 0), (30, 30), (50, 0)].

О питона синтаксис для массивов, которые могут быть не очевидны:

• x[a:b] является частью массива от индекса a до индекса b (исключенного)
• x[n:] является массив с использованием элементов x из индекс n к концу
• x[:n] это массив с использованием первых n элементов x
• a+b, когда a и b массивы означает конкатенацию
• x[-1] является последним элементом массива

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

Answer 2

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

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