有效地将2D形状放置在矩形中.怎么接近它？
LWo*_*olf 10 algorithm 2d uv-mapping texture-packing
我一直在七个互联网上进行广泛搜索,但无济于事.最接近我需要的似乎是切割库存问题,仅在2D(这是令人失望的,因为维基百科没有提供如何解决该问题的任何指示).另一个看似相似的问题是UV展开.那里有解决方案,但只有那些你从各种3D软件附加组件中获得的解决方案.
缩短谈话时间 - 我想要的是:给定一个已知宽度和高度的矩形,我必须找出有多少已知尺寸的形状(多边形)(可以随意旋转)可以放在那个矩形内.
例如,我可以选择一个T形件,在同一个矩形中,我可以有效地打包它,每个矩形产生4个形状
以及根据他们的边界框平铺它们,我只能适应3的情况
但当然,这只是一个例子......我认为解决这个特殊情况并不是很有用.我现在能想到的唯一方法就是回顾它们的复杂性或只解决这个问题的特定情况.所以...任何想法？
有人想玩俄罗斯方块游戏吗（你的问题的一个子集）？
这称为打包问题。如果不提前知道您可能会面对什么样的形状，那么想出一种算法来为您提供最佳答案可能会非常困难（如果不是不可能的话）。除非您的多边形是“好的”多边形（圆形、正方形、等边三角形等），否则您很可能不得不采用一种启发式方法，在大多数情况下为您提供近似的最佳解决方案。
一种通用的启发式方法（尽管根据输入多边形的形状远非最佳）是通过在多边形周围绘制一个矩形来简化问题，以便该矩形足够大以覆盖多边形。（作为下图中的示例，我们在蓝色多边形周围绘制一个红色矩形。）
完成此操作后，我们就可以获取该矩形并尝试将尽可能多的矩形放入大矩形中。这将问题简化为矩形包装问题，更容易解决并更容易理解。以下链接提供了该算法的示例：
现在显然，当所讨论的多边形与矩形的形状不接近时，这种启发式方法并不是最佳的，但它确实为您提供了一个可以使用的最小基线，特别是如果您对多边形的外观不太了解的话就像（或者多边形的外观存在很大差异）。使用这个算法，它将填充一个大矩形，如下所示：
这是没有中间矩形的同一张图像：
对于这些 T 形多边形的情况，启发式方法并不是最好的（事实上，对于所提出的近似值来说，它可能几乎是最坏的情况），但对于其他类型的多边形来说，它会非常有效。