C#で多角形同士の重なっている領域を計算する方法

Question

C#で多角形同士の重なっている領域を計算する方法

矩形同士であれば下記のような「Rectangle.Intersect」を用いることで
重なった部分の領域を求めることが出来ますが、
https://www.ipentec.com/document/csharp-rectangle-get-intersect-rectangle

polygonで描くような多角形同士が重なっている領域を計算する方法が思いつかず苦戦しております。。
どの様な方法で導くことが出来るか、お教えいただけないでしょうか。

Answer 1

Region.Intersect Method を使ってください。

Comments

[dubaisc]

すみません回答が遅くなってしまいました。ご回答ありがとうございます。
このメソッドでは矩形同士ではなく多角形についても利用できるということでしょうか？
こちら見ていると矩形にしか利用できないように見受けられまして、、

[Zuishin]

多角形の GraphicPath は作れますし、GraphicPath から Region は作れます。
https://qiita.com/Zuishin/items/0de2c21fbac5d0190c8b は私の記事ですが、ここで円形の Region と星形の Region を作っています。

https://docs.microsoft.com/ja-jp/dotnet/api/system.drawing.region.-ctor?view=netframework-4.8#System_Drawing_Region__ctor_System_Drawing_Drawing2D_GraphicsPath_
> 指定した GraphicsPath で新しい Region を初期化します。

https://docs.microsoft.com/ja-jp/dotnet/api/system.drawing.drawing2d.graphicspath.-ctor?view=netframework-4.8#System_Drawing_Drawing2D_GraphicsPath__ctor_System_Drawing_Point___System_Byte___
> GraphicsPath と PathPointType を指定して、Point クラスの新しいインスタンスを初期化します。

[dubaisc]

こちらの内容で対応してみたところ上手くいくことが出来ました！
ありがとうございました。ベストアンサーとさせていただきました。
とても遅くなってしまいすみませんでした。。

Answer 2

Polygon.Intersectのようなメソッドは標準にはないので、自分でアルゴリズムを作る必要があります。

直接的な回答ではないため恐縮ですが、

• "polygon intersection algorithm"で調べてみて、アルゴリズムを理解し自作する
• 誰かが作ったそのアルゴリズムの実装サンプルを読んで流用する

辺りから始める良いかと。

同等の疑問を持たれる方がSOにもいたので貼っておきます。
https://stackoverflow.com/questions/1526352/how-to-intersect-two-polygons/1526456

あとは2006年の古いソースですが、サンプルも貼っておきます。
（考え方辺りは参考になるかと思います）
https://www.codeproject.com/Articles/15573/2D-Polygon-Collision-Detection

Comments

[dubaisc]

すみません回答が遅くなってしまいました。ご回答ありがとうございます。
やはり自作しなければ実現出来なさそうですね。
SOについてもご紹介ありがとうございます。こちら参考にさせていただきます。

Answer 3

多角形は頂点と頂点を結ぶ線で分割することによって三角形の集まりにできます。

両方の多角形を、それぞれ三角形の集まりにして、三角形どおしの重なり部分を求め、最後にそれらを集めれば多角形どうしの重なっている部分が求まります。

・２つの三角形の辺どうしで交差しているかどうかを調べて、交差していれば２つの三角形に重なっている部分があります。
・辺同士の交差は無いが、一方の三角形の中心が、もう一方の三角形の内部にあるなら、２つの三角形に重なっている部分が有ります。（小さいほうの三角形全体が、重なっている部分になります）

Comments

[dubaisc]

すみません回答が遅くなってしまいました。ご回答ありがとうございます。
三角形に分解して重なりを求める方法、参考にさせていただきます。
ただ凹となっている多角形においては三角形への分割が少々難しそうですね、、一工夫がいりそうです。