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

Question

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

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)]