我有一种切割问题。有一个没有任何孔的不规则多边形和一个标准尺寸的矩形瓷砖及其值的列表。
我想要一个有效的算法来找到适合这个多边形的单个最有价值的瓷砖；或仅说明单个图块是否可以放入多边形的算法。对于少于 100 个顶点的不规则多边形，它应该在确定的时间内运行。
请考虑您可以旋转多边形和瓷砖。对凸多边形和非凸多边形的答案/提示表示赞赏。
问问题
8684 次
3 回答
7
免责声明：我从来没有读过任何关于这方面的文献，所以可能有更好的方法来做到这一点。这个解决方案正是我在阅读您的问题后所想到的。
矩形有两个重要的测量值 - 它的高度和宽度
现在如果我们从一个多边形和一个矩形开始：
1：绕过多边形的周边并记下矩形高度适合多边形的所有位置（您可以将其存储为多边形*）：
2：绕过刚刚制作的新多边形的周边，并记下矩形宽度适合多边形的所有位置（同样，您可以将其存储为多边形）：
3：矩形应该适合这个新多边形（请注意将矩形正确放置在多边形内，因为这是一个多边形 - 不是矩形。如果将矩形的左上角节点与左上角节点对齐这个新的多边形，你应该没问题）
4：如果找不到适合矩形的区域，请将多边形旋转几度，然后重试。
*注意：在一些多边形中，你会得到不止一个地方可以安装一个矩形：
于 2013-04-09T20:18:15.723 回答
2
经过多次无望的搜索，我认为这个问题没有任何特定的算法。直到，我发现了这篇关于多边形包含问题的旧论文。
提到的那篇文章，提出了一个非常好的算法来考虑具有n个点的多边形是否可以适合具有m个点的多边形。
对于两个可移动和可旋转的二维多边形，该算法通常为 O(n^3 m^3(n+m)log(n+m))。
如果您正在计算几何中寻找这样的不规则算法，我希望它可以帮助您。
于 2013-08-13T20:13:16.233 回答
2
这可能会有所帮助。它自带Java编写的源代码
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
于 2013-10-11T04:45:11.133 回答