11

私はこの小さな問題に悩まされており、これを解決するためのアルゴリズムはすべてのケースに当てはまるわけではありません。これを解決する方法を知っている人はいますか？

ポリゴンの例を次に示します。

例 http://img148.imageshack.us/img148/8804/poly.png

正式な説明

多角形を定義する CW 順の点のリストがあります。ポイントが切断ポイントであるかどうかをクエリすることもできます。is_cut(p)ここpで、 は特定のポイントです。次に、この「カット」によって生じる新しいポリゴンを計算します。

アルゴリズムはこれを行う必要があります。

入力：{a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}

出力: {a, c1, c2}, {b, c4, c3, f, c2, c1}, {d, c6, c5},{e, c3, c4, c, c5, c6}

ここに私の現在のアルゴリズム：

follow your points, CW
if the point is a cut point
-> go back trough the list looking for cut points
--- if next cut point is connected to the current cut point 
    and not part of the current poly, follow it
--- else keep searching
else
-> continue until you hit your starting point.
that's a poly
do this for every non-cut-point

cまたはで開始した場合、このアルゴリズムは成立しませんf。

4

4 に答える 4

5

最初に、元のポリゴンの内部に属する切断線のセグメントを計算する必要があります。これは古典的な問題であり、その解決策は簡単です。ポイントc1, c2, c3 ... c6が正確にこの順序で線に沿って配置されている場合、セグメントc1-c2などc3-c4は常にポリゴン内部 (*) に属します。

これで、ポリゴンをカットするための単純な再帰アルゴリズムを構築できます。大きな入力配列 {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2} を指定すると、任意のポリゴン ポイントから開始しbます。配列に追加しresultます。入力配列を順方向にトラバースします。遭遇したら

  • 通常のポリゴン ノードを配列にプッシュしresultます。
  • ckkが奇数であるノードを探し、c(k+1)その位置からトラバースし続けます。
  • ckk偶数であるノードを探し、c(k-1)その位置にジャンプし、それでも前方にトラバースし続けます。

最後の 2 つのケースでは、これらのノードを見つけた順序でresult配列に追加します。ckset に node を追加cutし、別の node (c(k+1)またはc(k-1)、取得した方) をグローバル set に追加しますdone。

最後の要素を超える必要がある場合は、入力配列の最初の要素に回路を移動します。

遅かれ早かれ、トラバースしていた最初のノードに遭遇します。result配列には、カットしたポリゴンがあります。それを覚えて。cutセットに属し、グローバル セットに属していない各ノードの位置から開始して、手順を再帰的に繰り返しますdone。

それが私が見た解決策です。しかし、これは計算幾何学であるため、見た目よりも少し複雑になる可能性があります。

この例では、次から開始しbます。

  1. done={}、 から開始しbます。最初のパスの後result=[b,c4,c3,f,c2,c1]、 , cut={c4,c2}, done={c3,c1};が得られます。c4andc2ノードに再帰します。
  2. done={c3;c1}c4、 (1 からの再帰) から開始します。このパスの後result=[c4,c,c5,c6,e,c3,c4]、 , cut={c5,c3}, done+={c6,c4};が得られます。に再帰しc5ます。
  3. done={c3;c1;c4;c6}c2、 (1 からの再帰) から開始します。このパスの後result=[c2,a,c1]、 , cut={c1}, done+={c2};が得られます。セットc1内にあるため、 に再帰しないでください。done
  4. done={c3;c1;c4;c6;c2}c5、 (2 からの再帰) から開始します。このパスの後result=[c5,d,c6]、 , cut={c5}, done+={c6};が得られます。セットc5内にあるため、 に再帰しないでください。done

出来上がり - 必要な 4 つのポリゴンが得られます。

(*) 線のより「数学的」な表現が必要であることに注意してください。たとえば、ポリゴンの頂点の 1 つがライン上にある場合、頂点を 2 倍にする必要があります。つまり、cポイントが少し右側にあり、赤いライン上にある場合、ラインには[c1, c2, c3, c, c, c6]ポイントがあり、ポリゴン配列は次のようになります。する[a, c1, b, c, c, c, d, c6, e, c3, f, c2]。

場合によっては (この例ではありません)、 などの「空の」ポリゴンがカットされることがあり[a, a, a]ます。それらが必要ない場合は、後の段階で削除できます。とにかく、膨大な数のボーダーケースを持つ計算幾何学です。1つの回答にすべてを含めることはできません...

于 2009-11-21T14:02:56.437 に答える
3

Weiler Athertonクリッピングを適用することもできますが(事実上、Pavel が提案していること)、大きな注意点があります。

浮動小数点エラーが原因で、W/A クリッピング アルゴリズムをうまく機能させるのは非常に困難です。クリッピング ラインが頂点を通過する場合や、正確にポリゴンのエッジに沿っている場合、アルゴリズムはどの「パス」について混乱する可能性があります。 」 従うべきポリゴンの周囲にあると、間違った結果が出力されます。

于 2009-11-21T14:24:22.460 に答える
0

実装が最も簡単なのはSutherland-Hodgmanです。それに関する1つの問題は、ラインの片側のポリゴンを接続するゼロエリアスライバーがほとんど残っていないことです。あなたの例では、これはあなたに次のようなものを与えるでしょう：

{a c2 c3 e c6 c5 cc4c1}および{bc1c2 f c3 c6 d c5 c4}

これを使用するか、それらを必要な部分に分割する方法を理解できれば、実際のクリッピングを実行するコードは可能な限り単純であることがわかります。

実装には、2つのスタックとポリゴンの頂点を1回通過する必要があります。各頂点で、前の頂点から線を越えたかどうかを確認します。もしそうなら、交差点を計算し、それをスタックの1つにプッシュします。次に、新しい頂点をスタックの1つにプッシュします。本当に簡単です。

于 2009-12-02T17:13:51.567 に答える
0

1 面を見つける各ポイントは

カットされていない 1 つのポン (たとえば a) を選択し、それが左側にあるように設定します (実際には測定されません)。

カット上のポイントを通過すると、到達したポイントの側が変化します。したがって、左/右のポイントが見つかります。

問題は、ポイントの順序が事前に定義されている必要があることも考慮する必要があることです。(例えば時計回り)

2 cx の各中央部から開始し、時計回りと反時計回りに 1 回ずつ進みます。

ポリゴンごとに、中央部を一方向に 1 回だけヒットします。

「オーバーフロー」した場合、それは外側の多項式に到達したことを意味します。polgon 上にある c0 と cmax を定義し、以下を持っていれば、この問題を解決できるかもしれません。

input =  {a, c1, c0 ,c1, b, c4, c, c5, d, c6, c7, c6, e, c3, f, c2}
于 2009-11-21T14:55:01.950 に答える