2

我正在寻找一种算法来计算将凸多边形（P1）定位在另一个凸多边形（P2）内所需的平移、旋转和缩放。我需要它来返回“最佳拟合”，这意味着 P1 完全包含在 P2 中并且具有可能的最大面积。

考虑下图：http: //i.imgur.com/ckaIIv7.png

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

我在网上找到了很多关于多边形包含算法的书面论文，但这些算法是确定多边形是否可以放入另一个多边形中，因为它们具有平移和旋转的能力。

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

有什么帮助吗？

4

1 回答 1

4

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

假设您有P1with pvertices 和P2with qvertices，并且您希望适合P1inside P2。

您已经找到了描述如何确定 P1 是否可以放入 P2 的文章。比如这篇文章及时给出了一个算法O(pq^2)。P1如果您都知道并且p2是凸的，我不确定它是否会更快。

a因此，从一个a(P1)无法放入的大数开始，(P2)对 的值进行二分搜索a。

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

于 2015-07-21T20:37:17.830 回答