位置の異なる円を重ならずに描画するコードのアルゴリズム

Question

###前提・実現したいこと
Matlabでランダムに円を描画しようとしています。
1200x1200の画面に半径は全て20pxの円を重ならないように描画しようとしています。
現状では、図形が重なってしまい、また円になっていません。
ランダムに複数個（個数と位置がランダム）円を生成する仕様にする際にどのようにアルゴリズムを組めば良いかわからず、困っています。

###発生している問題・エラーメッセージ
実行したコード

% 等間隔ベクトルの作成
t = linspace(0,2*pi,100);

figure
cx = 200 + (rand(20, 1) .* 400); cy = 300 + (rand(20, 1) .* 400); % 中心
r = 0; % 半径


for i =0:20 
    fill(r*sin(t)+cx,r*cos(t)+cy, 'k')
    r = r+1;    
end
i=i+1;

axis([0,1200,0,1200])
axis square 

思い通りに動いているコード
20pxの半径の円を1つ画面の中心に描画するコード

% 等間隔ベクトルの作成
t = linspace(0,2*pi,100);

figure
cx = 600; cy = 600; % 中心
r = 0; % 半径


for i =0:20 
    fill(r*sin(t)+cx,r*cos(t)+cy, 'k')
    r = r+1;    
end
i=i+1;

axis([0,1200,0,1200])
axis square 

###補足情報(言語/FW/ツール等のバージョンなど)
MatlabR2017b
MacOS high Sierra

Comments

[a_saitoh]

「現状では、図形が重なってしまい、また円になっていません。」とはどういうことですか？図形が重なるのはわかりますが、「円にならない」わけはないのですが。

[a_saitoh]

今になって気が付きましたが「ランダムに」とは「ランダムな位置に」でしょうか、「（決まった位置に）ランダムな順序に」ですか？

Answer 1

（アルゴリズムのタグが付いていたので）考え方だけですが、全て同じ半径ということなので、2つの円の中心間の直線距離が半径×2 以上であれば重なることはありません。（ただし円を描く線は幅0と見做します。ちょうど2倍の場合、描画上線は重なります。それが嫌なら、半径の2倍より大きいという条件にすればOKです）

ランダムに円を描くということなので、中心座標を配列に記憶しておいて、新たな座標で円を描く前に、既に描いていた全ての円の座標と新しい座標との直線距離を求めてそれが半径の2倍以上であれば描くようにし、2倍未満ならその座標は捨てて、次の座標に進めば良いのです。
予め配列のサイズは決めておく必要がありますが、描く平面の大きさが決まれば、その中に一番多く重ならずに円を描くには、隣接する3つの円の中心を結んだ時の図形が正3角形になるように配置した時なので、計算すればサイズは決まるはずです。（まあ、多めに取っておけば大丈夫でしょう）
既にいくつ描いたかは、描く度にカウントすればいいので、そのカウントの分だけ配列をスキャンして判定すればできると思います。

MATLABは殆ど使ったことが無いので、どういうコードになるかはご自身あるいは他の方に聞いてください。

Comments

[a_saitoh]

基本、この回答でもうfinal　answerだとおもうのですが、なぜかまだ解答募集中ですね。
なお、大雑把にいうと1200×1200÷（π×20×20）*0.906=1038個が円の個数の上界だとおもいます。

[PineMatsu]

そうですね。実際のコードが欲しいのかもしれませんね。
円の一部でも良いとなるともう少し描けるのでは？(たぶんあと50個近く）
ただ、ランダムに中心座標を選ぶので、整列する確率はまずゼロなので1000個でも十分かもしれません。

Answer 2

終了条件をどう定義するつもりだったのか気になりますが、計算量を減らそうとするならアイディア勝負ですね。

80x80 の正方形をキャンパスに敷き詰め、その正方形内に１つ円を描いてみるとかどうでしょうか？正方形の中でランダムに描画することで、見た目はソコソコ乱雑に並んでいるようにみえると思います。
正方形を直径80の円に変えて敷き詰めれば、より多く並べることが出来ます。

これなら、終了条件も定義が楽だし、描画も重なることがありません。
まぁ、ランダムじゃねぇじゃんって回答ですけどね＾＾；

Answer 3

逆の発想で、

1. 1に初期化した1200x1200の配列Aを最初に用意します。
2. 配列Aから要素が1である点を1つ取ってきます。
3. 取ってきた点を、円の中心座標にしてプロットします。
4. 点から半径40の距離のインデックスに対して配列Aの要素を0にします。

以上2〜4を繰り返す。

無駄な取り出しをしないので、稠密に円を書きたい場合に有利です。

Comments

[Zuishin]

重なるかどうかの判定と塗りつぶしが面倒くさいのでは？

[Zuishin]

訂正します。重なり判定は楽ですね。半径を倍にするわけですか。

[mkgrei]

取り出して重なったら破棄するのと、置かれた円の数だけ毎度判定するのが大変かと思いまして。

配列Aの1の部分が重ならずにおける場所になります。

Answer 4

描画した円の中心座標を記録しておいて今まで描画した円と次に描画する円の中心座標の距離が 20px 以下であれば座標を計算しなおすといいでしょう。

修正

20px は 40px の間違いです。

Comments

[Zuishin]

座標の記録は配列にするのがいいと思います。
配列の使い方は http://www.cc.kyoto-su.ac.jp/~yamada/programming/array.html
二点間の距離の求め方は http://www.sousakuba.com/Programming/gs_distance_2point.html
ループの使い方は http://www.orchid.co.jp/computer/cschool/clec12.html

[退会済みユーザー]

ご回答いただきましてありがとうございました。

Answer 5

どのくらいの大きさの空間に何個の丸を描きたいのかと、どの程度の速度で「ここに新しい丸を描くと既存の丸と重なる」チェックを行わねばならないかの要件がよく分かりません。

効率が重要なら計算機科学の最近傍検索を調べた方が良いですね。

あと、画面(?)の大きさから描ける丸の個数に上限が決まりますが、上限に近い個数の丸を描きたいのなら「乱数で座標を決めて駄目ならもう一度乱数」という方式では不都合になってきますよ。

Comments

[退会済みユーザー]

ご回答いただきましてありがとうございます。1200x1200の画面に20pxの半径の円を描きたいです。重なるかどうかの判断は目で見て重なっていないくらいの要件ですが、それを数理モデルで表す方法がわからず、困っている状況です。

[a_saitoh]

だから「最近傍検索」のアルゴリズム(wikipediaに何個か挙げられています）を使えばどうですか？というはなし。重なるかどうかは「新しい円の中心の候補地と最も近い円の中心との距離≦直径」という判断基準でいけるでしょう。

[退会済みユーザー]

追加のご説明をいただきましてありがとうございました。