用于在多边形内拟合矩形的算法

Question

我有一种切割问题.有一个不规则的多边形,没有任何孔和标准尺寸的矩形瓷砖及其值的列表.

我想要一个有效的算法来找到适合这个多边形的单个最佳值瓦片; 或者只是说单个图块是否适合多边形内部的算法.对于小于100个顶点的不规则多边形,它应该在确定的时间内运行.

请考虑您可以旋转多边形和瓷砖.凸起和非凸多边形的答案/提示是值得赞赏的.

Answer 1

免责声明:我从未阅读过任何关于此的文献,因此可能有更好的方法.这个解决方案正是我在阅读完你的问题后想到的.

矩形有两个重要的尺寸 - 它的高度和宽度

现在,如果我们从一个多边形和一个矩形开始:

1:绕过多边形的周边并记下矩形高度适合多边形的所有位置(可以将其存储为多边形*):

2:绕过你刚制作的新多边形的周长,记下矩形宽度适合多边形的所有位置(同样,你可以将它存储为多边形):

3:矩形应该适合这个新的多边形(只是要小心你正确地将矩形定位在多边形内部,因为这是一个多边形 - 而不是一个矩形.如果你将矩形的左上角节点与左上角的节点对齐这个新的多边形,你应该没问题)

4:如果找不到矩形适合的区域,则将多边形旋转几度,然后再试一次.

*注意:在某些多边形中,您可以获得多个矩形可以安装:

Answer 2

经过多次无望的搜索，我认为这个问题没有任何具体的算法。直到，我发现了这篇关于多边形包含问题的旧论文。
那篇文章提出了一个非常好的算法来考虑具有n 个点的多边形是否可以拟合具有m个点的多边形。
对于两个可移动和可旋转的二维多边形，该算法通常为 O(n^3 m^3(n+m)log(n+m))。

如果您正在计算几何中寻找这种不规则算法，我希望它可以对您有所帮助。