Q&A
なるほど、分割線を移動させる方法はよさそうですね。
ありがとうございました！
矩形内に存在する特定の座標が1つになるように矩形をランダムな大きさに分割するアルゴリズムを教えていただきたいです。
画像で説明すると、左のような矩形内に赤座標が割り当てられた状態から、右のように矩形内に赤座標が必ず1つしか存在しないようにランダムな大きさの矩形に分割する手法を考えています。
→
私がこれまで考えた手法は、
赤座標がランダムな数内包するように矩形全体に対して分割線を引いて(下画像青色線)、
分割線より上にある赤座標が矩形内に1つのみになるように分割するという手法を考えましたが、
この手法だと、必ず矩形全体を分割する横線が存在することになってしまいます(もっとランダムに分割したいです)。
よろしくお願いいたします。
回答3件
0
質問に示されているようなグリッドで区切られた世界を考えるのだとして…
以下のような手続きを思いつきましたが，どうでしょう？
（残すと面倒そうなマスからやっつけていくことで，行き詰りを避けられるんないんじゃないか，と思うけど…どうかな？）
矩形を１個ずつ作っていきます．最初は矩形がありません．
まだいずれの矩形にも取り込まれていないマスに得点を付けます：
各マスについて，マスの４辺を見て…
- 外周に接していれば，１辺あたり +1 点（なので，４つの角のマスは初期状態で2点）
- 作られた矩形の辺に接していれば，１辺あたり +2 点
とする．
で，最も得点が高いマスから１つをランダムで選び，以下のいずれかを行う
- 選ばれたマスと，まだいずれの矩形にも含まれていない「赤座標」を１つ含む矩形をランダムに作成する
- 選ばれたマスに隣接する既存の矩形を，選ばれたマスを取り込むように拡張する
これを，全てのマスがいずれかの矩形に取り込まれるまで繰り返す．
[処理進行の例]
(1) 図の上段左：
初期状態．選択できるマスを青●で示す．最初は４つの角のいずれかが選択肢．
↓
(2) 上段中央：
左下のマスが選択されたとして，このマスと「赤座標」を１つ含む矩形を作る．
次の候補マスは２か所．
↓
(3) 上段右：
一方のマスを選択し，矩形が追加された．次の候補マスは１箇所．
↓
(4) 下段左：
候補マスは既存の矩形を拡張して取り込まれた．
↓
(5) 下段中央：
矩形作成．
↓
(6) 下段右：
矩形作成．
↓
...
投稿2021/03/12 02:26
編集2021/03/12 02:28
総合スコア11990
0
ベストアンサー
ランダムに分割する方法はわかりませんが、できあがった分割線を少し変える程度なら、次の方法はどうでしょう。
隣り合った矩形を一つにしたとき、その形が矩形なら分割線を動かせるので、この分割線を動かす。
例えば、図の一番上の2つの矩形を1つにしたとき、3マス×10マスの1つの矩形になるので、
分割線は左に1つあるいは右に2つまで動かせます(各矩形には赤座標が1つという条件があるので)
同様に、左上の矩形とその下の矩形を1つにしたとき、7マス×5マスの1つの矩形になるので
分割線は上に1つあるいは下に1つ動かせます(赤座標の条件があるのでそれ以上は動かせない)
これを応用して、分割線が十字になるような位置に分割線を移すことで大きな矩形を作れれば、
分割線を動かせるようになる場合もあります。
例えば、一番下の2つの矩形の分割線を1つ右に動かすと
左下の矩形とその上の矩形を1つにした形が矩形になるので、分割線を動かせるようになります。
これをもう少し発展させて、最初に分割線を引くときに分割線がなるべく一直線になるように分割する。
そして1つにした形が大きな矩形になる2つの矩形の分割線を動かしていく
(分割線をほとんど動かせない可能性も大いにありますが)
投稿2021/03/09 16:57
総合スコア282
0
まず，「赤座標」を１つしか含まない矩形を「赤座標」の個数だけ用意する．
（質問内の図で言えば，各矩形を赤い矩形とすれば条件を満たす）
で，以降，
「いずれかの矩形を，上下左右いずれかの方向に適当に大きくする」（もちろん，矩形同士が重なる結果を生じる操作はダメ．）という操作を，できなくなるまで繰り返す．
…という感じの手続きで達成できないでしょうか？
こういう感じになって行き詰ることはあるか……
（４つの矩形が不幸にもこんな形に成長してしまうと灰色の領域を誰も統合できない）
投稿2021/03/09 07:04
編集2021/03/10 09:50総合スコア11990
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/03/12 02:32