我正在寻找一种算法来计算定位凸多边形(P1)内部另一个凸多边形(P2)所需的平移，旋转和缩放。我需要它返回"最佳匹配"，这意味着P1完全包含在P2中，并且具有最大可能的面积。
考虑下面的图:https://i.stack.imgur.com/PfnSG.png
右边的黑色多边形(P1)需要最优地放置在左边的蓝色多边形(P2)里面。
我在网上找到了很多关于多边形包含算法的书面论文，但这些算法是确定是否多边形可以容纳在另一个多边形中给定平移和旋转它们的能力。
我正在寻找的算法应该总是产生一个结果，因为它包括缩放多边形P1的能力。我知道这种算法可以产生多个最优答案，这没关系。
帮忙吗?
好吧，如果没有人有更好的想法，我想给出一个不太好的算法。
假设你有P1的p顶点和P2的q顶点，你想把P1放在P2里面。
您已经找到了描述如何确定P1是否可以放入P2的文章。以O(pq^2)时间为例，本文给出了一个算法。我不确定如果你知道P1和p2都是凸的，它是否还能更快。
所以，从一个大的数字a开始，这样a(P1)就不能放在(P2)里面，然后对a的值进行二进制搜索。
这不是很聪明，但至少它给出了答案。如果有人贴了更好的答案，请忽略我的…