For two overlapping arbitrary polygons, find the best rotation to maximize overlap

Question

I have two arbitrary polygons, which may or may not be the same shape. I am looking for advice on a simple algorithm that will rotate one of the polygons in order to minimize the difference between them. Thanks.

Answer 1

If you are trying to make them more similar, you can try to minimize the area of ​​difference between the two polygons. That is, the area of ​​the union of the two, minus the area of ​​intersection between them.

The approximation would be to find two points with a maximum distance in each polygon (let's call them "diameters") and align them for two polygons.

For instance:

• The polygon A = [(13, 12); (9, 14); (1,4); (5, 2)] [(13, 12); (9, 14); (1,4); (5, 2)] [(13, 12); (9, 14); (1,4); (5, 2)] (rhombus)
  • Diameter = [(13, 12); (1,4)] [(13, 12); (1,4)] (length 14.4 )
• The polygon B = [(14, 11); (8, 17); (3,24); (9, 18)] [(14, 11); (8, 17); (3,24); (9, 18)] [(14, 11); (8, 17); (3,24); (9, 18)] (another rhombus)
  • Diameter = [(14, 11); (3,24)] [(14, 11); (3,24)] (length 17.0 )

Polygon B is shifted and rotated so that the diameters align:

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