ルート上のポイント (緯度、経度) の順序付きリストがあります。停留所（緯度、経度）の順序付きリストがあります。1000 ポイントと 20 ストップがあるとしましょう。どのポイントがルートにより関連しているかに応じて、1000 ポイントを 100 程度に減らしたいと考えています。たとえば、ターンを誘発するポイントのように。
私がこれを行うことができると思う 1 つの方法は、ストップの周りにクラスターを作成し、おそらくランダムにポイントを選択することです。しかし、それはまだ私には効果的ではないようです。私はすでに Douglas Peucker アルゴリズムを使用しています。これら以外に何かアイデアはありますか？
ポリラインを単純化するために、 Ramer–Douglas–Peuckerアルゴリズムを利用できます。
初期の複雑なポリラインが与えられると、このアルゴリズムは、指定された許容誤差でオリジナルを近似する新しいポリラインを取得しますe。新しいポリラインを定義するポイントは、元のサブセットです。
アルゴリズムはインクリメンタルで、ポリラインの端点から開始し、反復ごとに現在の近似値から最も遠い点を追加します。アルゴリズムは、残りのすべてのポイントがe現在の近似の垂直距離内にあるときに収束します。
このアルゴリズムは「分割統治」型のアプローチに基づいているため、予想される複雑さはO(n*log(n))(最悪の場合は ですがO(n^2)) です。
「ワースト ファースト」の動作のため、結果のポリラインには、鋭い角を定義する「重要な」ポイントが含まれますが、許容範囲内の平坦なセクションに沿った疑似冗長ポイントは除外されますe。