（OPENCV）複数の円を重ならずに描画させたい

Question

前提・実現したいこと

プログラミング初心者で勉強中です。

現在opencvを使用し、numpyでランダムなxとyを抽出し、200×200の画面に中心座標（x,y）の半径10の円をランダム配置で10個生成し、画像表示させるプログラミングを学習しています。
その時円が重なることがあるので、「重複しないよう描画させる」のが目標です。

調べると円と円の衝突判定があり、これを用いて当たり判定し当たっていなければ描画、当たりなら描画予定の円の座標を削除するプログラミングにしようと考えています。

過去質問で恐らく類似質問を見つけ、このベストアンサーと同じ考え方でした。
https://teratail.com/questions/107389
しかし、その考え方のコード記述方法の実力が私にありませんでした。

→ppaul様の回答よりリストを使用することで可能だと考えています。

発生している問題・エラーメッセージ

そこでぶつかっている点が１点あります。（私の実力不足なのですが、、）
・当たり判定で使用する過去に描画したそれぞれの円の中心座標の記述方法が分かりません。

コードにするとどうなるのか（コードでなくても何かヒント）を教えて頂けると幸いです。
また、将来的に画像解析もしていこうと考えておりopencv以外にもおススメのライブラリなどあれば教えて欲しいです。

該当のソースコード

現在重複ありのソースコード

import cv2  
import numpy as np 
import random 

img=np.zeros((200, 200, 3), np.uint8)

for i in range(10): 
    x=int(random.uniform(10,190)) 
    y=int(random.uniform(10,190)) 
    cv2.circle(img, ((x, y), 10), (255, 255, 0), -1)

cv2.imshow("random",img) 
cv2.imwrite("random.png",img) 

cv2.waitKey(0)
cv2.destroyAllWindows()

試したこと・やりたいこと

円の当たり判定と繰り返し

i=0
while i<10:
    x=int(random.uniform(10,190))
    y=int(random.uniform(10,190))

    if ((#過去のx座標 - x) * (#過去のx座標 - x) + (#過去のy座標 - y) * (#過去のy座標 - y)) > 20 * 20:
　　　　　cv2.circle(img, (x, y), 10, (255, 255, 0), -1)

上記で考えています。

＃過去の座標部分の記述方法が知りたいです。

補足情報（FW/ツールのバージョンなど）

Python3.9
opencv_version = "4.5.3.56"
OS＝Microsoft Windows [Version 10.0]

Answer 1

不真面目な(?)方法かもしれませんが，判定が画素単位で良いならば，マスク画像を作る手があります．

つまり，各画素について「その画素位置を新たな円の中心位置として選んでよいか否か」という情報を持つための，（本当に円を描画したい画像と同じサイズの）バッファを用意してやれば，
「新しい円を中心座標を(x,y)として追加しても良いだろうか？」という判定は，このバッファの(x,y)の中身をチェックすれば良いわけです．

例えば以下のようになりますかね：

1. 描画対象画像Iと同じサイズのバッファBを用意し，全0で初期化しておく
2. 新しい円の中心位置の候補(x,y)を乱数で作る
3. B(x,y)をチェック．値が0でない場合は2に戻る
4. 画像Iに円を描画すると共に，バッファBにも2倍の径で塗りつぶし円を描画する（もちろん塗りつぶす画素値は非0とする）
5. 円の個数が所望の個数になってないなら2に戻る

Comments

[infinite]

fana様
ご回答ありがとうございます。
判定条件で私が最初に考えた方法に似ています。プログラムを作る前に衝突判定を目にして、後回しにしてしまいました。
衝突判定とこの方法が完成したらどちらが描画スピード早いのか確認してみます。(まだまだ勉強しなければいけませんが)

[fana]

今の条件（200x200の領域内に半径10の円を10個）であれば素朴な方法でも十分でしょうけど，
厳しい条件になってくると相応のアルゴリズムが要るのかもしれません．（図形充填問題とか何とかいう世界？）

あと，参考になるかわかりませんが，
昔，「円を複数置きたいです」的な話で「ポアソンディスクサンプリング」という方法を目にしたことがあります．
（アルゴリズムの内容はさっぱり覚えてないですが，それで迷路を作って楽しかった記憶がある）

[fana]

与太話：

円の中心座標が整数であれば，この問題は，
【40000(=200x200)個の点群の中から，条件（全ての点の間の距離が20以上はなれていること）を満たす10個の点の組み合わせを見つける】
と言い表すことができる．
↓
必ずしも40000個でやらずともいいのではないか？
例えば，最初に適当に乱数でN個(30個とか50個とか100個とかその程度）の点を作り，この中から組み合わせを見つけるのでも目的は達成できるハズ．
（処理中に，このN個では条件に合う組み合わせが作れないとわかったならば，N個の点を作り直せばいい）

1. 最初にN個の点を乱数で作る（この時点で "残りの点群の個数"＝N個）
2. 残りの点群の中から，てきとーに点を１個選ぶ．（≒円の中心として採用）
3. 残りの点群から，今選んだ点からの距離が20未満のものを全て除去する．
4. 選んだ点の個数が10個になったならば完了．
5. 残りの点の個数が明らかに足りなくなったならば1に戻ってやりなおす．そうでないなら2へ．

みたいな．

[infinite]

fana様
図形充填問題は目にしていました。詰め込んでいくのは今回のが完成後個数を限定せずにやってみたいと思います。

「ポアソンディスクサンプリング」については初見で、一番上に出てきた論文を読んでみて面白そうでした！また点同士が一定の距離を保つので、円を重ならずに配置もできそうですね。今はランダムでやってますが、テクスチャを使用して密度が不均一なものなど頭の中のイメージをプログラミングに移せるようたくさん勉強していきます！

Answer 2

円を描画してその中心座標を覚えないでいるのでは無理です。
したがって、円を描画したときに、何かの方法でその中心座標を覚えておく必要があります。
そのために、普通はリストを使います。

公式ドキュメント 3.1.3. リスト型 (list)

Comments

[infinite]

ppaul様
ご回答ありがとうございます。
if文の当たり判定で真ならリストへ中心座標（要素）を追加していき、当たり判定の計算時にリストから座標（要素）を出してくるイメージですね。

もし差し支えなければでかまいませんリストについて追加質問があります。
テストとして
kx=[]
をfor文の前に作り
for文中に
kx.append(x)
としてリストに追加しようとappendしようとしてもできませんでした。
考え方等間違っている箇所はどこになるでしょうか。

今一度リストの使い方を勉強してきます。

[ppaul]

その方法で出来るはずですが、何がうまくいかなかったのでしょうか。
質問を編集してソースコードと、もしエラーが起きているならエラーメッセージを載せてください。

[infinite]

ppaul様
大変申し訳ございません。
上記については、numpyのarray（配列）はappendできないみたいだったので
kx1 = np.array([])
kx = np.append(kx1, x)
に変換したらエラーは消えました。ご迷惑をおかけいたしました。
新たに問題ができたので質問を編集します。

[ppaul]

リンクを貼ってリストの使い方を説明したのですが、なぜnumpyの話になっているのでしょう。
絆創膏の入手方法を聞かれてドラッグストアを教えたら、ホームセンターでガムテープを買ってきたけれどうまく使えません、と聞き返されたような印象を受けました。

[infinite]

ppaul様
ご不快な思いをさせてしまい大変申し訳ございませんでした。
再度、上記のappendでリストが出来上がり10個のリスト内要素(x座標)が取れました。

リンク先のリストも確認したのですが、昨夜はなかなか上手くいかずネットで調べて以下のサイトの3.5pythonのappendとnumpyのarrayを参考にしたら動きました。
https://www.headboost.jp/python-append/#35_Pythonappendnumpyarray

現在はリストへappend出来ております。(私の0:20の方法で)
上手くいかなかった理由は、kxを別のプログラムで使用していたからだと考えています。kx1にしてリストが出来ました。

ppaul様大変申し訳ございませんでした。

[ppaul]

別に不快な思いをしたわけではないので、気にしないでください。
ただ、世の中にはアドバイスを聞かずに迷路とか泥沼にはまり込んでいくというタイプの人がいて、そういう人にアドバイスをしても大抵は無駄です。infiniteさんがそういうタイプでないので安心しました。