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

我有一种切割问题。有一个不规则的多边形，没有任何孔和一个标准大小的矩形瓷砖及其值的列表。在多边形内拟合矩形的算法

我想要一个高效的算法来找到适合这个多边形的单个最有价值的瓷砖;或者一个算法，它只是说一个单独的tile可以放在多边形内部。对于不到100个顶点的不规则多边形，它应该在确定的时间内运行。

请考虑你可以旋转多边形和瓷砖。赞赏凸和非凸多边形的答案/提示。

2013-03-13 aisa

上[多边形内部矩形]谷歌搜索将返回了一些有趣的结果，包括该研究论文的源代码：http://www.mpi-inf.mpg.de/~ jeschmid/public/Knauer2012.pdf和一些SO问题：http://stackoverflow.com/q/610462/56778和http://stackoverflow.com/q/10214829/56778 – 2013-03-13 12:55:54

你提到你的多边形是不规则的。它们是凸的吗？ – phs 2013-03-13 20:12:23

当然我之前已经使用过Google。但谢谢你的指导。我编辑了这个问题。 – aisa 2013-03-16 09:19:31

许多绝望的搜索后，我觉得没有任何特定的算法针对此问题。直到，我发现this old paper about polygon containment problem.
这个提到的文章，提出了一个非常好的算法来考虑如果一个多边形与n点可以适合多边形与米点或不。
对于两个可移动和可旋转的2D多边形，该算法通常为O（n^3 m^3（n + m）log（n + m））。

我希望它可以帮助你，如果你正在计算几何中寻找这样一个不规则的算法。

来源

2013-08-13 20:13:16 aisa

声明：我从来没有读过任何有关这方面的文献，所以可能有更好的方法来做到这一点。这个解决方案正是我在阅读完你的问题后想到的。

一个矩形，有两个重要的测量 - 它的高度，现在，如果我们开始与多边形和矩形它的宽度

：

polygon and rectangle

1：去身边的多边形的周长和请注意所有矩形的高度将适合多边形（您可以将其存储为多边形*）：

where will the hight fit?

2：去身边刚刚完成的新多边形的周长，并采取所有地方的矩形宽度将适合在多边形的说明（同样，你可以在此存储为一个多边形）：

3：矩形应该适应这种新的多边形内（只是要小心，你正确定位多边形内部的矩形，因为这是一个多边形的 - 而不是一个矩形。如果您将矩形的左上角节点与此新多边形的左上角对齐，则应该没问题）

4：如果没有找到矩形可以放入的区域，则将多边形旋转一对度，然后再试一次。

*注：在某些多边形，你会得到多个地方的矩形可以装：

来源

2013-04-09 20:18:15 stormCloud

感谢您的回答;但这不是我想要的。我想要一个算法来解决**矩形问题**的多边形遏制问题。 – aisa 2013-05-01 08:52:11

@aisa我的算法会告诉你一个矩形在每个给定的旋转中将在多边形内适合多少个不同的位置。所以如果地方的数量是零，矩形将不适合在那个旋转。如果位置数量>零，矩形将适合该旋转。所以用一个简单的条件语句，你可以检查你需要什么。除非您真的想要解决这个问题，因为您的公差极其严格，您应该能够将您算法的每次迭代所需的度数调整为您的方案。 – stormCloud 2013-05-01 22:37:30

这可能有帮助。它配备了编写的Java

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/

来源

2013-10-11 04:45:11

感谢您的帮助。但我提到多边形可以旋转。它不一定是凸面的。无论如何，再次感谢您的链接。 – aisa 2015-02-17 08:08:06

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

回答

相关问题