Учитывая два перекрывающихся произвольных многоугольника, найдите лучшее вращение, чтобы максимизировать перекрытие

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