Re: Best fit of polygon inside another polygon
"Nicholas \"Indy\" Ray" <[email protected]>
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <[email protected]> |
Without scaling this seems to be an odd request... as what defines any one fit better then another, so long as the polygon does fit within the quad, there lacks a metric for "best" as any fit will take the same area and have the same excess area. Indy On Sun, May 24, 2009 at 3:52 PM, Stefan Dänzer <[email protected]> wrote: > 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 <[email protected]> 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 >> [email protected] >> 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 > > ------------------------------------------------------------------------------ > 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 > [email protected] > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > ------------------------------------------------------------------------------ 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 [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list