给定两个重叠的任意多边形，找到最佳旋转角度以最大化重叠面积。

Question

我有两个任意的多边形，它们可能是相同的形状，也可能不是。我正在寻求一个简单的算法建议，该算法将旋转其中一个多边形以最小化两者之间的差异。谢谢。

- John Traynor

---

“overlap”是正确的度量标准吗？如果其中一个多边形比另一个大得多，则无论旋转了多少，它都可能完全包含另一个。此外，多边形是否应该进行缩放或平移？ - j_random_hacker

@j_random_hacker 我不确定重叠是否是最佳方法，我已经尝试了最接近点之间的均方误差，但似乎也不正确。目前规模不是问题，但我已经考虑了平移，同时进行平移和旋转是否更好？由于我的数学背景不太好，因此试图组合一个更通用的算法，而不是采用数学方法。 - John Traynor

好的。我不知道这个问题是否存在任何“好的”算法（可能有）。另一个问题是：两个多边形的顶点数量总是相同吗？如果是，那么我可以建议一种“尝试几次旋转并查看”的方法，该方法使用http://en.wikipedia.org/wiki/Assignment_problem来最优地匹配2个多边形之间的顶点。 - j_random_hacker

多边形最好有相同数量的顶点，但情况并非总是如此。如果不特意计算，似乎蛮力法会是最佳选择。谢谢。 - John Traynor

Answer 1

如果您想使它们更相似，则可以尝试最小化两个多边形之间差异的区域。也就是说，它们的并集面积减去它们的交集面积。

一种近似方法是找到每个多边形中距离最远的两个点（我们称之为“直径”），并将它们对齐在两个多边形上。

例如：

多边形A = [(13,12);(9,14);(1,4);(5,2)]（一个菱形）

直径 = [(13,12);(1,4)]（长度为14.4）

多边形B = [(14,11);(8,17);(3,24);(9,18)]（另一个菱形）

直径 = [(14,11);(3,24)]（长度为17.0）

将多边形B移动和旋转以使直径对齐：

[(14.08465297, 12.72310198); (7.439737081, 7.446257009);
 (-0.084652970, 3.276898021); (6.560262919, 8.553742991)]

- Markus Jarderot

---

这似乎是一个可靠的方法，谢谢，我会实施并看看效果如何。 - John Traynor

有时候会出现这样的情况，例如两个完全相同、又长又窄的三角形可以用两种不同的方式排列，一种情况下重叠率约为50%，而在另一种情况下则为100%。你需要尝试这两种方式才能确定正确的排列方法。 - Thomas

好观点。由于B几乎对称，我甚至没有考虑到这个细节。 - Markus Jarderot