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

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