将 2D 框分类为更大的框，以最有效和完整的方式填充

Question

背景：
你好，所以我一直在研究这个功能，但我绊倒了。最终，我想要完成的是拥有一个应用程序，用户可以在其中输入较大的框，还可以输入较小框的列表。（顺便说一句，都是二维的）。然后程序会对此进行处理，并尝试用较小的盒子尽可能完全地填充较大的盒子。对于那些好奇的人，这是一个剧院平台应用程序。

代码内容：
我这里有这个函数，它接受 "box"，这是一个由用户创建的大盒子 table，和 "platforms"，它是一个 table 小盒子。正如在评论中看到的那样，我已经写了如果一个平台完全适合一个盒子的部分，那么它就会这样做。然后它会减少该平台给定尺寸的数量，并将该框标记为已填充。

问题：
我无法弄清楚的问题是如何以最有效的方式以编程方式将两个平台放入一个更大的盒子中。我考虑过使用盒子的 x 侧并用一组给定平台的 x 值填充它，然后在该组中插入具有相同 x 值但具有不同 y 值的不同平台，但那里存在几个问题。
关于从这里我应该去哪里的任何指示？

userInterfaceCall()
    squares[#squares+1] = {x1=x, y1=y, x2 = nil, y2 = nil, f=false}
    --x1,y1 and x2,y2 are coordinates for two opposite points in a square
    --f is the boolean that is marked true when a square (box) is completely filled
end

platforms[1] = {x=4, y=4, q=2} --example user data
platforms[2] = {x=4, y=6, q=2} --x and y are platform dimensions
platforms[3] = {x=6, y=2, q=1} --q is quantity
platforms[4] = {x=8, y=4, q=1} 

process(squares,platforms) --this is called by a UI element

function process(box,platforms)
for i,box in ipairs(box) do                     --for every square do
    if box.f == false then                      --if the box already has a given platform, don't do shit
        for i,platform in ipairs(platforms) do  --for each platform for each box
            boxX = math.abs(box.x1-box.x2)/scale  --Ignore this, this is working with scaling from-
            boxY = math.abs(box.y1-box.y2)/scale  --pixel size to feet to compare to list of platforms
            if boxX == platform.x and boxY == platform.y and platform.q > 0 then        --Test if any platform fits directly in the box
                placements[#placements+1] = {x1 = box.x1, y1 = box.y1, x2 = box.x2, y2 = box.y2, s = ''} --Creates a new placement of a given platform, which is then drawn
                platform.q = platform.q - 1 --we reduce the quantity, cause we used one
                box.f = true --yes, we just filled the box completely
            elseif boxY == platform.x and boxX == platform.y and platform.q > 0 then    --Test for switched x and y
                placements[#placements+1] = {x1 = box.x1, y1 = box.y1, x2 = box.x2, y2 = box.y2, s = ''}
                platform.q = platform.q - 1
                box.f = true
            elseif
                --put multiple platforms in one box, Help
            else
                setPrompt('Could not find for box: '..boxX..','..boxY)
            end
        end
    end
end

结束

Answer 1

您找到了 Multi-dimensional Knapsack Problem 的一个变体，它被认为是 NP 完全的。所以不，没有简单的 "best" 解决方案，但是，已经发现许多策略可以在可接受的时间内产生可接受的结果。请参阅链接文章以获取更多说明。

Answer 2

对于其他正在查看此内容的人，请阅读此处：http://codeincomplete.com/posts/2011/5/7/bin_packing/

这是一个有效的 javascript/CSS 解决方案。

将 2D 框分类为更大的框，以最有效和完整的方式填充

Sorting 2D boxes into larger boxes to fill in the most efficient and complete manner

sorting

lua

2d

love2d