12

単純な（穴や自己交差のない）ポリゴンのセットがあり、それらが互いに交差していないことを確認する必要があります（1つは別のポリゴンに完全に含まれている可能性があります。それで問題ありません）。これは、あるポリゴンと他のポリゴンの頂点ごとの内部性を確認するだけで確認できます。

また、包含ツリーを決定する必要があります。これは、どのポリゴンに特定のポリゴンが含まれるかを示す一連の関係です。ポリゴンは他のポリゴンと交差できないため、含まれているポリゴンには一意のコンテナがあります。「次に大きい」もの。つまり、AにBが含まれ、BにCが含まれている場合、AはBの親であり、BはCの親であり、AをCの親とは見なしません。

質問：封じ込め関係を効率的に決定し、交差しない基準を確認するにはどうすればよいですか？それぞれの問題を個別に解決するよりも、組み合わせたアルゴリズムの方が効率的かもしれないので、これを1つの質問として尋ねます。アルゴリズムは、頂点のリストによって指定されたポリゴンのリストを入力として受け取る必要があります。ブールBを生成して、どのポリゴンも他のポリゴンと交差していないかどうかを示します。また、B = trueの場合、ポリゴンPが子Cの親であるペア（P、C）のリストを生成します。

これは宿題ではありません。これは私が取り組んでいる趣味のプロジェクトのためのものです。

4

4 に答える 4

9

まず、封じ込めをテストするためのアルゴリズムは、交差を正しくテストしません。次のような2つの長方形を想像してみてください。

    +--+
 +--+--+--+
 |  |  |  |
 +--+--+--+
    +--+

頂点は（1、2）（1,3）（4,2）（4,3）および（2,1）（3,1）（2,4）（3,4）にあります-頂点はありません任意のポリゴンの内部ですが、ポリゴンは実際には交差しています。

この種の交差をテストするには、ポリゴンのエッジのいずれかが交差しているかどうかを判断する必要があります。あなたの目的のために、エッジが交差しているが、一方のポリゴンがもう一方のポリゴン内に含まれていない場合、それらが許可されていない方法でオーバーラップしていることがわかります。

封じ込めツリーを決定する場合、そのための1つの方法は、ポリゴンを最小から最大の領域で並べ替えることです。ポリゴンが包含なしでオーバーラップしない場合、ツリー内のポリゴンの親は、リスト内でポリゴンの後に続く最初の包含ポリゴンになります。

編集：ああ、また、高速バウンディングボックスまたはバウンディングサークルオーバーラップルーチンを作成し、それを使用して、すべての線交差および頂点包含テストを実行する必要がないようにすることをお勧めします。それでも十分な速度が得られない場合は、クワッドまたはBSPツリーを構築することをお勧めします。それは物事をかなり複雑にしますが、交差点チェックの多くを完全に排除します。

于 2010-06-10T19:58:34.550 に答える
8

Shamos-HoeyアルゴリズムO(n*log(n))を適用することにより、どのポリゴンも交差していないかどうかを判断できます。Shamos-Hoeyアルゴリズムが返すものに応じて、Pjからの頂点が2つのポリゴンに対して行われるPiの内側にある場合、ポリゴンPiにはポリゴンPjが含まれます。O(n)

于 2010-06-10T20:04:16.440 に答える
4

交差点をテストするには、私のフリーウェアクリッパーライブラリを使用できます： http ：//sourceforge.net/projects/polyclipping/ 。

封じ込めをテストするには、最初に上記のように交差点を除外します。次に、Clipperを再度使用して、すべてのポリゴンを追加します-Clipper.AddPolygon（）。次に、ポリゴンに対してユニオン（ブールOR）演算を実行します-Clipper.Execute（ctUnion、solution）。Clipper.ForceAlternateOrientationプロパティがtrueの場合、Clipperは、ソリューションの外側のポリゴンを時計回りに返し、含まれているポリゴン（穴）を反時計回りに返します。次に、ポリゴンの方向をテストし、反時計回りのポリゴンの1つの頂点から他の時計回りのポリゴンに対してPointInPolygonを適用するだけです。

于 2010-06-10T22:07:07.853 に答える
1

コードについては、gpcを参照してください。

于 2010-06-10T20:13:57.423 に答える