Алгоритм распределения N прямоугольников разного размера с сохранением соотношения сторон - PullRequest
Новая
       39

Алгоритм распределения N прямоугольников разного размера с сохранением соотношения сторон

0 голосов
/ 25 мая 2020

Я хочу распределить n прямоугольников из фрейма данных с разной высотой и длиной, чтобы соотношение сторон (r_expected) общей длины (L) и общей высоты (H) было примерно L / H = 0,33. Эскиз прямоугольного распределения logi c ниже:

Чтобы найти наиболее оптимальную длину, я начинаю с предполагаемой длины (L_guess). Исходя из этого, я могу рассчитать общую высоту (H) (примечание: я опускаю подробное описание того, как это делается, поскольку это вторично) и, следовательно, отношение r, как показано здесь: 

import pandas as pd
import numpy as np

H = 0
L_guess = 18

l_cum = [2.5, 6.1, 9.9, 13.8, 18.1, 20.0] #cumulative length of rects
h = [3.5, 4.5, 6.7, 4.8, 6.8, 3.1] # height of rects
df = pd.DataFrame(list(zip(l_cum,h)), columns = ["l_cum", "h"])

tolerance = 0.01 #error tolerance for calculated ratio
r_expected = 0.33 #expected target ratio L/H


rowlist = [np.floor(i/L_guess) for i in df["l_cum"]] #check how many rects fit in L_guess by assigning a row index

for k in range(int(max(rowlist))): #check with rect has the largest height
        vals = [j for j,i in enumerate(rowlist) if i == k]
        H += max(df['h'][vals]) #add largest height to get total height

r = L_guess/H #calculated ratio out of L_guess and calculated h

Затем я обновляю L_guess, если рассчитанное отношение r не находится в пределах заданного допуска к ожидаемому отношению 0,33. ТЕПЕРЬ ЗДЕСЬ МОЯ ПРОБЛЕМА: В настоящее время я произвольно увеличиваю или уменьшаю L_guess на 15% до тех пор, пока рассчитанное соотношение не окажется в пределах заданного допуска и не будет возвращено L_guess: 

if abs(r_expected - r) <= tolerance: #if ratio difference is <= tolerance
     return L_guess #stop iterating and return length that works best

elif r < r_expected: #if L_guess too small
    L_guess += L_guess * 0.15 #increase
    findbestL(df,L_guess) #try again

else: #If L_guess too big
     L_guess -= L_guess * 0.15 #decrease
     findbestL(df,L_guess)

Есть ли способ найти подходящий шаг, не угадывая, и тем самым ускорить время расчета? Я читал о градиентном спуске, целью которого является минимизация некоторых функций, которые кажутся чем-то похожими?

...