グラフの簡略化アルゴリズムのアドバイス

Question

私はn点の2Dグラフを取り、r点を減らす必要があります（rはnより小さい特定の数です）。たとえば、1021と1001のように、合計ポイントの数が少し異なる2つのデータセットがあり、両方のデータセットに1000ポイントを強制したいとします。私は、Lang SimplificationとDouglas-Peuckerの2つの単純化アルゴリズムを知っています。私はLangを以前のプロジェクトで少しずつ異なる要件で使用しました。

私が探していたアルゴリズムの具体的な特性は次のとおりです。

1））

2線の形状を保持しなければならない、私はポイント

の特定の数にデータセットを削減できるようにする必要があります3）は比較的高速です

この記事はさまざまなアルゴリズムのメリットについての議論です。私は、JavaまたはGroovyの実装に関するアドバイスのための2番目のメッセージを投稿します（なぜホイールを再構築するか）。

私は上記要件2を懸念しています。私は、出力ポイントの正確な数を指定できるかどうかを知るために、これらのアルゴリズムで十分な専門家ではありません。私が使ったLangの実装では、LookAhead、許容値、点の配列を入力としたので、出力のポイント数を指定する方法はわかりません。これは私の現在のニーズの重要な要件です。おそらくこれは私たちが使っていたLangの具体的な実装によるものですが、Web上のLangに関する多くの情報は見ていません。あるいは、Douglas-Peuckerを使用することもできますが、出力のポイント数を指定できるかどうかはわかりません。

私はこれらのタイプのアルゴリズムやあらゆる種類の数学の専門家ではないので、私は単純な死人型のアドバイスを探しています：上記の要件1と2をどのように満たしていますか？私は適切なソリューションのためにパフォーマンスを犠牲にします。

Answer 1

Douglas-Peuckerの簡略化については、hereとhereのC++実装と記事があります。また、結果として得られる簡略化された線の点の数を指定することができるDouglas-Peuckerの簡略化の修正版を提供します。 'Peter Taylor'が述べたように優先度キューを使用します。しかし、それはかなり遅いので、私はそれが 'が比較的速いです'を満たすかどうかわかりません。

私はLangの簡略化（およびその他のいくつかの実装）の実装を提供する予定です。現在、固定小数点数に減らすためにLangを調整する簡単な方法はありません。 がそれほど厳しい要件を満たすことができない場合： 'は、データセットをおよそ点数'に減らす必要があります。それでは、反復的アプローチを使用できます。ルックアヘッドの初期値：ポイント数/希望ポイント数を推測します。次に、希望のポイント数に近づくまで先読みをゆっくりと増加させます。

こちらがお役に立てば幸いです。

p.s .:私は何かを覚えていましたが、あなたはVisvalingam-Whyattアルゴリズムを試すこともできます。要するに：最小面積 その隣接 -resort -continueの-update面積を有する点-removeこれらの領域 -sortその直接の近隣 と各点の三角形領域-compute N点は

残るまで

Answer 2

私はダグラス・ピューッカーを非常に簡単に適応させることができると思います。リストを生成するのではなく、再帰呼び出しの構造をミラーリングするツリーを生成するように、再帰アルゴリズムを適用します。ツリーのルートは単一行近似P0-Pnになります。次のレベルは2ライン近似P0-Pm-Pnを表し、PmはP0-Pnから最も遠いP0とPnの間の点であり、次のレベル（フルの場合）は4行の近似などを表します。次に、深さに基づいて、または親線からの挿入された点の距離に基づいてツリーをトリミングすることができます。

編集：実際には、後者のアプローチをとると、ツリーを構築する必要はありません。代わりに、親ラインから挿入されたポイントの距離によって優先順位が与えられるプライオリティキューを設定します。その後、キューが終了すると、削除するポイントが示されます（または優先順位の順番に従って保持されます）。