Tetris packing with complex shapes

This topic is 4401 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi... I have a problem and i don't know how to search for a possible answer. I have an infinite number of things with this shape: and an empty 2D lattice. I want to fill this lattice with as much of these things as i can, thus minimizing the free space in the lattice. Any object can be rotated +-90 degrees. Because of the shape is symmetric in both x and y axis, only one rotation makes sense. Every colored square in the shape has exactly the same dimensions as the others. This looks a lot like Tetris, but with more complex shapes. I tried to search how this can be done, but i haven't found something useful (a paper, an algorithm). Does somebody have any suggestions/papers on that? Any keywords for searching on Google? Anything? As you can figure out, packing multiple objects like the above, always leave some empty space. This is because you can't have one object perfectly fit inside the other. There will always be some empty cells, left and right of the blue cells. Knowing this, is there any way i can calculate the minimum empty space that can be formed inside an arbitrary lattice? Thanks in advance. And if you have any questions, please ask. HellRaiZer

Share on other sites
is this a homework assignment?

Share on other sites
Quote:
 Original post by limais this a homework assignment?

No. I have stopped doing any homework 1.5 years ago (when i graduated from uni) :)

After all i'm not asking for the solution. I'm asking for directions/suggestions/etc. Something to read on the subject. I don't even know if this is possible, so i'm searching. Don't you think that if this was homework, i would already have something to start searching?

Do you have any info on that?

HellRaiZer

Share on other sites
Quote:
 Original post by HellRaiZerAfter all i'm not asking for the solution. I'm asking for directions/suggestions/etc. Something to read on the subject. I don't even know if this is possible, so i'm searching. Don't you think that if this was homework, i would already have something to start searching?Do you have any info on that?

Look for the algorithm called 'back tracking'...

1. 1
2. 2
3. 3
4. 4
Rutin
12
5. 5

• 12
• 16
• 10
• 14
• 10
• Forum Statistics

• Total Topics
632659
• Total Posts
3007691
• Who's Online (See full list)

There are no registered users currently online

×