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

[Nicholas \Indy\ R. <ar...@gm...>]

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 <ste...@gm...> 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...> 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
>
> ------------------------------------------------------------------------------
> 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
>