5

パスを指定して、直線上にあるすべての頂点を削除できるように最適化します。

例：パス：

*******
*      *
*        *
***********

次のように最適化できます。

*-----*
|      \
|        \
*---------*

ただし、傾斜からの偏差を制御して、傾斜上に正確に配置する必要がないようにする必要があります。

これはどのようなアルゴリズムで実行できますか？

ありがとう

4

7 に答える 7

7

これは、パス上のポイントを繰り返し歩くだけで実行できると思います。各ポイントで、最後に遭遇した3つのポイントを追跡します。3つすべてが同一線上にある場合は、パスから中間点を削除します。これは、最初のノードから3番目のノードまで直線パスをとると中間ノードを通過するためです。ポイントがどれだけ同一線上にある必要があるかを制御する項を設定することで、偏差の量を制御できます。

これは、二重リンクリストのようなデータ構造にポイントが格納されている場合、データを簡単に渡すだけでO（n）時間で実装できます。

お役に立てれば！

于 2011-08-11T19:29:45.907 に答える
3

凸包アルゴリズム（ポリゴンがメモリにどのようにストックされているかによって異なります）を使用してから、両方の隣接ポイントの最小角度でポイントをクリーンアップする必要があります。次に、四肢のポイントのみを含むポリゴンが作成されます。

ここにあります：http： //en.wikipedia.org/wiki/Convex_hull

それらは多くの可能な実装です。それはあなたがプログラミングしている言語とあなたが遊んでいるデータに依存します。

編集：私はあなたがすでにデータにポイントを持っていることを知りませんでした..ポイントを繰り返して、あなたがいるポイント、前のポイントと次のポイントの間の角度を計算するだけです。角度が〜= 180の場合、現在のポイントを消去します。

于 2011-08-11T19:29:10.077 に答える
3

私はC++の人間ではないので、これは少し抽象化されたビューになりますが、ここに行きます...

今、あるポイントを見てみましょう。

*******
*      *
*        *<- this one, lets call it X
***********

あなたがやろうとしていることは、各ポイントが必要かどうかをゆっくりと決めることです。ポイントが有効かどうかを判断するには、他のポイントを使用する必要があります。直前と直後のポイントは次のとおりです。

*******
*      *<- A
*        *
***********<- B

AからXまでの角度がXからBまでの角度と同じである（またはエラー内で十分に正確であるとみなされる）場合、Xは不要です。

これは、凸包アルゴリズムと同じ結果にはなりません。これにより、パスの解像度が低下します。許可されたエラーが次のように大きすぎる場合、副作用が発生する可能性があります。

     *        *
    *         |
   *          |
    *    ->   |
     *        |
    *         |
   *          *

または、エラーが小さすぎる場合は、パスをまったく変更しない可能性があります。

また、凸包はパスを大幅に変更する可能性があることに注意してください。例：

  *   *            *---*
 * * * *          /     \
*   *   *   ->   *       *
*       *        |       |
*********        *-------*
于 2011-08-11T19:33:39.993 に答える
0 
set `D` to a maximum deviance of 10 degrees or so.  
set `P` to the first point.
set `Q` to the point after `P`. 
set `A` to the angle from `P` to `Q`.
while `Q` is not that last point in the list
    if the angle from `P` to `Q` is within of `A` plus or minus `D`
        remove `Q`
    else
        set `P` to `Q`
        set `A` to the angle from `P` to `Q`.
    set `Q` to the point after `P`

これは、templatetypedefの答えよりも少し複雑ですが、大きな曲線によりよく適合するという利点があります。

于 2011-08-11T21:07:06.200 に答える
0

より複雑な解決策には、画像処理の手法が含まれます。偏差を許容するハフ変換を試すことができます。パラメータ空間を「ぼかし」ることにより、偏差を含めることができます。ただし、アルゴリズムは単純ではありません。また、各ラインのポイント数が大きく異なる場合、多数のラインをどれだけうまく処理できるかわかりません。ポイントは順序付けられているので、パラメータスペースを調べて、一致したすべてのポイントを削除することができます。最初に最適な一致を選択すると、おそらく良い解決策が残されます。

于 2011-08-11T21:22:46.270 に答える
0

このページが役立つと思います：Simplyfing Polygons（そして私もこの本をお勧めします）。

于 2011-08-12T04:52:15.423 に答える
0

@templatetypedefのソリューションを、2つのベクトルC++で記述された閉じた折れ線に対して実装しました。x,yポリゴンを歩き、ポイントが前のポイントと次のポイントと同一線上にある場合は、それを削除します。

template<class T> void del_collinear_vanilla(std::vector<T> &x,
        std::vector<T> &y) {
    assert(x.size() == y.size());
    size_t i = x.size();
    size_t im1, ip1 = 0;
    do {
        i--;
        im1 = i ? i - 1 : x.size() - 1;
        if (are_collinear(x[ip1], y[ip1], x[i], y[i], x[im1], y[im1])) {
            x.erase(x.begin() + i);
            y.erase(y.begin() + i);
        }
        ip1 = i;
    } while (i != 0);
}

ここで、実装はマクロ/テンプレートに依存しare_collinear(x0,y0,x1,y1,x2,y2)ます。

ただし、場合によっては、出力に同一線上の点がいくつか残っていました。これは、アルゴリズムが失敗する入力の例です。

ここに画像の説明を入力してください

この例では、P5はP0と一致し、P4はP0とP1の同じ縦座標を持っています。すべてのセグメントを表示するために、座標を少し変更しました。アルゴリズムは、頂点がP1、P2、P3、P4の長方形のみを返す必要があります。

上記では、P6はP5およびP0と同一線上にあります。次に、P6が削除されると、P5とP0が一致し、両方ともP4およびP1と同一線上になります。

前のポイントと次のポイントと同一線上にある場合にポイントを削除する、各ポイントの単純なループでは、正しい結果が得られないことがわかります。

（この例では、P0から始めて、P6の前のポイントとP1の後のポイントと同一線上にないことがわかったとします。次に、P6に到達するまでP1、P2、...に移動します。P6は同一線上にあります。 、削除すると、ループが終了します。ただし、P0はP4およびP1と同一線上にあるため、削除する必要があります。）

オープンパスにも同じ欠陥があります。ある意味で、入力パスがそれ自体で折りたたまれていない限り、アルゴリズムは正常に機能します。

解決策は、ポイントを削除するたびに一歩下がって、前のポイントが同一線上にあるかどうかを確認することです。

template<class T> void del_collinear(std::vector<T> &x, std::vector<T> &y) {
    assert(x.size() == y.size());
    size_t target = x.size() - 1;
    size_t i = x.size() - 1;
    do {
        size_t im1 = i ? i - 1 : x.size() - 1;
        size_t ip1 = (i == x.size() - 1) ? 0 : i + 1;
        if (are_collinear(x[ip1], y[ip1], x[i], y[i], x[im1], y[im1])) {
            x.erase(x.begin() + i);
            y.erase(y.begin() + i);
            // I do not decrease i in this case, as the the previous (alread
            // processed) point may now be a collinear point that must be
            // deleted. I mod it because i may now exceed x.size()
            i = i % x.size();
            //Increment the target as well.
            target = (i + 1 + x.size()) % x.size();
        } else
            //go for the next point.
            i = i ? i - 1 : x.size() - 1;
    } while (i != target);
}
于 2014-03-02T19:20:41.460 に答える