围绕中心点进行矩形包装

Question

有不同（已知）宽度和高度的矩形列表。

如何将这些矩形排列在中心点周围

Answer 1

这使用标准的装箱技术。 这里没有一个或多个常规尺寸的容器来装箱子。 相反，盒子应围绕中心点尽可能紧密、整齐地排列。

我喜欢这样思考的一种方式是它模拟饱和溶液中的晶体生长。这些盒子是漂浮在溶液中的分子。 有时，盒子会在生长的晶体上找到完美契合的位置。 从随机的布朗运动中，出现了大规模的有序，形成了美丽的晶体。

以中心点为中心的二维空间分为4个象限

象限指数：

• 0：左上角
• 1：右上角
• 2：右下角
• 3：左下角

为了可以使用相同的代码来打包所有象限，每个象限都被旋转到右下象限的方向，打包，然后连同所有打包的盒子一起旋转回其最终位置。选择右下象限是因为点与中心包装点的距离只需通过 x 和 y 坐标之和来计算。

象限概念为我们提供了 4 个容器来包装。每个容器都是直角三角形，斜边敞开，因此我们可以根据需要继续填充容器。待包装的盒子按照面积递减的顺序进行排序，并以循环方式分配给象限（盒子 0 到象限 0，盒子 1 到象限 1，...盒子 3 到象限 0，盒子 5 到象限 1，...... ..）。 循环分配确保每个象限获得总面积大致相同的盒子。

未使用的空间块用于跟踪下一个盒子最适合安装的位置。 有几种算法可用于识别特定块的最佳空间，根据用户到底要优化的细节（块之间的最小间隙，或距中心点的最小平均距离，或性能，或...）。

当找到合适的空间时，它通常会比包装的盒子大，因此该空间被分成 2 个新的、较小的未使用空间块。 由于盒子是按尺寸递减的顺序包装的，因此后面的盒子通常可以装入较早的较大包装盒子之间留下的小间隙中。

这是该算法的典型结果

此算法的 C++ 实现以及用于构建该算法的 VSCODE 项目可在 https://github.com/JamesBremner/so79276745

获取