3

n ポイントの 2D グラフを取得し、それを r ポイント (r は n 未満の特定の数) に減らす必要があります。たとえば、合計ポイント数がわずかに異なる 2 つのデータセット (1021 と 1001 など) があり、両方のデータセットに 1000 ポイントを強制したいとします。Lang Simplification と Douglas-Peucker の 2 つの単純化アルゴリズムを認識しています。少し異なる要件を持つ以前のプロジェクトでLangを使用しました。

私が探しているアルゴリズムの特定のプロパティは次のとおりです。

1) 線の形状を維持する必要があります

2) データセットを特定のポイント数に減らすことを許可する必要があります

3) 比較的速い

この投稿では、さまざまなアルゴリズムのメリットについて説明します。Java または Groovy での実装に関するアドバイスを求めて、2 番目のメッセージを投稿します (車輪を再発明する理由)。

上記の要件 2 が気になります。私は、出力ポイントの正確な数を指示できるかどうかを知るほど、これらのアルゴリズムの専門家ではありません。私が使用した Lang の実装は、lookAhead、tolerance、および Point の配列を入力として使用したため、出力のポイント数を指定する方法がわかりません。これは、私の現在のニーズの重要な要件です。おそらくこれは、使用した Lang の特定の実装によるものですが、Lang に関する多くの情報を Web で見たことがありません。代わりに Douglas-Peucker を使用することもできますが、出力のポイント数を指定できるかどうかはわかりません。

私はこれらのタイプのアルゴリズムやあらゆる種類の数学の専門家ではないことを付け加えておく必要があります. 適切なソリューションのためにパフォーマンスを犠牲にします。

4

2 に答える 2

2

Douglas-Pücker を非常に簡単に適応させることができると思います。リストを生成するのではなく、再帰呼び出しの構造を反映したツリーを生成するように、再帰アルゴリズムを適応させます。ツリーのルートは、単線近似 P0-Pn になります。次のレベルは、2 線近似 P0-Pm-Pn を表します。ここで、Pm は P0 と Pn の間の点で、P0-Pn から最も離れています。次のレベル (完全な場合) は、4 ライン近似などを表します。その後、深さに基づいて、または親ラインから挿入されたポイントの距離に基づいて、ツリーをトリミングできます。

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

于 2011-02-05T13:00:59.103 に答える
1

Douglas-Peuckerの単純化に関する私のC++実装と記事は、こことここにあります。また、結果の簡略化された線の点の数を指定できるようにするDouglas-Peucker簡略化の修正バージョンも提供します。「PeterTaylor」で説明されているように、優先キューを使用します。ただし、かなり遅いので、「比較的速い」要件を満たすかどうかはわかりません。

Langの単純化（および他のいくつか）の実装を提供することを計画しています。現在、Langを調整して固定小数点数に減らす簡単な方法はわかりません。より厳密でない要件で生活できる場合：'データセットをおおよそ のポイント数に減らすことができる必要があります'場合は、反復アプローチを使用できます。先読みの初期値を推測します：ポイント数/目的のポイント数。次に、目的のポイント数にほぼ達するまで、先読みをゆっくりと増やします。

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

ps：何かを思い出しました。Visvalingam-Whyattアルゴリズムを試すこともできます。要するに：-各ポイントの三角形の領域を直接隣接するものと計算します-これらの領域を並べ替えます-最小の領域を持つポイントを削除します-隣接する領域の領域を更新します-リゾート-n個のポイントが残るまで続行します

于 2011-02-07T16:12:14.397 に答える