Q&A
> 図形内に任意のサイズの円を重ならない用に任意の数敷き詰める
当然，サイズや個数の指定次第では不可能な場合もあり得るわけですが，どうするんでしょうか？
実装する処理次第では
「（実際には解が存在するのだけれども）解を見つけることができなかった」という結果を生じ得るでしょうけども，それは許容されるのでしょうか？
また，そのような場合，処理が「無理でした」という結果を返してきたときに，「本当に解が無い」のか「たまたま(?)発見できなかっただけ」か？ を区別できずとも問題はないのでしょうか？
前提・実現したいこと
pythonで取得した画像（動画の１フレーム）からほぼ楕円の形を抽出し、
その図形内に指定したサイズの円を重ならない用に任意の数敷き詰める
ということをしたいと考えてます。
イメージとしては、クッキー作りの時に広げた生地からクッキー最大何個型抜きできるか
と言った感じです。
四角形や円などのきれいな図形であれば、座標指定なり、円の方程式から領域を簡単に指定できるで、できたのですが、
歪な形の場合その領域を同定義すればよいかいいアイデアあれば教えてください。
試したこと
・任意の形の抽出
OpenCVにて、輪郭抽出をおこない、cv2.approxPolyDPにて輪郭の近似を行い、その座標を取得
・円の敷き詰め
円中心の座標をランダムで取得し、２つの円の半径以上になるような位置に円を配置し、置けなくなるまで繰り返す。
※歪というと様々な形を想像するので、タイトルを変更しました。
approxPolyDP でそれなりに領域の抽出はできると思いますが、何が不満なんでしょうか。
もう少し具体的な質問をお願いします。
> 何が不満なんでしょうか。
「領域の抽出」の部分には不満はないのでは？
その後の，「その領域の中に円を詰め込む」話が課題点と見えます．
解きたい問題はこれ
https://imagej.net/plugins/max-inscribed-circles
でしょうか。Javaの実装でした。
>fanaさん
回答ありがとうございます。円のサイズは指定して、１つずつ入れて行って、それ以上入らなければおわり、結果を図示する形で処理してます。なので、ご質問の懸念点は生じないと考えています。
欲しい数取得できなかった場合は型でくり抜いて余った生地をまたこね直して、繰り返す形になります。
＞yuki２３さん
ありがとうございます。fanaさんがフォローしていただいた通り、領域を抽出できたのですが、その領域内を指定するアイデアが浮かばなく、困っております。approxPolyDPのx,y座標群のMax,Minをとると指定領域は四角形になってしまうので、いい方法はないか考えてます。
＞quickquip
まだ全部みきれてませんが、ページの後半にあるoutputイメージです！（そこまで歪である必要はないですが）円サイズを同じにして埋められるような感じです。
回答1件
0
（処理速度とかの面でどうかはわからんけども）
distanceTransform を用いれば
円中心の座標をランダムで取得し
という作業を行う際の助けになるでしょう．
初期位置から円の位置を「動かす」ような処理を考える際にも，移動先の候補を挙げるのに役立つかもしれません．
で，方法論としては，とりあえずそこそこの位置（これは例えば上記のようなものを用いて決める）に円群を配置した後で，
円群の中心位置を最適化パラメータとた最適化処理を行う，という方向でどうでしょう？
- 円が領域からはみ出す場合，はみだし具合が多いほど大きくなるような Penalty を課す
- 他の円との距離としては「円同士が接するほどよい」的な評価（下図のような）
みたいな要素が複合した目的関数を適当に用意してやれば，そこそこ調整されませんかね？
投稿2021/06/11 02:24
編集2021/06/11 02:26総合スコア11996
あなたの回答
tips
プレビュー
