問題タブ [douglas-peucker]

Google マップで使用する GPolyline を生成するために Douglas-Peucker ポリライン単純化アルゴリズムを使用しているさまざまなプログラミング言語の例を数多く見てきました。アルゴリズムは、平面図上のポリラインで表現される場合、ポイントとライン (他の 2 つのポイントを通過する) の間の距離の計算を含みます。

これまで見てきたすべての例は、単純に x と y を緯度と経度に置き換えるという単純な方法でアルゴリズムを適用しています。ポリラインが極に近づきすぎず、180°子午線を横切らない限り、ポリラインが非常に局所化されている限り、これは許容できる結果を生成する可能性がありますが、アルゴリズムのより一般的なバージョンを実装したいと思います。

したがって、私が間違っていなければ、点から球の表面の他の2つの点を通過する円までの、球の表面上の最短の弧の長さを計算する必要があります。その中心は球の中心（地球）。

この長さを計算する式を知っている人はいますか?

前もって感謝します

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 を使用することもできますが、出力のポイント数を指定できるかどうかはわかりません。

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

これは実際には私たちの論文です。行を単純化するためにRamer-Douglas-Peuckerアルゴリズムを使用する必要があります。Androidアプリでこれを実装する方法を教えてください。

描いた線から点の文字列を取得し、合計数を減らして線を単純化する方法を知りたいだけです。以下の与えられたコードに基づくポイント？

これがメインクラスです。

EXISTING MENUをクリックすると、描画されている線が簡略化され、ポイントの少ない線または既に簡略化された線が表示されます。そのための新しいクラスを作成することを計画していますが、キャンバスに描画されている線からポイントの文字列を取得する方法がわかりません。

これは私のコードです。JAVA アプリケーションとしてコンパイルされています。作成したいのは Android アプリケーションです。ANDROID APPLICATIONとしてコンパイルしたときにエラーが発生しないように、このコードをコードに変換する方法を尋ねたいだけです。

誰かがこれを行う方法を手伝ってもらえますか? ありがとうございました

これが私のコードです：

私は、古い座標系のいくつかのマップ/領域を、Web上で表現するためのより単純な（詳細度の低い）モデルに変換する作業を行っています（jVectorMapを使用）。Douglas Peuckerアルゴリズムを正常に使用しました（ここにあるコードから：http：//www.codeproject.com/Articles/18936/AC-Implementation-of-Douglas-Peucker-Line-Expliciti）。

これは非常にうまく機能していますが、この実装では、これらの領域が互いに整列している（境界を共有している）ことを考慮していません。以下に示すように、より高い許容値を使用すると、非常に醜い結果になります。

リージョンが整列したままになるソリューションを実装することは可能ですか？

ルート上のポイント (緯度、経度) の順序付きリストがあります。停留所（緯度、経度）の順序付きリストがあります。1000 ポイントと 20 ストップがあるとしましょう。どのポイントがルートにより関連しているかに応じて、1000 ポイントを 100 程度に減らしたいと考えています。たとえば、ターンを誘発するポイントのように。

私がこれを行うことができると思う 1 つの方法は、ストップの周りにクラスターを作成し、おそらくランダムにポイントを選択することです。しかし、それはまだ私には効果的ではないようです。私はすでに Douglas Peucker アルゴリズムを使用しています。これら以外に何かアイデアはありますか？

Douglas-Peucker ライン単純化アルゴリズムの最悪の場合の時間計算量は O(n²) です。ただし、この最悪のケースを実際にトリガーする行については、次の 2 つのことが同時に「うまくいかない」必要があります。

• ほとんどの頂点が保持されるように、しきい値を非常に低く設定する必要があります
• 各再帰ステップで、現在の端点間の線からの偏差が最大の頂点は、端点の 1 つに (ユークリッド位置ではなく、線上のインデックスの点で) 近くなければなりません。(代わりに、線からの最大の偏差を持つ頂点のインデックスが現在の端点の中間に十分近い場合、アルゴリズムは深さ の再帰的なバイナリ細分割を引き起こしlog(n)、全体的な時間の複雑さは になりO(n log(n))ます。)

最初の基準は簡単にトリガーできますが (許容しきい値を 0.0 に設定するだけです)、2 番目の基準を満たす線はまだ見つかりません。

したがって、最悪のケースの動作をもたらす簡単な例の行があります(できれば、各再帰ステップで最大の偏差を持つポイントが行のエンドポイントの1つに直接接続されるという明らかな最悪のケースをトリガーするものです;しかし、他の例も大丈夫です）？

Douglas Peucker アルゴリズムについて調べました。多分私はそれを別の解決策として使用して、図面を自由に流せるようにすることができます. しかし、私の問題は、私が描いているときに、以前に描いた点も動いていることです。配列内の同じポイントのコレクション内で描画しているときに、描画された線を静止させる方法はありますか?

ここにコードがあります

現在、「Douglas Peucker」アルゴリズムを使用しています。

私の問題は、私が描いているときに、以前に描いた線も変化しており、もちろん現実的ではないことです。保存されたポイントを最小化するが、以前に描画されたポイントを変更しない、または必要に応じて「Douglas Peucker」を変更する他の方法はありませんか?

https://github.com/hgoebl/simplify-javaから削減アルゴリズムを実装しようとしています

私は彼のテスト コードを調べて、正しいロジックと思われるものを見つけようとしました。

Locationオブジェクトのリストを取得してに変換しPoint、削減アルゴリズムを実行してから、削減されたポイントをLocationオブジェクトのリストに変換しています。

問題はここにあります：

常に 2 のサイズで出力されます。明らかに何か間違ったことをしていますが、何が原因かわかりません。私の実装の問題点を特定できますか?

アプローチ 1 の失敗

アプローチ #2 も失敗します 。このアプローチも試しました。

これらのハイパーは両方とも、ポイントを最初と最後の場所に減らします。

どんなアドバイスでも大歓迎です。

解決

アドバイスのおかげで、今では完全に機能するソリューションが得られました。最終的なコードは次のとおりです。