对象定位算法 [英] Object Positioning Algorithm

问题描述

我不知道是否有一个最佳的解决方案针对此问题：

I'm wondering if there is an "optimal" solution for this problem:

我有anxm（像素）大小与对preexisting空间方型 - 在有各种大小的物体。现在，我希望把●在这个空间（同样大小）的新对象，没有任何重叠。

I have a n x m (pixel) sized space with p preexisting rectangled - objects in various sizes on it. Now I want to place q (same sized) new objects in this space without any overlapping.

我想出了这个算法：

1. 与大小创建数组A [] [] [（N）/（size_of_object_from_q）]×[（N）/（size_of_object_from_q）]

2. 遍历从对所有的元素，并为每个：

1. Create array A[][] with the size [(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]

2. Iterate all Elements from p and for each:

标记在各领域的A [] []作为占领，那里的元素谎言

广场●在其中，在[] []字段没有标记的根据地方的所有元素

Place all elements from q in the according places where the fields in A[][] are not marked

（男孩，我希望我能有这样的理解......）

(Boy, I hope I could make that understandable...)

有没有更好的方式来做到这一点？任何帮助真的会AP preciated！

Is there any better way to do this? Any help would really be appreciated!

推荐答案

从网上一个简短的搜索，似乎是最佳的长方形包装是的 NP难的问题。 我猜想，聪明的人在学术界发现了一些近似算法的，所以它是谷歌搜索的选项。

From a brief search in the internet, it seems that optimal rectangle packing is an NP-hard problem. I would guess that smart people in the academia found some approximation algorithms for that, so it is an option for googling.

不过，我会尽量让简单的方法工作的首位：

But I would try to make the simple method work first:

1. 将你的对象放入大小根据它们的宽度
2. 尝试把他们行由行从最大到最小。

我的猜测是，在许多情况下，这种天真的解决方案，将工作。

My guess is that in many cases this naive solution will work.

这篇关于对象定位算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！