Pythonを用いた図形(円)の詰め込み問題

Question

pythonのmatpoltlibを用いて、図形の詰め込み問題を解こうとしております。
2次元の詰め込みで、指定したグラフの中に、高さHが最も低くなるように円を下から詰め込みたいと考えております。

下記の文献を参考に取り組んでおります。
http://www.orsj.or.jp/archive2/or63-12/or63_12_762.pdf

TypeError: only size-1 arrays can be converted to Python scalars

The above exception was the direct cause of the following exception:

該当のソースコード

from pulp import *
m = LpProblem(sense=LpMinimize)
import matplotlib.pyplot as plt

#n:並べたい円の数,r:半径,W:横幅,UB高さ
n=5
r=0.17
W=2.2
UB=2.6

x=[LpVariable("x%d" %i, lowBound=0) for i in range(n)]
y=[LpVariable("y%d" %i, lowBound=0) for i in range(n)]

u=[[LpVariable("u%d%d" %(i,j),cat=LpBinary) for j in range(n)] for i in range(n)]
v=[[LpVariable("v%d%d" %(i,j),cat=LpBinary) for j in range(n)] for i in range(n)]

H=LpVariable("H")

#モデルプロジェクトm
m += H
for i in range(n):
	for j in range(n):
		m += x[i]+r <= x[j]+W*(1-u[i][j])
		m += y[i]+r <= y[j]+UB*(1-v[i][j])
		if i < j:
			m += u[i][j]+u[j][i]+v[i][j]+v[j][i] >= 1 

for i in range(n):
	m += x[i] <= W-r
	m += y[i] <= H-r

#描写
fig = plt.figure()
ax = fig.add_subplot(111,aspect='equal')
ax.set_xlim([0,W])
ax.set_ylim([0,UB])

center,r = (x,y),r
circ = plt.Circle(center,r,fc="lightgray",ec="black") 
ax.add_patch(circ)

#グラフのタイトル
plt.title("Sectional View")

#x軸ラベル
plt.xlabel("Hole diameter")

#y軸ラベル
plt.ylabel("depth")

fig.savefig("test1.png")

試したこと

初心者でよくわからなかったので、defで標記したり、モジュールを追加したりしましたが、解決できませんでした。

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

ここにより詳細な情報を記載してください。

Answer 1

n=5だと５つの円が配置されます。ところがn=10だと同じ円が10個表示（1個に見える）になります。

Comments

[nanoseeing]

私の伝え方も悪かったのですが、こちらは回答欄ですので、質問を書かないでください。「スレッドを立て直して質問された方がよい」というのは、質問を新規投稿した方が良いという意味です。元の質問自体は解決済みになっており、ここで質問をしても有益な回答は得られないかと思います。

質問を新規投稿する際は、ヘルプをご覧ください。
https://teratail.com/help/question-tips

[KAZENOMACHI]

すみませんでした。まだ、使い方が素人なもので。

Answer 2

n=5だと５つの円が配置されます。ところがn=10だと同じ円が10個表示（1個に見える）になります。

Answer 3

エラー出力だけでなく、どの行でエラーが起きたかも明記しましょう。

実行してみたところ、

circ = plt.Circle(center,r,fc="lightgray",ec="black")

上記の行でエラーが発生していました。

エラー内容は、「サイズ1の配列のみスカラーに変換可能」と言っています。
つまり、centerやrなどの変数がサイズ1の配列ではないということです。

for文で配列の中身を取り出してやれば、描画はできるはずです。

Comments

[yoshih]

ありがとうございます。
エラー分が長かったので、しっかりと読んでおりませんでした。
今後よく見てきたいと思います。

エラーなく無事に出力することができました。

[KAZENOMACHI]

私も同じところでつまずいていますが、yoshihさんのように「for文で配列の中身を取り出してやれば、描画はできるはずです。」ということでは解決できない初心者です。どのようにしたか、具体的にご教示いただけないでしょうか？

[KAZENOMACHI]

#描写
fig = plt.figure()
ax = fig.add_subplot(111,aspect='equal')
ax.set_xlim([0,W])
ax.set_ylim([0,UB])
for i in range(n):
center,r = (x[i],y[i]),r
#center,r = (3,3+i),r
circ = plt.Circle(center,r,fc="lightgray",ec="black")
ax.add_patch(circ)
と思ったのですが、うまくいかないので、お教え願います。

[nanoseeing]

惜しいです。

コメントアウトした箇所を元に戻す（centerに直接数字を代入する）と、描写はされますよね。ということは、x[i]やy[i]はただの数値ではないのです。

print(x[i]))
print(type(x[i]))

などでxの中身を表示してみる、というのがヒントです。

[KAZENOMACHI]

x[i]やy[i]がただの数字ではなく、x0、x1などの配列番号ということがわかりました。そして、その中身の数字をとりたくて、以下にしてみたのですが、なぜかｙ[i]はすべてゼロ、x[i]は、x[i] value: 0.0
x[i] value: 0.34
x[i] value: 1.86
x[i] value: 0.17
x[i] value: 2.03
のように、円が重なり（これは元のところで半径を直径にしないといけないのですね）、詰込みにならず、また、0.5から1.75には詰め込まれないということになりました。どうして、ｙ[i]が適切な値にならないのでしょうか？

[KAZENOMACHI]

#n:並べたい円の数,r:半径,W:横幅,UB高さ
n=5
r=0.17
W=2.2
UB=2.6
の条件で、モデルで半径を直径に直し、
#モデルプロジェクトm
m += H
for i in range(n):
for j in range(n):
m += x[i]+r*2 <= x[j]+W*(1-u[i][j])
m += y[j]+r*2 <= y[j]+UB*(1-v[i][j])
if i < j:
m += u[i][j]+u[j][i]+v[i][j]+v[j][i] >= 1

for i in range(n):
m += x[i] <= W-r*2
m += y[i] <= H-r*2
m += r <= x[i]
m += r <= y[i]
m.solve()
起動しましたら、
for i in range(n):
for j in range(n):
print("x[i] value:", x[i].value())
print("y[j] value:", y[j].value())
#print(x[i])
#print(type(x[i]))
circle_n = plt.Circle((x[i].value(),y[j].value()),r)
#center,r = (3,3+k),r
#circ = plt.Circle(center,r,fc="lightgray",ec="black")
ax.add_patch(circle_n)
で、一応、5個の円が重ならないようになりましたが。どうしても左からキレイに並びません。
x[i] value: 0.51
y[j] value: 0.17
x[i] value: 0.51
y[j] value: 0.17
x[i] value: 0.51
y[j] value: 0.17
x[i] value: 0.51
y[j] value: 0.17
x[i] value: 0.51
y[j] value: 0.17
x[i] value: 0.85
y[j] value: 0.17
x[i] value: 0.85
y[j] value: 0.17
x[i] value: 0.85
y[j] value: 0.17
x[i] value: 0.85
y[j] value: 0.17
x[i] value: 0.85
y[j] value: 0.17
x[i] value: 1.52
y[j] value: 0.17
x[i] value: 1.52
y[j] value: 0.17
x[i] value: 1.52
y[j] value: 0.17
x[i] value: 1.52
y[j] value: 0.17
x[i] value: 1.52
y[j] value: 0.17
x[i] value: 0.17
y[j] value: 0.17
x[i] value: 0.17
y[j] value: 0.17
x[i] value: 0.17
y[j] value: 0.17
x[i] value: 0.17
y[j] value: 0.17
x[i] value: 0.17
y[j] value: 0.17
x[i] value: 1.86
y[j] value: 0.17
x[i] value: 1.86
y[j] value: 0.17
x[i] value: 1.86
y[j] value: 0.17
x[i] value: 1.86
y[j] value: 0.17
x[i] value: 1.86
y[j] value: 0.17

[nanoseeing]

xとyの値を取り出せたとのことで良かったです。まだ疑問があるようでしたら、スレッドを立て直して質問された方がよろしいかと思います。一応、パッと見て間違えてそうな箇所はご指摘させていただきます。

・元の質問者様にも回答させていただいたのですが、円の詰め込みは線形な制約条件で表せないと思われます。別の最適化手法が必要です。https://teratail.com/questions/328308#reply-454344

・円が左からキレイに並ぶことは保証されていません。Hを最小化することだけが目的だからです。

・x, yは円の中心座標ですか。それとも円を正方形で囲ったときの左下の座標ですか。制約条件を書く際は後者、円をプロットする際は前者の解釈になっており、混同しているように見受けられます。

・xとyの値を取り出す際に、二重ループを利用しているのはなぜでしょう。n=5で5個の円を描画するはずが、5*5=25個の円が描画されてしまいます。

[KAZENOMACHI]

・Hを最小化することが目的というのは理解しました。
・x,yは円の中心座標と思っていました。制約条件を再度考えます。
・2重ループは間違いです。5x5の円が表示されますね。
もともとはサイズの違う円（ランダム）を長方形の中に効率的に数多く配置するのはどうなるのかという問題を検討していました。