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

 Re: [Algorithms] Best fit of polygon inside another polygon From: Jon Watte - 2009-05-24 16:42:21 ```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 ```