4

次の問題があります。

サイズの異なるランダムな数の円が配置された大きな領域があります。ランダムな半径の新しい円がランダムな場所に挿入された場合、他の円と重ならないように、その近くの位置を見つけたいと思います。円が近くにある場合に最適です。

円の数とサイズには制限がありますが、ランダムです。領域は非常に大きくなるため（おそらく2500x2500）、ここで提案されているピクセルの配列は問題外です。同じ質問に答えた人は、セルが円のサイズであるグリッドを提案しました。それは私の問題を解決し、可能な限り最大の円のサイズのセルを使用しますが、円をできるだけ近くに保ちたいので、私のニーズを完全に満たすことはできません。

非常に基本的なアプローチは、新しい円の配置時に衝突を検出し、衝突する円から遠ざけることです。その後、衝突を再度確認し、プロセスを繰り返します。これは明らかにあまりエレガントではなく、無限ループになりがちです（想像以上に頻繁に）。

目標は、新しく挿入された円が他の人と重ならないように、可能な限り最も近い位置を見つけることです。

PD
非常に良いことですが、私の主な目的ではなく、別の問題は、円を1つだけ再配置するのではなく、必要な数だけ円を再配置することです。移動する円の数よりも距離を優先します。つまり、元の位置から非常に遠くに移動するには、多くの円を1つより少しだけ移動することをお勧めします。

4

3 に答える 3

5

次のようにします。x、yのグリッドを定義し、グリッドについて、すべての円から円までの半径を引いた最小距離を計算します。結果のマップで、Xより明るいピクセルを選択できます。これは、半径Xの円をオーバーラップせずに配置できることを意味します。これは、結果のマップを示すコードと画像です。高速にしたい場合は、低解像度バージョンのマップを使用できます。

import numpy as np,numpy.random
import matplotlib.pyplot as plt,matplotlib,scipy.optimize

maxx=2500
maxy=2500
maxrad=60 #max radius of the circle
ncirc=100 # number of circles
np.random.seed(1)

#define centers of circles
xc,yc=np.random.uniform(0,maxx,ncirc),np.random.uniform(0,maxy,ncirc)
rads=np.random.uniform(0,maxrad,ncirc)
#define circle radii

xgrid,ygrid=np.mgrid[0:maxx,0:maxy]
im=xgrid*0+np.inf

for i in range(ncirc):
    im = np.minimum(im, ((xgrid - xc[i])**2 + (ygrid - yc[i])**2)**.5 - rads[i])
# im now stores the minimum radii of the circles which can 
# be placed at a given position without overlap

#plotting 
fig=plt.figure(1)
plt.clf()
plt.imshow(im.T,extent=(0, maxx, 0, maxy))
plt.colorbar()
ax = plt.gca()
for i in range(ncirc):
     ax.add_patch(matplotlib.patches.Circle((xc[i], yc[i]), rads[i],
          facecolor='none', edgecolor='red'))
plt.xlim(0, maxx)
plt.ylim(0, maxy)
plt.draw()

重なり合うことなく配置できる円の最小半径のマップ

マップはボロノイ図のように見えますが、それを利用できるかどうかは不明です。

更新：いくつかの考えの後、多数のサークルで機能する可能性のあるより高速なソリューションがあります。まず、エリアのグリッドを作成します（たとえば、2500x2500）。円の内側にあるすべてのピクセルを1で塗りつぶし、それ以外はすべてゼロで塗りつぶします。次に、配置する円の必要な半径を持つ円形カーネルでこのマップを畳み込む必要があります。結果のマップは、ピクセルの配置に使用できるピクセルで0を持っている必要があります。この方法の利点は、非常に大きなグリッドと数の円に対して機能し、畳み込みをfftで簡単に実行できることです。

これは、最初のマスクと、半径128ピクセルの円形カーネルとの畳み込み後のマスクを示す図です。右側のマスクのすべてのゼロピクセルは、半径128の新しい円の可能な位置です。

マスク

于 2012-06-13T01:29:21.063 に答える
2

動的グリッドを試してください。ここでは、最大の円サイズから始めて、最終的な位置に配置した後、円の各エッジに線を描画します。これで、グリッドはさまざまなサイズのボックスで構成されます。新しい円の境界ボックスに合うボックスを見つけて配置し、小さいボックスを定義する線を描画するだけです。すべてのサークルを配置するまで続けます。

正方形の領域内の角の位置にいつでも円を配置できるため、線を描画するときは、最初に2本の線を描画するだけで済み、次に配置後は常に最大スペースを開いたままにします。

于 2012-06-12T23:02:42.380 に答える
2

あなたの質問は、反発力と引力の賢明なバランスを備え た力ベースのレイアウトアルゴリズムに基づく解決策を提案しています。この答えはあなたが使うかもしれない図書館を指しています、グーグルは私が期待するあなたのために他のものを見つけるでしょう。

于 2012-06-13T15:51:18.367 に答える