Supprimer les points redondants pour le tracé de ligne

Question

J'essaie de tracer de grandes quantités de points en utilisant une bibliothèque. Les points sont classés en fonction du temps et leurs valeurs peuvent être considérées comme imprévisibles.

Mon problème pour le moment est que le nombre de points rend la bibliothèque trop longue à rendre. La plupart des points sont redondants (c'est-à-dire qu'ils sont "sur" la même ligne que celle définie par une fonction y = ax + b). Existe-t-il un moyen de détecter et de supprimer les points redondants afin d'accélérer le rendu?

Nous vous remercions de votre temps.

Answer 1

Ce qui suit est une variante de l'algorithme Ramer-Douglas-Peucker pour les graphes 1.5D:

1. Calculer l'équation de la ligne entre le premier et le dernier point
2. Vérifiez tous les autres points pour trouver ce qui est le plus éloigné de la ligne
3. Si le pire moment est inférieure à la tolérance que vous voulez alors sortir un seul segment
4. Sinon, appeler récursive considérant deux sous-réseaux, en utilisant le pire moment que séparateur

En python cela pourrait être

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) 

La sortie est [(0, 0), (30, 30), (50, 0)].

A propos de la syntaxe python pour les tableaux qui peuvent être non évidente:

• x[a:b] est la partie du tableau à partir index a jusqu'à l'indice b (exclu)
• x[n:] est le tableau fait en utilisant des éléments de x de n index à la fin
• x[:n] est la matrice faite en utilisant les premiers éléments de nx
• a+b lorsque a et b sont des tableaux signifie concaténation
• x[-1] est le dernier élément d'un tableau

Un exemple des résultats de l'exécution de cette mise en œuvre sur un graphique avec 100,000 points avec les valeurs croissantes de eps peut être vu here.

Answer 2

J'appliquerais probablement un algorithme des "moindres carrés" pour obtenir une ligne de meilleur ajustement. Vous pouvez ensuite passer par vos points et les points consécutifs du downfilter qui se trouvent à proximité de la ligne. Vous avez seulement besoin de tracer les valeurs aberrantes, et les points qui ramènent la courbe à la ligne de meilleur ajustement.

Éditer: Vous n'avez pas besoin d'employer les «moindres carrés»; Si votre entrée est censée tourner autour de "y = ax + b" comme vous le dites, alors c'est déjà votre meilleur choix et vous pouvez simplement l'utiliser. :)