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

[Stefan D. <ste...@gm...>]

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...> 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...
> 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