Arrangement of shapes in an area

[xchaos01]

Hello,

I'm trying to research a method or algorithm to determine how to best fit a couple of diferent shapes into a given area.

Type of area: Rectangular
Types of shapes: Rectangles, Triangles, Circles

Where I work at we have to figure out how to best arrange the shapes we need into a steel metal plague (10ft x 15ft for example) in order to require the least amount of plaques so we can give the customes a lower price overall.

I've tried my luck with google but I can't quite pinpoint the correct search criteria for this.

Any help is appreciated. Thanks.

EDIT: BTW, if this topic belongs to another section please direct me to it.

 

[gb7nash]

Hello,

I'm trying to research a method or algorithm to determine how to best fit a couple of diferent shapes into a given area.

This is pretty well-known problem. It's also a very difficult problem. The one I usually hear about is how to fit disks of a certain size inside of a square so that you maximize the area. There's plenty of naive algorithms to fit disks into a square(most likely won't obtain an optimal solution), but as far as maximizing your area, it's hard to do.

 

[Stephen Tashi]

Search for "die cutting layout optimization algorithms". You get hits like: http://www.google.com/url?sa=t&sour...k_G1Dg&usg=AFQjCNEYHySBKxxqLOGOxVWacn2sBwsiuw