Tetris packing with complex shapes
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
Quote:Original post by lima
is 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
Quote:Original post by HellRaiZer
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?
Look for the algorithm called 'back tracking'...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement