1

複雑な多角形 (自己交差多角形) を単純な凸多角形に変換する方法を探しています。

------------------------------
 - -               
   - -
     - -
       - -
         - -
           - -
             -
           - -
         - -
       - -
     - -
    - -
   - -
   ----------------------

上の図は、2 つの多角形 (三角形) になるはずです。

ブースト ライブラリに取り組んでおり、ブースト ライブラリを使用したソリューションを探しています。

4

1 に答える 1

0

最初のポリゴンが ...xa,xb,....,xc,xd,.... (xi は頂点) で、エッジ xa,xb と xc,xd が交差しているとします。次に、....xa,xe,xd,... と xe,xb,...,xd の 2 つのポリゴンがあります。

2 つのポリゴンが交差する場合、2 つの場所 (または偶数の場所) で交差する必要があります。2 つのポリゴン ....xa,xb,...xc,xd,.... および ...xe,xf,....xg,xh,... が (xa,xb) (xe ,xf) と (xc,xd) (xg,xh) 2 つの新しい頂点 xi と xj を持つ新しいポリゴンの 2 つのセットがあります (これらのポリゴンの正確な性質を理解させます)。

次に、交差する線分のペアのリストを把握するアルゴリズムがあります。

これら 3 つの部分を組み合わせると、アルゴリズムが得られます。

于 2013-03-06T03:30:47.940 に答える