Entfernen Sie redundante Punkte für Liniendiagramm

Question

Ich versuche, große Mengen von Punkten mit einer Bibliothek zu plotten. Die Punkte sind nach Zeit geordnet und ihre Werte können als nicht vorhersehbar angesehen werden.

Mein Problem im Moment ist, dass die bloße Anzahl der Punkte die Wiedergabe der Bibliothek zu lange dauert. Viele der Punkte sind redundant (das heißt - sie sind "auf" der gleichen Linie wie durch eine Funktion y = ax + b definiert). Gibt es eine Möglichkeit, redundante Punkte zu erkennen und zu entfernen, um das Rendering zu beschleunigen?

Vielen Dank für Ihre Zeit.

Answer 1

Das Folgende ist eine Variation des Ramer-Douglas-Peucker Algorithmus für 1.5d Graphen:

1. Berechnen Sie die Liniengleichung zwischen dem ersten und letzten Punkt
2. Überprüfen Sie alle anderen Punkte zu finden, was die entfernteste ist aus die Linie
3. Wenn der schlechteste Punkt unterhalb der Toleranz wollen Sie gibt dann ein einzelnes Segment
4. Ansonsten rekursiv ruft unter Berücksichtigung zwei Unteranordnungen, den schlechtesten Punkt als Splitter mit

In Python könnte dies

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) 

sein Der Ausgang ist [(0, 0), (30, 30), (50, 0)].

über Python Syntax für Arrays, die nicht offensichtlich sind:

• x[a:b] ist der Teil der Anordnung von Index a bis Index b (ausgeschlossen)
• x[n:] ist die Array-Elemente von unter Verwendung x aus index n zum Ende
• x[:n] ist das Array unter Verwendung erste n Elemente x
• wenn a und b Arrays sind, bedeutet Verkettungs
• x[-1] das letzte Element eines Arrays ist

Ein Beispiel für die Ergebnisse in einem Diagramm mit 100.000 Punkten mit steigenden Werten von eps diese Umsetzung ausgeführt wird, kann sein gesehen here.

Answer 2

Ich würde wahrscheinlich einen "Least Squares" -Algorithmus anwenden, um eine Linie der besten Anpassung zu erhalten. Sie können dann durch Ihre Punkte gehen und Downfilter aufeinanderfolgende Punkte, die nahe an der Linie liegen. Sie müssen nur die Ausreißer und die Punkte, die die Kurve zurück zur Linie der besten Anpassung bringen, plotten.

Bearbeiten: Sie müssen nicht "kleinste Quadrate" verwenden; Wenn Sie erwarten, dass Ihre Eingabe um "y = ax + b" schwebt, wie Sie sagen, dann ist dies bereits Ihre beste Linie und Sie können diese einfach verwenden. :)