Как упаковать шары в питоне?

Question

Я пытаюсь смоделировать случайные замкнутые сферы упаковки одинакового размера в квадрате, используя python. И сферы не должны пересекаться, но я не знаю, как это сделать

У меня так далеко

Код:

import random, math, pylab

def show_conf(L, sigma, title, fname):
    pylab.axes()
    for [x, y] in L:
        for ix in range(-1, 2):
            for iy in range(-1, 2):
                cir = pylab.Circle((x + ix, y + iy), radius=sigma,  fc='r')
                pylab.gca().add_patch(cir)
    pylab.axis('scaled')
    pylab.xlabel('eixo x')
    pylab.ylabel('eixo y')
    pylab.title(title)
    pylab.axis([0.0, 1.0, 0.0, 1.0])
    pylab.savefig(fname)
    pylab.close()

L = []
N = 8 ** 2

for i in range(N):
    posx = float(random.uniform(0, 1))
    posy = float(random.uniform(0, 1))
    L.append([posx, posy])

print L

N = 8 ** 2
eta = 0.3
sigma = math.sqrt(eta / (N * math.pi))
Q = 20
ltilde = 5*sigma

N_sqrt = int(math.sqrt(N) + 0.5)


titulo1 = '$N=$'+str(N)+', $\eta =$'+str(eta)
nome1 = 'inicial'+'_N_'+str(N) + '_eta_'+str(eta) + '.png'
show_conf(L, sigma, titulo1, nome1)

Answer 1

Это очень сложная проблема (и, вероятно, np-hard). Там должно быть много доступных ресурсов.

Прежде чем я представлю более общий подход, проверьте этот сайт википедии для обзора наиболее известных в настоящее время шаблонов упаковки для некоторых N (N кружков в квадрате).

Вам повезло, что в Python существует реализация упаковки по кругу (эвристическая!), Которая в значительной степени основана на современной теории оптимизации ( различие выпуклых функций + вогнутая выпуклая процедура).

• Используемый метод описан здесь (академическая статья и ссылка на программное обеспечение; 2016!)
• Пакет программного обеспечения используется здесь
  • Есть пример каталога с circle_packing.py (который размещен ниже вместе с выходом)
• Следующий пример также работает для кругов разных форм

Пример взят из вышеуказанного программного пакета (пример Xinyue Shen)

__author__ = 'Xinyue'
from cvxpy import *
import numpy as np
import matplotlib.pyplot as plt
import dccp

n = 10
r = np.linspace(1,5,n)

c = Variable(n,2)
constr = []
for i in range(n-1):
    for j in range(i+1,n):
        constr.append(norm(c[i,:]-c[j,:])>=r[i]+r[j])
prob = Problem(Minimize(max_entries(max_entries(abs(c),axis=1)+r)), constr)
#prob = Problem(Minimize(max_entries(normInf(c,axis=1)+r)), constr)
prob.solve(method = 'dccp', ccp_times = 1)

l = max_entries(max_entries(abs(c),axis=1)+r).value*2
pi = np.pi
ratio = pi*sum_entries(square(r)).value/square(l).value
print "ratio =", ratio
print prob.status

# plot
plt.figure(figsize=(5,5))
circ = np.linspace(0,2*pi)
x_border = [-l/2, l/2, l/2, -l/2, -l/2]
y_border = [-l/2, -l/2, l/2, l/2, -l/2]
for i in xrange(n):
    plt.plot(c[i,0].value+r[i]*np.cos(circ),c[i,1].value+r[i]*np.sin(circ),'b')
plt.plot(x_border,y_border,'g')
plt.axes().set_aspect('equal')
plt.xlim([-l/2,l/2])
plt.ylim([-l/2,l/2])
plt.show()

Выход

Модификация для вашей задачи: круги одинакового размера

Просто замените:

r = np.linspace(1,5,n)

С:

r = [1 for i in range(n)]

Выход

Интересный пример с 64 кружками (это займет некоторое время!)

Answer 2

Если вам нужна более обновленная версия решения @leopold.talirz, я предлагаю вам использовать следующее:

      from cvxpy import *
import numpy as np
import matplotlib.pyplot as plt
import dccp

n = 10
r = np.linspace(1,5,n)

c = Variable(shape=(n,2))
constr = []
for i in range(n-1):
    for j in range(i+1,n):
        constr.append(norm(c[i,:]-c[j,:])>=r[i]+r[j])
prob = Problem(Minimize(max(max(abs(c),axis=1)+r)), constr)
#prob = Problem(Minimize(max_entries(normInf(c,axis=1)+r)), constr)
prob.solve(method = 'dccp', ccp_times = 1)

l = max(max(abs(c),axis=1)+r).value*2
pi = np.pi
ratio = pi*sum(square(r)).value/square(l).value
print("ratio =", ratio)
print(prob.status)

# plot
plt.figure(figsize=(5,5))
circ = np.linspace(0,2*pi)
x_border = [-l/2, l/2, l/2, -l/2, -l/2]
y_border = [-l/2, -l/2, l/2, l/2, -l/2]
for i in range(n):
    plt.plot(c[i,0].value+r[i]*np.cos(circ),c[i,1].value+r[i]*np.sin(circ),'b')
plt.plot(x_border,y_border,'g')
plt.axes().set_aspect('equal')
plt.xlim([-l/2,l/2])
plt.ylim([-l/2,l/2])
plt.show()