11

ポリライン単純化アルゴリズムを実装しようとしています。元の記事はhttp://archive.is/Tzq2にあります。概念は簡単に思えますが、提供されているサンプル アルゴリズム (表現が不十分だと思います) の疑似コードがわかりません。記事から、基本的な考え方は

  1. 各ポイントの有効面積 (線上の 3 つの連続するポイント間の三角形によって形成される) を計算し、面積が 0 のポイントを削除します。
  2. 最小の領域から始めて、ポイントの領域をしきい値と比較し、領域がそのしきい値を下回っている場合は、ポリラインから削除します。
  3. 隣接する 2 つの点に移動し、変化に応じて面積を再計算します。
  4. しきい値を下回るすべてのポイント領域が削除されるまで、2 に戻ります。

アルゴリズムは次のとおりです (記事からそのままコピー)。

  • 各ポイントの有効面積を計算します 面積がゼロのすべてのポイントを削除し、この面積とともに別のリストに保存します
  • 繰り返す
    • 有効面積が最も少ないポイントを見つけ、それを現在のポイントと呼びます。計算された面積が、最後に削除するポイントの面積よりも小さい場合は、代わりに後者の面積を使用します。(これにより、以前に削除されたポイントを削除せずに現在のポイントを削除できないことが保証されます。)
    • 元のリストから現在のポイントを削除し、これを新しいリストに追加して、関連する領域と一緒に実行時にラインをフィルタリングできるようにします。
    • 隣接する 2 点の有効面積を再計算します (図 1b を参照)。
  • それまで
    • 元の線は、始点と終点の 2 点のみで構成されています。

「REPEAT」の下の最初のステップの「if」句と混同しています...誰か明確にできますか?

4

3 に答える 3

10

d3.jsの作成者であるFWIWMikeBostockは、このアルゴリズム（Visvalingamのアルゴリズム）の厳密なJavaScript実装を作成しました。

于 2012-08-19T14:06:02.423 に答える
8

アルゴリズムの本質は、重要度によるポイントのランキングです。ポイントの重要性は、有効面積によって概算されます。

点 A を削除してから、点 B の有効面積を再計算したとします。新しい面積は、古い面積より大きくても小さくてもかまいません。これは、A の有効領域よりも小さい場合があります。ただし、アルゴリズムは依然として B を A よりも重要であると見なします。

句の目的はif、最終的なリストでポイント B が A よりも重要であることを確認することです。それだけです。

于 2012-05-11T21:33:14.907 に答える
2

私もこれに戸惑い、戻って記事をもう一度読みましたが、ポイントを削除する場合は不要であることがわかりました-別名、固定面積しきい値で1回限りの単純化を行っている場合. JavaScript の実装はこのように動作するため、実際には「if」ステートメントは必要ありません (ただし、とにかくそれはあります)。

すべてのポイントを維持する場合は、「if」ステートメントが必要です。その場合、出力ポイントの数を制御するインタラクティブなスライダーを使用して、後でそれらをフィルタリングできるように、各ポイントで「有効領域」を保存しています。そのより大きな有効領域を格納することで、適切な順序を維持できます。

于 2015-11-13T13:24:06.727 に答える