Re: [Algorithms] Best fit of polygon inside another polygon

[Jon W. <jw...@gm...>]

Stefan Dänzer wrote:
> size. I have different polygons with varying shape and size and I want
> to find the polygon and according transformation of the polygon which
> best fits it into the given quad. The allowed transformations which
> can be applied to the polygon are translation and scaling.
>   

But you could just as easily try to fit the rectangle around the 
polygon, using translation and rotation, and then just invert that 
transform to go from polygon to rectangle.

In general, I believe you can show that the optimal fit will have one 
side of the polygon parallel with one side of the rectangle. If that is 
indeed the case, a very straightforward algorithm (but slow) would be:

foreach polygon:
  foreach side in the polygon
    for lengthwise and heightwise sides in rectangle
      translate and rotate polygon so that it fits as well as possible 
with the polygon side snug to the rectangle side
      test whether fully inside, and calculate coverage

Then pick the one with the best coverage value while being fully inside.
To calculate the "snug fit" you rotate the polygon to match the side to 
the rectangle, rotate your frame of reference to make this side "right," 
and then slide it so that the uppermost vertex just touches the 
uppermost side of the rectangle.

Sincerely,

jw