複数の多角形を囲む四角形を求めたい

質問

こんにちは。
複数の多角形を囲む「長方形」を求めるためにはどのようにすればよろしいのでしょうか？
添付した画像のような「長方形」を求めたいのです。また面積は最小にしたいのですが、手順が思いつきません。解は一つではない場合もあるとは思いますがそれはとりあえず考えないことにしようかと思っています。
もし手法をご存じの方がいらっしゃいましたら教えていただけないでしょうか。

回答No.1

info22_ · ベストアンサー

添付図をご覧下さい。

手順１）複数の多角形（図では灰色に塗り潰した多角形「 a-b-c-d-a 」と
多角形「 e-f-g-h-i-j-e 」の2個）に紫色に塗り潰した領域を加えた
凸多角形「 1-2-3-4-5-6-1」を求める。

手順２）
凸多角形「 1-2-3-4-5-6-1」の辺「1-2」を含む長方形（図の凸多角形を含む最小面積の長方形ABCD（水色に塗り潰した青実線で囲まれた長方形）を求める。
これを各辺「2-3」,「3-4」,「4-5」,「5-6」,「6-1」について最小面積長方形を求める（各辺についての最小長方形の図を青実線で求めて描き込んでおきました。図の凸多角形の場合、合計5個出来ます）。
なお、凸多角形の頂角が鋭角の時、頂角の頂点を１つの頂点とする最小面積長方形が２つ出来ます(凸多角形の頂点1)。凸多角形の頂角が直角の時、頂角を挟む２辺を含む長方形は重なって１だけになります（図の凸多角形の頂点4が該当）。凸多角形の頂点が鈍角の時、辺の両端の頂点は最小面積長方形の頂点にはなりません(凸多角形の頂点2,3,5,6が該当)。

手順３）
各辺について求めた最小面積長方形の面積を比較してその中から最小の面積の長方形を求めれば良いでしょう。

お礼

とても詳しい説明をありがとうございます。
プログラムを組んでみてで実際に試してみようと思います。
添付していただいた図を見るとよく分かります。
また二つの図ではなく無数の点と考えた方がよかったかもしれません。
ありがとうございました !

回答No.2

info22_

#1です。

A#1の添付図です。