将矩形堆叠成尽可能最正方形的排列 [英] Stacking rectangles to into the most square-like arrangement possible

问题描述

• 我有N个矩形
• 所有矩形都具有相同的形状(例如2英寸宽x 1英寸高)-让我们将此尺寸称为Sw和Sh表示宽度和高度
• 我想将这些矩形放置在网格中，以使矩形完全在顶部和底部彼此相邻-就像您在电子表格中看到的一样
• 我需要的是:给出N，Sw和Sh的行数(R)和列数(C)将这些矩形堆积成尽可能最正方形的排列
• 据了解，R& C可能会提供比所需数量更多的单元(例如，如果N = 15，Sw = 1，Sh = 1，则R = 4，C = 4会产生15个矩形的16个槽"-可以.
• 如果Sw = Sh，那么我谦虚的数学技能就足够了-当它们的矩形具有不同的宽度和高度时-坦率地说，这超出了我的范围.

• I have a N rectangles
• The rectangles all have the same shape (for example 2 inches wide x 1 inch tall) - Let's refer to this size as Sw and Sh for the width and height
• I want to position these rectangles in a grid such that the rects completely on top and next to each other - like what you would see in a spreadsheet
• What I need is this: Given N, Sw, and Sh what are the number of rows (R) and columns (C) that would stack these rects into the most square-like arrangement possible
• It is understood that R & C may provide more cells than in needed (for example if N=15,Sw=1,Sh=1 then R=4,C=4 yielding 16 "slots" for 15 rectangles - that is OK.
• If Sw=Sh then my humble math skills are enough - when they rectangles have differing widths and heights - well frankly that's beyond me.

• 是的，我已经阅读了以下问题:堆叠矩形以采用尽可能少的空间，没有帮助.也不是同一个问题.这个问题是关于可能具有不同大小的矩形，在这个问题中，矩形具有相同的大小
• 是的，我在wolfram.com上搜索过，等等，没有运气
• 我没有很强的数学背景，所以我对这个问题的措辞本身可能阻止我找到答案-我尝试了与平铺，解剖，分解相关的搜索，但没有成功要么

• Yes I have read this question: Stacking rectangles to take as little space as possible and no it did not help. Also it isnt the same question. That question is about rectangles that could be of different sizes, in this question the rectangles have the same size
• Yes I have searched on wolfram.com, etc and no luck there
• I don't have a strong math background so I the way I phrasing this problem may itself be preventing me from finding the answer - I've tried related searches relating to tiling, dissecting, decomposing, and not had any success there either

the * indicates the edges of the rects
the | indicates that a cell is "filled-in"
Notice that not all R*C cells are filled in, but only and exactly N cells

IF N=1, Sw=2, Sh=1 THEN R=1, C=1

********
*||||||*
********

IF N=2, Sw=2, Sh=1 THEN R=2, C=1

********
*||||||*
********
*||||||*
********

IF N=3, Sw=2, Sh=1 THEN R=2, C=2


***************
*||||||*      *
***************
*||||||*||||||*
***************

IF N=4, Sw=2, Sh=1 THEN R=2, C=2


***************
*||||||*||||||*
***************
*||||||*||||||*
***************

IF N=5, Sw=2, Sh=1 THEN R=3, C=2


***************
*||||||*      *
***************
*||||||*||||||*
***************
*||||||*||||||*
***************

实现明天的答案

# Implementation of AaronofTomorrow's answer
# implemented in python 2.6
# reasonable output
# works in constant time

import math

def f( N, Sw, Sh ) :
    cols = math.sqrt( float(N) * float(Sh) / float(Sw) )
    cols = round(cols)
    rows = float(N) / float(cols)
    rows = math.ceil(rows)
    return (int(cols),int(rows))

另一种由Will的答案启发的实现方式(于2008-12-08更新)-这是我最后使用的实现方式

# Another implementation inspired by Will's answer
# implemented in python 2.6
# reasonable output - a bit better in yielding more squarelike grids
# works in time proportional to number of rects
#
# strategy used it to try incrementaly adding a rect.
# if the resulting rect requires more space then two
# possibilities are checked - adding a new row or adding a new col
# the one with the best aspect ratio (1:1) will be chosen 


def g( N, Sw, Sh ) :
    slope = float(Sh)/float(Sw)
    cols = 1
    rows = 1
    for i in xrange( N ) :
        num_to_fit =i+1
        allocated_cells= cols* rows
        if ( num_to_fit <= allocated_cells ) :
            pass # do nothing
        else :
            hc,wc = float(Sh * rows), float(Sw * (cols+1))
            hr,wr = float(Sh * (rows+1)), float(Sw * cols)
            thetac = math.atan( hc/wc)
            thetar = math.atan( hr/wr)
            alpha = math.pi/4.0
            difr = abs(alpha-thetar)
            difc = abs(alpha-thetac)
            if ( difr < difc ) :
                rows = rows +1
            else:
                cols = cols + 1

    return (cols,rows)

推荐答案

以威尔·迪恩(Will Dean)的反应为基础，找到他的公式的导数(相对于nCols):

Building on Will Dean's response, find the derivative of his formula (with respect to nCols):

-N * Sh/nCols + Sw

-N*Sh / nCols + Sw

然后将其设置为0并求解nCols，得到:

Then set it to 0 and solve for nCols, which gives:

nCols = sqrt(N * Sh/Sw)

nCols = sqrt(N * Sh / Sw)

围绕这一点，您应该具有最佳的列数:

Round that and you should have the optimum number of columns:

cols = round(sqrt(N * Sh/Sw))
行= ceil(N/列)

cols = round(sqrt(N * Sh / Sw))
rows = ceil(N / cols)

这篇关于将矩形堆叠成尽可能最正方形的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！