c# - 2つのポリゴンを交差させる方法は?

Question

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

入力: 2D の 2 つのポリゴン (A と B) [(x0, y0, x1, y2), ...]。それぞれエッジのリストとして指定されます。ポイントはのペアで表されdoubleます。それらが時計回り、反時計回り、または任意の方向に与えられているかどうかはわかりません。それらが必ずしも凸状ではないことは知っています。

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

最適化のヒント: これらのポリゴンは、部屋とフロアの境界を表します。そのため、部屋の境界は通常、同じ平面上の別のフロアに属していない限り、フロアの境界と完全に交差します (おっと!)。

この問題についてこれまでに発見したことはかなり困難であるため、誰かがすでにこれをC＃で行っており、彼らの戦略/コードを使用できるようにしてくれることを願っています。

編集：だから、私はこれを行う見込みで気絶するのは完全にチキンではないようです. これは特殊なケースであり、計算が簡単になる可能性があるため、ここで目的の出力をもう一度述べたいと思います。

出力: 最初のポリゴンからすべての交差ビットを差し引いたもの、交差ポリゴン (複数可)。2 番目のポリゴンにはあまり関心がありません。最初のポリゴンとの交差だけです。

EDIT2：私は現在、これを本当に簡単にするGPC（General Polygon Clipper）ライブラリを使用しています！

score 17 · Accepted Answer

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

ETA: しかし、実際には、これを行う最善の方法は、これを行わないことです。任意のポリゴンの交差を含まない問題にアプローチする別の方法を見つけてください。

score 14 · Accepted Answer

.NET Framework でプログラミングしている場合は、Microsoft SQL Server System CLR 型として出荷された .NET アセンブリで利用可能な SqlGeometry クラスを確認することをお勧めします。

SqlGeometry クラスはSTIntersectionメソッドを提供します

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

score 11 · Accepted Answer

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

あなたがそれを助けることができるならば、これを自分でやろうとしないでください. 代わりに、すでに存在する多くの使用可能なポリゴン交差アルゴリズムの 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/Weiler-Atherton

彼らが言うように、詳細はここに含めるには密度が高すぎますが、今後何年にもわたって Weiler-Atherton に関する参考文献を見つけることができることは間違いありません。基本的に、すべてのポイントを最終的なポリゴンに入るポイントまたは最終的なポリゴンから出るポイントに分割し、すべてのポイントからグラフを作成し、適切な方向にグラフをたどってすべてのポリゴンピースを抽出します。欲しいです。「入る」ポリゴンと「出る」ポリゴンを定義および処理する方法を変更することで、いくつかの可能なポリゴン交差 (AND、OR、XOR など) を実現できます。

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

score 3 · Accepted Answer

Clipper は、オープンソースのフリーウェアポリゴンクリッピングライブラリ (Delphi および C++ で記述) であり、まさにあなたが求めていることを実行します - http://sourceforge.net/projects/polyclipping/

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

score 3 · Accepted Answer

また、NetTopologySuite を確認したり、Sqlサーバー 2008 にインポートしてみてください。これは空間ツールです。

score 2 · Accepted Answer

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

score 2 · Accepted Answer

2

この学術論文では、これを行う方法について説明しています。

于 2011-10-05T00:25:37.417 に答える

score 2 · Accepted Answer

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

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

ナロゼー化した

score 2 · Accepted Answer

あえて他の人の GPL C++ コードを調べてみると、彼らが Inkscape でどのようにそれを行っているかを見ることができます:

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

c# - 2つのポリゴンを交差させる方法は?

9 に答える 9

Related

Reference