对象定位算法

Question

我想知道这个问题是否有"最佳"解决方案:

我有焦虑(像素)大小的空间与p预先存在的矩形 - 各种大小的对象.现在我想在这个空间中放置q(相同大小)的新对象而不重叠.

我提出的算法:

1. 使用大小创建数组A [] [] [(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]

2. 迭代p中的所有元素和每个元素:

   mark all fields in A[][] as occupied, where the element "lies"

3. 将q中的所有元素放在A [] []中字段未标记的相应位置

(男孩,我希望我可以理解......)

有没有更好的方法来做到这一点？真的很感激任何帮助!

Answer 1

从互联网上的简短搜索来看，最优矩形包装似乎是一个NP 难题。我猜想学术界的聪明人找到了一些近似算法，所以这是谷歌搜索的一个选择。

但我会尝试先让简单的方法起作用：

1. 根据物体的宽度将物体分成不同的尺寸
2. 尝试将它们从最大到最小逐行放置。

我的猜测是，在很多情况下，这种简单的解决方案会起作用。