多边形堆积 2D
我在包装 2 个任意多边形时遇到问题。即我们有 2 个任意多边形。当包围该多边形的矩形具有最小面积时，我们要找到该多边形的这种放置（我们可以进行旋转和移动）。
我知道，这是一个NP完全问题。我想选择一种有效的算法来解决这个问题。我正在寻找不适合多边形的方法。但我在任何地方都找不到简单明了的算法来查找两个任意多边形的 NFP。
I have problem of packing 2 arbitrary polygons. I.e. we have 2 arbitrary polygons. We are to find such placement of this polygons (we could make rotations and movements), when rectangle, which circumscribes this polygons has minimal area.
I know, that this is a NP-complete problem. I want to choose an efficient algorithm for solving this problem. I' looking for No-Fit-Polygon approach. But I could't find anywhere the simple and clear algorithm for finding the NFP of two arbitrary polygons.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
参数空间看起来并不算太大，测试起来也不错。如果固定一个多边形，则另一个多边形可以沿 x 轴移动 X，沿 y 轴移动 Y，并旋转 r。
X 和 Y 的感兴趣区域可以通过找到多边形的边界框来确定。 r当然是在 和 360 度之间。
那么，您可以在 X、Y 和 r 的有趣范围内尝试一组等距间隔。或许，一旦你发现了这些维度中有趣的点，你就可以进行更细粒度的搜索。
The parameter space does not seem too big and testing it is not too bad either. If you fix one polygon, the other ploygon can be shifted along x-axis by X, and shifted along y-axis by Y and rotated by r.
The interesting region for X and Y can be determined by finding some bounding box for for the polygons. r of course is between and 360 degrees.
So how about you tried a set of a set of equally spaced intervals in the interesting range for X,Y and r. Perhaps, once you found the interesting points in these dimensions, you can do more finer grained search.
如果它是 NP 完全的，那么你需要启发式方法，而不是算法。我会尝试将每一对可能的侧面放在一起，然后将一个侧面滑动到另一个侧面以最小化面积，当然，如果它们是凹形的，则受到可能重叠的限制。
If its NP-complete then you need heuristics, not algorithms. I'd try putting each possible pair of sides together and then sliding one against the other to minimise area, constrained by possible overlap if they are concave of course.
在 C++ 库中，使用轨道方法实现了稳健且全面的不拟合多边形生成：https:/ /github.com/kallaballa/libnfporb
（我是libnfporb的作者）
There is an implementation of a robust and comprehensive no-fit polygon generation in a C++ library using an orbiting approach: https://github.com/kallaballa/libnfporb
(I am the author of libnfporb)