可能重复：
如何将正方形打包成圆形？
我有一个问题，我需要在一个圆圈内放置一堆不同大小的矩形。所有矩形都必须适合圆圈，不能相互重叠，也不能溢出圆圈。
假设矩形可以放在圆圈内，如何开发一种算法将它们分布在圆圈内？
我能想到的就是一遍又一遍地随机分布矩形并测试是否满足条件（蛮力）。
问问题
754 次
2 回答
3
这是一个经典的约束问题，蛮力是解决问题的一种方法，但还有其他方法可以更好地使用启发式算法等方法来帮助引导算法找到解决方案。您将不得不在 Google Scholar 之类的东西上查找一些约束规划和装箱论文，以获得更好的算法。
维基百科有一个很好的概述： http ://en.wikipedia.org/wiki/Packing_problem
于 2012-10-04T13:20:36.073 回答
1
正如其他人所提到的，最佳解决方案（例如最小面积或均匀分布）可能是 NP 难的。不过，根据您的需要，有一些很棒的算法可以将不同大小的矩形打包到其他矩形中。例如：用于构建 CSS Sprites 的快速优化矩形打包算法：
本文介绍了一种快速算法，可将一系列不同宽度和高度的矩形打包成一个单独的封闭矩形，没有重叠，并且可以最大限度地减少封闭矩形中浪费的空间量。[...] 一步一步地展示了算法如何到达最佳封闭矩形。
请注意，在上述过程中，允许边界矩形变化（我也不相信解决方案是最佳封闭矩形）。您可以通过将圆分解为离散的矩形来近似圆。
虽然不是您正在寻找的完整解决方案，但我认为这可能是一个很好的第一步。
于 2012-10-04T14:05:02.820 回答