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

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

That's what I actually thought, so that's what I answered.

Sincerely,

jw

Stefan Dänzer 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 <jw...@gm... 
> <mailto:jw...@gm...>> 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
>     GDA...@li...
>     <mailto:GDA...@li...>
>     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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list