こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

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

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

投稿日時 - 2011-10-13 15:50:14

QNo.7069118

困ってます

質問者が選んだベストアンサー

添付図をご覧下さい。

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

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

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

投稿日時 - 2011-10-13 22:22:03

お礼

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

投稿日時 - 2011-10-15 17:37:59

ANo.1

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(2)

ANo.2

#1です。

A#1の添付図です。

投稿日時 - 2011-10-13 22:28:31

あなたにオススメの質問