物体定位算法
我想知道这个问题是否有一个“最佳”解决方案：
我有一个xm（像素）大小的空间，上面有p个预先存在的矩形-各种大小的对象。现在我想在这个空间中放置q个（相同大小的）新对象，没有任何重叠。
我想出的算法：
- 创建数组 A[][]，其大小
[(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)] 迭代所有元素p 并且对于每个：
将 A[][] 中的所有字段标记为已占用，元素“所在”的位置将 q 中的所有元素放置在 A[][] 中字段未标记的相应位置
（男孩，我希望我能让这一点可以理解......）
有没有更好的方法来做到这一点？任何帮助将不胜感激！
I'm wondering if there is an "optimal" solution for this problem:
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.
The algorithm I came up with:
- Create array A[][] with the size
[(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)] Iterate all Elements from p and for each:
mark all fields in A[][] as occupied, where the element "lies"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...)
Is there any better way to do this? Any help would really be appreciated!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
从互联网上的简短搜索来看，最佳矩形包装似乎是一个 NP-hard 问题。
我猜想学术界的聪明人找到了一些近似算法，所以这是谷歌搜索的一个选择。
但我会尝试首先使用简单的方法：
我的猜测是，在很多情况下，这种简单的解决方案会起作用。
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:
My guess is that in many cases this naive solution will work.
如果我理解这个问题，听起来您正在寻找“最佳”装箱算法（又名背包问题）。这是一个 NP 完全问题，尽管您的描述听起来您可能可以通过暴力方式获得最佳解决方案。
If I understand the question, it sounds like you are looking for an "optimal" bin packing algorithm (aka the Knapsack Problem). That's an NP-Complete problem, although your description sounds like you can probably brute-force your way to an optimal solution.
我知道这不是您问题的具体答案，但研究和/或深入研究 graphviz 可能很有用源代码。 graphviz 提供了许多布局模型，包括 neato，它试图最小化全局能量函数。
维基百科有一些基于力的算法的伪代码。
I know this isn't a specific answer to your question, but it may be useful to research and/or dig into the graphviz source code. graphviz offers a number of layout models, including neato, which attempts to minimize a global energy function.
Wikipedia has some pseudo-code for force-base algorithms.