如何找出凸多边形与其它凸多边形的最佳拟合

Question

我正在寻找一个算法来计算在另一个凸多边形(P2)中定位凸多边形(P2)所需的平移、旋转和缩放。我需要它返回“最佳匹配”，这意味着P1完全包含在P2中，并且有最大的可能范围。

请考虑下面的图表：http://i.imgur.com/ckaIIv7.png

右侧的黑色多边形(P1)需要最优地放置在左边的蓝色多边形(P2)中。

我在网上发现了很多关于多边形包含算法的书面论文，但是这些算法都是为了确定，多边形，是否适合于另一个多边形中的，因为它们具有转换和旋转的能力。

我正在寻找的算法应该总是产生一个结果，因为它包括缩放多边形P1的能力。我知道这种算法可以产生多个最优答案，这没关系。

有什么帮助吗？

Answer 1

好吧，如果没人有更好的主意，我想给出一个不太好的算法。

假设您有P1和p顶点，P2有q顶点，您希望在P2中安装P1。

您已经找到了描述如何确定P1是否适合P2的文章。例如，这篇文章给出了一个以O(pq^2)时间为单位的算法。如果你知道P1和p2都是凸的，我不确定它是否还能更快。

因此，从大量的a开始，这样a(P1)就不能适应(P2)，并对a的值进行二进制搜索。

这不是很聪明，但至少它给出了答案。如果其他人发表了更好的答案，请忽略我的.