ネットナレッジ研究会コミュの格子状区画の指定法

今考えている問題があるのですが、
もしこれに関する研究などご存じでしたらお教えください。

2次元の表は、行と列によって格子状に区画されています。
この中の連続した任意の領域を指定する方法として、
長方形区画の組み合わせという方法を考えてみました。
例えば、凸型であれば、下の部分と上の部分の２つの組み合わせ。
凹型であれば、下の部分と上２つで合計３つの組み合わせ。
ただし、凹型については、全体をひとつの長方形で取って、
そこからへこんでいる部分を引くという方法で、
２つの組み合わせでも表現できると考えています。

分割数を最小にするような分けかたを提案するようなアルゴリズムはないでしょうか？
最終的には、3次元のマトリクスで考えたいことがあります。

時間と空間を占めるある領域を、分割することで、
構成要素を旨く抽出できないかと考えています。

コメント(5)

最初
全て
最新の40件

[1] mixiユーザー 04月30日 23:18

読み逃してました…。

で、ちょっと考えてみました。

function div_box( fig x ) {
　if (x が 1つの長方形で表せる) return 1;
　a = 1 + div_box( minus_bottom_box(x) );
　b = 1 + div_box( minus_large_box(x) );
　if (a <= b) {
　　return a;
　} else {
　　return b;
　}
}

function minus_bottom_box( fig x ) {
　x の最も最下部の辺の中で最も左側の頂点を含む
　連続する辺を底辺とする最大の長方形を y とする。
　return (x から長方形 y を除いた形状);
}

function minus_large_box( fix x ) {
　x をすべて含む最小の長方形を y とする。
　return ( 長方形y から x を除いた形状);
}

main() {
　最小分割数 = div_box(形状);
}

一応、これで分割数を最小にする形状を見つけられそうな気がする…。
ただ、これだと探索数が多くなるので、アプリオリのように、

・一回でも分割方式が求まったところで、その数より分割数が大きくなる探索はやめる

とか

・分割数が求まった形状の分割数をハッシュに入れておいて、
　すでに解析済みの形状の分割数はすぐに返す

とかする必要があるかも。

うーん、どうだしょうー。
こういうの考えるの久しぶりだったので面白かったです。

[2] mixiユーザー 05月01日 13:25

ご回答ありがとうございました！
さすがですね～。
まだきちんと理解できていないので、あとでまたコメントいたします。

[3] mixiユーザー 05月02日 00:54

こんばんは。
内容を理解いたしました（つもりです）。

「Ｔ」の形だと「最大」という部分で引っかかりそうです。
最下辺から最大の長方形を取ってしまうと、「Ｔ」の軸ごと真ん中が抜けてしまい、3つの組み合わせである、と返してきます。
じゃあ、単純に90度づつ回転させた図形4つをインプットすれば・・・という話になりそうですが、■と＋を足したような形（■の上下左右からすこし棒が出ているような形）で、かつその棒の位置が左右、上下でずれている場合には、やはり「最大」を取ってしまうと正しい数を出せません。
上のサンプルは、(aが失敗例、(b)が成功例です。

なんだか、ＴＳＰとか、そこら辺に近い話のような気がしてきたのですが、気のせいでしょうか・・・。

[4] mixiユーザー 05月03日 00:03

上に書いたアルゴリズムじゃ「分割数最小」とは限らないですね。。
この例のパターンでも分割数を最小にしようと思ったら、どういうアルゴリズムにしたらいいんだろ。。

この問題を、「領域内部と領域外部」を分ける「境界」を消化していく問題と考えてみます。

分割に使う長方形の辺の一部が

a) 領域の内部と外部を分割するようになっていれば、「境界を消化した」
b) その外側も内側も、領域の内部／領域の外部の場合、「新たな境界を増やした」

と考えると、

「ある長方形による消化した境界の長さ(L)」は、
その長方形の aの長さ - bの長さ
で表されます。

はじめの領域の境界の長さが N で、長方形を使って境界を消化していき、すべての境界を消化したら終了といった感じ。

この考え方は、いいかなーと思ってシミュレートしてみると、
「Ｔ」の形でうまくいきません。

Tの分割のしかた
a: 10 - (4 - 2) - 4 - 4 = 0
b: 10 - (7 - 1) - 4 = 0
で、b の方がいいよ、という指標とよい長方形を探す探索方法を考えないと…
と、これってそもそもはじめの問題そのものですね。

うーん。

[5] mixiユーザー 05月03日 11:58

境界線の考え方は、ここまできちんと整理できていたわけではありませんが、考えたことがありました。
僕の場合、ここで言う｢境界線の消化｣が最も多い長方形から決めていく、という方法で良さげな結果がでそうかなと。しかしながら、反例がありそうな予感がしています。

ログインすると、みんなのコメントがもっと見れるよ