Example:
If I have these rects:
GG
HHHHH BBB GG DDD
HHHHH and BBB and GG and DDD
BBB GG
I could make them into one square that would look like:
HHHHHGGBBB
HHHHHGGBBB
DDD GGBBB
DDD GG
Or...
HHHHH
HHHHH
GGDDD
GGDDD
GGBBB
GGBBB
BBB
The second one would in this case be optimal(I think!?)
Smallest rect to contain X amount of rects!?
Author
Okey, didn''t really know what to name this thread, and didn''t really know where to put it.
Well, I need to optimize the memory usage! And what I need to do is that I need to figure out the smallest possible rect to store X amount of other rect.
What I mean is:
I recently wrote some code to do this, although it''s kind of simplistic so it''s not nearly as optimized as it could be...
I did find this page a while back though:
http://www.blackpawn.com/texts/lightmaps/default.html
I haven''t really had time to read it in depth but it looks like it''s what you''re looking for
Raj
I did find this page a while back though:
http://www.blackpawn.com/texts/lightmaps/default.html
I haven''t really had time to read it in depth but it looks like it''s what you''re looking for
Raj
Author
quote:Original post by RajanSky
I recently wrote some code to do this, although it''s kind of simplistic so it''s not nearly as optimized as it could be...
I did find this page a while back though:
http://www.blackpawn.com/texts/lightmaps/default.html
I haven''t really had time to read it in depth but it looks like it''s what you''re looking for
Raj
Thank, but that didn''t sort them in an optimal way. It was just an algorithm to add many rects to one rect.
Anyone else got anything that might help?
/MindWipe
Author
quote:Original post by Anonymous Poster
What do you need it for, why can''t it be done with a linear array?
It''s java, J2me, so it''s very limited. I need the images compressed (it uses PNGs) and I need to use the inbuilt functions.
Hence the problem :/
/MindWipe
Here''s how I''d approach it:
1) Start with (arbitrarily) the tallest and/or widest rectangle in the top left of your container rectangle... heck just first rectangle in your array/list would probably do just as well.
2) For each remaining rectangle, run through every combination of adding it immediately to the a) right and then the b) bottom of the previous rectangle.
3) Only switch to the bottom after you have processed all the remaining rectangles in the same way.
4) Upon placing the last rectangle in the container rectangle for each configuration, check if the configuration has produced less empty spaces than the minimal ammount of empty spaces generated by any particular configuration so far.
5) Do this until you''ve either tried all configurations, or you find a configuration that yeilds no empty space.
Hope this helps!
-Glyph
Reading back through my answer, I realize that step 2 certainly won''t produce optimal results... perhaps try playing around with adding it to a) the right, b) the bottom, or c) the top of the next empty column. I''m sure there are others I can''t think of right now...
1) Start with (arbitrarily) the tallest and/or widest rectangle in the top left of your container rectangle... heck just first rectangle in your array/list would probably do just as well.
2) For each remaining rectangle, run through every combination of adding it immediately to the a) right and then the b) bottom of the previous rectangle.
3) Only switch to the bottom after you have processed all the remaining rectangles in the same way.
4) Upon placing the last rectangle in the container rectangle for each configuration, check if the configuration has produced less empty spaces than the minimal ammount of empty spaces generated by any particular configuration so far.
5) Do this until you''ve either tried all configurations, or you find a configuration that yeilds no empty space.
Hope this helps!
-Glyph
Reading back through my answer, I realize that step 2 certainly won''t produce optimal results... perhaps try playing around with adding it to a) the right, b) the bottom, or c) the top of the next empty column. I''m sure there are others I can''t think of right now...
I wonder if the optimal solution doesn''t fall in the P!=NP category. That is nearly impossible to reach exactly. Reminds me some scientific article in American Science. But not sure, I am not a real scientist 
This is a classic knapsack problem, which I believe is NP hard. A very common solution which yields good results is to start with the biggest object, and work your way smaller and smaller.
Author
Thank you all for the replies!
I think you can do it with the following algorithm:
Set the maximum height/width, then begin placing one rect going from top left to bottom right, so that it has been placed in every possible way.
After you have placed that one, place another. You will also have to make a list off all possible orders. Then you do the same with this other one, try every possibility and do the same thing with the next in line, etc etc.
That WOULD solve it, and will be rather simple to write. But it could take a while to computete. But I''m only talking 8-10 rects at once, so...
/MindWipe
I think you can do it with the following algorithm:
Set the maximum height/width, then begin placing one rect going from top left to bottom right, so that it has been placed in every possible way.
After you have placed that one, place another. You will also have to make a list off all possible orders. Then you do the same with this other one, try every possibility and do the same thing with the next in line, etc etc.
That WOULD solve it, and will be rather simple to write. But it could take a while to computete. But I''m only talking 8-10 rects at once, so...
/MindWipe
*shrug* I think the thing I wrote would work pretty fine in this case... it''s not too fast but it gets the job done. Basically as someone mentioned, you begin by sorting your objects by size, so you insert the largest one first, and so on.... (Note that size isn''t area, but rather the max of the rectangles width and height)
Another trick that works very well is to allow rotations. For example, if you attempt to add a rectangle and it fails, then rotate it 90 degrees and try again... Then just set a flag that it has been rotated.
Then, the basic idea is that every time you want to add a rectangle you scan all pixels and say "can I insert it at this (x,y)?"... Now obviously if you implement it the simple way and do a collision test with every rectangle, for every pixel, it''s going to run like crap. But, with some acceleration techniques it runs fine assuming it''s not used every frame or in any other speed critical area, and the space taken up is minimized as far as I could tell. The solutions are probably no less than 5% away from optimal.
There is one other potential issue, depending on how you do things... This algorithm assumes that the rectangles are sorted from large to small. If your rectangle list is determined prior to running the algorithm then you can sort it once and be done with it. But if the interface to your code is that rectangles are added one at a time, and you don''t know if they will come in any particular order, then you will have to recalculate the entire solution every time, so that you can add the new rectangle, sort the whole rect list, and then re-compute the solution.
This can be expensive though... So, what I did was simply allow new rects to be added without recomputing (so there''s no guarantee it will be optimal)... but, then the next time a rectangle fails to be added, recompute the solution. Hopefully this will free up some space, so now the texture addition will work properly. If not, then expand the rectangle dimensions by some amount and recompute the solution for that area. In my case, since I am dealing with textures, I expand to the next power of two. So if I''m at 32x64 then I expand to 64x64.
Hope that wasn''t too confusing
Here''s a screenshot w/ an example... It''s a tool for adding textures to a texture sheet, automatically keeping track of the UV coordinates. This was made without the rotation optimization- I decided to take it out because it still produces pretty good results, and I didn''t want to waste lots of time on this..
Raj
Another trick that works very well is to allow rotations. For example, if you attempt to add a rectangle and it fails, then rotate it 90 degrees and try again... Then just set a flag that it has been rotated.
Then, the basic idea is that every time you want to add a rectangle you scan all pixels and say "can I insert it at this (x,y)?"... Now obviously if you implement it the simple way and do a collision test with every rectangle, for every pixel, it''s going to run like crap. But, with some acceleration techniques it runs fine assuming it''s not used every frame or in any other speed critical area, and the space taken up is minimized as far as I could tell. The solutions are probably no less than 5% away from optimal.
There is one other potential issue, depending on how you do things... This algorithm assumes that the rectangles are sorted from large to small. If your rectangle list is determined prior to running the algorithm then you can sort it once and be done with it. But if the interface to your code is that rectangles are added one at a time, and you don''t know if they will come in any particular order, then you will have to recalculate the entire solution every time, so that you can add the new rectangle, sort the whole rect list, and then re-compute the solution.
This can be expensive though... So, what I did was simply allow new rects to be added without recomputing (so there''s no guarantee it will be optimal)... but, then the next time a rectangle fails to be added, recompute the solution. Hopefully this will free up some space, so now the texture addition will work properly. If not, then expand the rectangle dimensions by some amount and recompute the solution for that area. In my case, since I am dealing with textures, I expand to the next power of two. So if I''m at 32x64 then I expand to 64x64.
Hope that wasn''t too confusing
Here''s a screenshot w/ an example... It''s a tool for adding textures to a texture sheet, automatically keeping track of the UV coordinates. This was made without the rotation optimization- I decided to take it out because it still produces pretty good results, and I didn''t want to waste lots of time on this..
Raj
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
