2 つの多角形を交差させるにはどうすればよいですか?

Question

これは簡単なことではないようですが (さまざまなフォーラムでよく質問されます)、より複雑なアルゴリズムの構成要素としてこれが絶対に必要です。

入力:エッジのリストとして指定された 2D の 2 つのポリゴン (A および B) [(x0, y0, x1, y2), ...] それぞれ。点は次のペアで表されます。 doubles.それらが時計回りに与えられているのか、反時計回りに与えられているのか、それとも何らかの方向に与えられているのかはわかりません。私 する 必ずしも凸状である必要はないことに注意してください。

出力:A、B、および交差する多角形 AB を表す 3 つの多角形。どちらも空の (?) ポリゴンである可能性があります。 null.

最適化のヒント:これらの多角形は部屋と床の境界を表します。したがって、同じ平面上の別のフロアに属さない限り、部屋の境界は通常、フロアの境界と完全に交差します (ああ!)。

この問題に関して私がこれまでに見つけたものはかなり困難であるため、誰かがすでにこれをC#で実行しており、その戦略/コードを使用できるようにしてくれることを期待しています。

編集:したがって、私がこれを行うという見通しに気が遠くなるのは完全にチキンではないようです。これは特殊なケースであり、計算がより簡単になる可能性があるため、ここで目的の出力を再説明したいと思います。

出力:最初のポリゴンからすべての交差ビットを除いた交差ポリゴン (複数可)。私は 2 番目の多角形にはあまり興味がなく、最初の多角形との交点だけに興味があります。

編集2:現在使用しているのは、 GPC (汎用ポリゴンクリッパー) このライブラリを使用すると、これが本当に簡単になります。

Answer 1

あなたがすべきだと思うこと

できる限り自分でこれを実行しようとしないでください。代わりに、既に存在する多くの利用可能なポリゴン交差アルゴリズムの 1 つを使用してください。

私は、デモ コードの強度と、ほとんど/すべての奇妙なケースの処理について言及しているという事実に基づいて、次のコードベースを強く検討していました。商業的に使用する場合は、(あなた/あなたの会社が選択した) 金額を寄付する必要がありますが、この種のコードの堅牢なバージョンを入手するには、寄付する価値があります。

http://www.cs.man.ac.uk/~toby/gpc/

私が実際に行ったのは、Java2D ライブラリの一部であるポリゴン交差アルゴリズムを使用することでした。MS 独自の C# ライブラリで同様のものを見つけて使用できる可能性があります。

他にもオプションがあります。「ポリゴン クリッパー」または「ポリゴン クリッピング」を探してください。ポリゴンの交差を処理す​​る同じ基本アルゴリズムが一般的なクリッピングの場合にも使用できる傾向があるためです。

実際にポリゴン クリッピング ライブラリを作成したら、ポリゴン A からポリゴン B を減算して最初の出力を取得し、ポリゴン A と B を交差させて 2 番目の出力を取得するだけです。

どうしようもなくマゾヒスティックな人のための、自分でロールする方法

自分でアルゴリズムを作成することを検討していたとき、一般的なポリゴンの切断には Weiler-Atherton アルゴリズムが最も可能性があることがわかりました。以下を参考にさせていただきました。

http://cs1.bradley.edu/public/jcm/weileratherton.html

http://en.wikipedia.org/wiki/ワイラー-アサートン

彼らが言うように、詳細はここには載せられないほど濃密ですが、今後何年にもわたってワイラー・アサートンに関する参考文献を見つけることができることは間違いありません。基本的に、すべてのポイントを最終ポリゴンに入るポイントと最終ポリゴンから出るポイントに分割し、すべてのポイントからグラフを形成し、グラフを適切な方向に移動して、必要なすべてのポリゴン部分を抽出します。欲しい。「入口」ポリゴンと「出口」ポリゴンの定義および処理方法を変更することで、いくつかの可能なポリゴン交差 (AND、OR、XOR など) を実現できます。

実際にはかなり実装可能ですが、他の計算幾何学コードと同様に、悪魔は縮退の中にいます。

Answer 2

アーラシュ・パートウの ファストジオ ライブラリには、計算幾何学における多くの興味深いアルゴリズムの実装が含まれています。ポリゴン交差もその 1 つです。Pascal で書かれていますが、数学を実装しているだけなので、かなり読みやすいです。時計回りまたは反時計回りの順序にするには、エッジを少し前処理する必要があることに注意してください。

到着予定時刻:でも本当に、 これを行う最善の方法は、これを行わないことです. 。任意のポリゴンの交差を含まない、問題に対処する別の方法を見つけてください。

Answer 3

.NET Framework でプログラミングしている場合は、.NET アセンブリとして同梱されている SqlGeometry クラスを参照してください。 Microsoft SQL Server システムの CLR タイプ

SqlGeometry クラスが提供するのは、 ST交差点 方法

SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry intersection = g1.STIntersection(g2);

Answer 4

こちらもご覧ください。 ネットトポロジースイート あるいは、SQL Server 2008 とその空間ツールにインポートしてみてください。

Answer 5

多角形は、点 (P1、P2、...、Pn) の順序付きリストによって完全に記述されます。エッジは (P1 - P2)、(P2 - P3)、...、(Pn - P1) です。重なっている 2 つの多角形 A と B がある場合、多角形 B で囲まれた領域内にある点 An (多角形 A を記述する点のリストから) が存在します。またはその逆になります (B の点が A 内に存在します)。そのような点が見つからない場合、ポリゴンは重なりません。そのような点が見つかった場合 (つまり、Ai) 多角形 A(i-1) と A(i+1) の隣接点をチェックします。エリア外の点が見つかるか、すべての点がチェックされるまで繰り返します (その後、最初の多角形が 2 番目の多角形の中に完全に収まります)。外側の点を見つけた場合は、交差点を計算できます。ポリゴン B の対応するエッジを見つけて、再設定されたロールでそれをたどります = ここで、ポリゴン B のポイントがポリゴン A 内にあるかどうかを確認します。このようにして、重なり合うポリゴンを記述する点のリストを作成できます。必要に応じて、ポリゴンが同一であるかどうかを確認する必要があります ((P1, P2, P3) === (P2, P3, P1))。

これは単なるアイデアであり、もっと良い方法があるかもしれません。有効でテスト済みのソリューションを見つけたら、それを使用することをお勧めします...

ナライズされた

Answer 6

そのためには、ArcObjects、TopologySuite、GEOS、OGR などの GIS ツールを使用してみてください。これらのディストリビューションがすべて .net で利用できるかどうかはわかりませんが、機能はすべて同じです。

Answer 7

クリッパーは、 オープンソースのフリーウェア あなたが求めていることを正確に実行するポリゴンクリッピングライブラリ（DelphiとC++で書かれています） - http://sourceforge.net/projects/polyclipping/

私のテストでは、Clipper は GPC よりも大幅に高速であり、エラーが発生しにくいことがわかりました (詳細な比較はこちらを参照してください - http://www.angusj.com/delphi/clipper.php#features）。また、Delphi と C++ の両方のソース コードが存在しますが、Clipper ライブラリには、他の (Windows) 言語でもクリッピング関数を非常に簡単に使用できるようにするコンパイル済み DLL も含まれています。

Answer 8

これ 学術論文 これを行う方法を説明します。

Answer 9

他の人の GPL C++ コードをあえて見てみると、Inkscape でどのようにコードを実行しているかがわかります。

http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp (126行目)