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.



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.
GDAlgorithms-list mailing 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