有效地将 2D 形状放置在矩形中。如何接近它？
我在七个互联网上进行了广泛的搜索，但一无所获。最接近我需要的似乎是切削库存问题，仅在二维中（这令人失望因为维基百科没有提供任何有关如何解决该问题的说明）。另一个类似的问题是 UV 展开。那里有解决方案，但仅限于您从各种 3D 软件的附加组件中获得的解决方案。
长话短说——我想要的是这样的：给定一个已知宽度和高度的矩形，我必须找出该矩形内可以容纳多少个已知尺寸（可以随意旋转）的形状（多边形）。
例如，我可以选择一个 T 形件，并在同一个矩形中以有效的方式将其打包，从而每个矩形有 4 个形状
以及根据边界框平铺它们，在这种情况下我只能容纳 3 个
但是当然，这只是一个例子......我认为这对于解决这个特殊情况没有多大用处。我现在能想到的唯一方法要么是回溯其复杂性，要么只解决这个问题的特定情况。那么...有什么想法吗？
I've been searching far and wide on the seven internets, and have come to no avail. The closest to what I need seems to be The cutting stock problem, only in 2D (which is disappointing since Wikipedia doesn't provide any directions on how to solve that one). Another look-alike problem would be UV unwrapping. There are solutions there, but only those that you get from add-ons on various 3D software.
Cutting the long talk short - what I want is this: given a rectangle of known width and height, I have to find out how many shapes (polygons) of known sizes (which may be rotated at will) may I fit inside that rectangle.
For example, I could choose a T-shaped piece and in the same rectangle I could pack it both in an efficient way, resulting in 4 shapes per rectangle
as well as tiling them based on their bounding boxes, case in which I could only fit 3
But of course, this is only an example... and I don't think it would be much use to solving on this particular case. The only approaches I can think of right now are either like backtracking in their complexity or solve only particular cases of this problem. So... any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
有人想玩俄罗斯方块（您的问题的一个子集）吗？
这称为打包问题。如果不提前知道您可能会面对什么样的形状，那么想出一种算法来为您提供最佳答案可能会非常困难（如果不是不可能的话）。除非您的多边形是“好的”多边形（圆形、正方形、等边三角形等），否则您很可能不得不采用一种启发式方法，在大多数情况下为您提供近似的最佳解决方案。
一种通用的启发式方法（尽管根据输入多边形的形状远非最佳）是通过在多边形周围绘制一个矩形来简化问题，以便该矩形足够大以覆盖多边形。 （作为下图中的示例，我们在蓝色多边形周围绘制一个红色矩形。）
一旦我们完成然后，我们可以采用该矩形并尝试将尽可能多的矩形放入大矩形中。这将问题简化为矩形包装问题，更容易解决并更容易理解。此算法的示例位于以下链接：
一种有效的递归分区方法将相同的矩形填充到一个矩形中。
现在显然，当所讨论的多边形与矩形的形状不接近时，这种启发式方法并不是最佳的，但它确实为您提供了一个可以使用的最小基线，特别是如果您对多边形的外观不太了解的话就像（或者多边形的外观存在很大差异）。使用此算法，它将填充一个大矩形，如下所示：
这是没有中间的相同图像矩形：
对于这些 T 形多边形的情况，启发式方法并不是最好的方法（事实上，对于所提出的近似来说，这可能几乎是最坏的情况），但它对于其他类型的多边形来说效果很好。
Anybody up for a game of Tetris (a subset of your problem)?
This is known as the packing problem. Without knowing what kind of shapes you are likely to face ahead of time, it can be very difficult if not impossible to come up with an algorithm that will give you the best answer. More than likely unless your polygons are "nice" polygons (circles, squares, equilateral triangles, etc.) you will probably have to settle for a heuristic that gives you the approximate best solution most of the time.
One general heuristic (though far from optimal depending on the shape of the input polygon) would be to simplify the problem by drawing a rectangle around the polygon so that the rectangle would be just big enough to cover the polygon. (As an example in the diagram below we draw a red rectangle around a blue polygon.)
Once we have done this, we can then take that rectangle and try to fit as many of that rectangle into the large rectangle as possible. This simplfies the problem into a rectangle packing problem which is easier to solve and wrap your head around. An example of an algorithm for this is at the following link:
An Effective Recursive Partitioning Approach for the Packing of Identical Rectangles in a Rectangle.
Now obviously this heuristic is not optimal when the polygon in question is not close to being the same shape as a rectangle, but it does give you a minimum baseline to work with especially if you don't have much knowledge of what your polygon will look like (or there is high variance in what the polygon will look like). Using this algorithm, it would fill up a large rectangle like so:
Here is the same image without the intermediate rectangles:
For the case of these T-shaped polygons, the heuristic is not the best it could be (in fact it may be almost a worst case scenario for this proposed approximation), but it would work very well for other types of polygons.
通过将 t 放入一个正方形中来考虑其他答案所说的内容，但不要只是将其保留为正方形，而是将形状设置在列表中。然后使用 True 和 False 将嵌套列表填充为形状，即 T 形状的 [[True,True,True],[False,True,False]] 。然后使用函数将形状放置在网格上。为了优化结果，创建一个跟踪器，它将关注新形状中有多少 false 与先前形状的网格上已有的 true 重叠。该函数会将形状放置在重叠最多的位置。必须进行修改才能创建越来越高的优化，但这是您正在寻找的一般前提。
consider what the other answer said by placing the t's into a square, but instead of just leaving it as a square set the shapes up in a list. Then use True and False to fill the nested list as the shape i.e. [[True,True,True],[False,True,False]] for your T shape. Then use a function to place the shapes on the grid. To optimize the results, create a tracker which will pay attention to how many false in a new shape overlap with trues that are already on the grid from previous shapes. The function will place the shape in the place with the most overlaps. There will have to be modifications to create higher and higher optimizations, but that is the general premise which you are looking for.