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

 Re: [Algorithms] Best fit of polygon inside another polygon From: Stefan Dänzer - 2009-05-24 22:53:11 Attachments: Message as HTML ```Sorry Jon, I stated the allowed transformations incorrectly in my last email. The following part: "The allowed transformations which can be applied to the polygon are translation and scaling" should read: The allowed transformations which can be applied to the polygon are translation and rotation." Sorry for the confusion. On Sun, May 24, 2009 at 6:42 PM, Jon Watte wrote: > 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 > > > > ------------------------------------------------------------------------------ > Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT > is a gathering of tech-side developers & brand creativity professionals. > Meet > the minds behind Google Creative Lab, Visual Complexity, Processing, & > iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian > Group, R/GA, & Big Spaceship. http://www.creativitycat.com > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > -- -- Stefan Daenzer Körnerplatz 8 04107 Leipzig Tel.: +49-176-61157550 "Work like you don't need the money, love like you've never been hurt and dance like no one is watching." - Randall G Leighton ```