logo标签列表

对象定位算法

algorithmobjectpartitioning
6
我想知道是否有一种“最优”解决方案来解决这个问题：
我有一个大小为n x m（像素）的空间，上面有各种不同大小的p个矩形对象。现在我想在这个空间中放置q个相同大小的新对象，而没有任何重叠。
我想出的算法如下：
1. 创建大小为[(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]的数组A[][]。 2. 遍历所有p中的元素，并对每个元素执行以下操作： 在A[][]中标记所有“位于”该元素上的字段为已占用。 3. 将q中的所有元素放置在A[][]中未被标记的相应位置上。
是否有更好的方法来解决这个问题？非常感谢您的帮助！
只是为了明确，您不能重新定位现有的对象，对吗？ - Larry OBrien
你的“q个相同大小的新对象”是什么形状？它们都是矩形吗？你可以旋转它们吗？ - Mark Byers
3个回答
1
如果我理解问题正确的话，你似乎正在寻找一种“最优”的装箱算法（也称为背包问题）。这是一个NP-Complete问题，尽管你的描述听起来像是可以通过蛮力方法得到最优解。
1

从互联网的简短搜索来看，最优矩形装箱似乎是一个NP-hard问题。 我猜想学术界的聪明人已经找到了一些近似算法，因此这是一个谷歌搜索的选项。

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

  1. 根据宽度将对象分成不同大小
  2. 从大到小逐行尝试放置它们。

我猜在许多情况下，这种天真的解决方案都能够奏效。

0

我知道这不是你问题的具体答案，但研究和/或挖掘graphviz源代码可能会很有用。graphviz提供了许多布局模型，包括neato，它试图最小化全局能量函数。

维基百科上有一些关于力导向算法的伪代码。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接