3

いくつかのライブラリを使用して大量のポイントをプロットしようとしています。ポイントは時間順に並べられており、その値は予測できないと見なすことができます。

現時点での私の問題は、ポイントの数が非常に多いため、ライブラリのレンダリングに時間がかかりすぎることです。ポイントの多くは冗長です（つまり、関数y = ax + bで定義されたのと同じ線上にあります）。レンダリングを高速化するために冗長なポイントを検出して削除する方法はありますか？

お時間をいただきありがとうございます。

4

3 に答える 3

6

以下は、1.5d グラフのRamer-Douglas-Peuckerアルゴリズムのバリエーションです。

  1. 最初の点と最後の点の間の直線方程式を計算します
  2. 他のすべての点をチェックして、線から最も遠い点を見つけます
  3. 最悪の点が必要な許容範囲を下回っている場合は、単一のセグメントを出力します
  4. それ以外の場合は、最悪のポイントをスプリッターとして使用して、2 つのサブ配列を考慮して再帰的に呼び出します

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)]です。

明らかではないかもしれない配列のpython構文について：

  • x[a:b]aindex から indexまでの配列の一部ですb(除外)
  • x[n:]xindexnから end までの要素を使用して作成された配列です
  • x[:n]nの最初の要素を使用して作成された配列ですx
  • a+bwhen aand bare array は連結を意味します
  • x[-1]配列の最後の要素です

の値が増加する 100,000 ポイントのグラフでこの実装を実行した結果の例は、ここepsで見ることができます。

于 2011-01-16T22:05:45.143 に答える
-2

おそらく、「最小二乗」アルゴリズムを適用して、最適な線を取得します。次に、ポイントを調べて、ラインの近くにある連続するポイントをダウンフィルターできます。外れ値と、曲線を最適な線に戻す点のみをプロットする必要があります。

編集：「最小二乗法」を採用する必要はないかもしれません。あなたが言うように、入力が「y = ax + b」の周りにあると予想される場合、それはすでに最適なラインであり、それをそのまま使用できます。:)

于 2011-01-16T22:02:58.467 に答える