java - 什么算法可用于以最佳方式在 A1 尺寸的纸张上包装规则形状

Question

什么算法可用于以最佳方式在 A1 尺寸的纸张上包装规则形状？

标签： java

Answer 1

假设您的意思是不规则形状的包装（如图所示），最佳算法几乎完全不可行。但是，确实存在有效的近似值。这个问题有无数个重要的解决方案，不幸的是我不知道有什么方法可以找到最佳解决方案。

我需要指出，这与经过充分研究的矩形包装问题（当然是可以解决的）非常不同，因为不规则形状的侧面很少对齐，并且还必须考虑旋转。

最好的近似方法是贪婪地从最大的形状开始，以最小的形状结束，将每个形状尽可能地移动到左下角，然后再将下一个形状添加到画布上。

本文描述了一些近似解决此问题的算法： https ://pdfs.semanticscholar.org/84b0/6942a8986c6214fc88c000265c7fe7f78f52.pdf

您可能还对解决更简单的矩形打包问题的方法感兴趣： https ://codeincomplete.com/posts/bin-packing/

由于您的问题被标记为 Java，您可以使用 Area 类轻松检查不规则的交叉点。