🔒 Locked

Tangram Solving Algorithm?

Started by EmrldDrgn Oct 16, 2008 at 11:16 PM 2 replies 3.8k views

Original Post

Oct 16, 2008 at 11:16 PM

Well, OK, what I'm really trying to do is re-arrange a number of rectangles so that they will fill, as efficiently as possible, a finite rectangular space. I figure this is essentially tangrams, although probably quite a bit easier, and further that there are probably some very good algorithms out there to do this kind of thing. However, I cannot seem to find anything. Can anyone point me in the right direction? I'd be ever so grateful.

Nyarlath

Oct 17, 2008 at 3:27 AM

What is the meaning of "efficiently"? You want to minimize the area of the bounding rectangle, or the size of the bounding rectangle is predefined and you want to find a position for the rectangles to fill it? The rectangles should perfectly fill the bounding one, or the area of the bounding rectangle is greater than the sum of the smaller ones?

Deaken Frost

Oct 17, 2008 at 11:20 AM

The magic google word for this problem is: "rectangle packing" or more generally "bin packing". And it's not really easy. In fact it is NP-hard.

all_names_taken

110

all_names_taken

Oct 17, 2008 at 12:16 PM

You might need to specify the problem more formally first, before anyone can offer more help. Tangram is about fitting a given set of shapes into a given polygon, where we know beforehand that there exists an arrangement (translations and rotations of the shapes) which give a perfect fit. Packing rectangles in a polygon, while trying to minimize the number of and possibly the area of the needed rectangles, is a completely different problem. Or do you mean packing a given set of rectangles into a larger one? Are we given the entire set of available rectangles, or can we use some rectangle more than once? Etc etc.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.