12

I need algorithm which splits big static sized rectangle to small ones. A perfect implementation for me look like this:

struct RECT
{
  int l,t,r,b;
};

class BigRect
{
public:
  // width and height of big rect
  BigRect( unsigned width, unsigned height );

  // returns -1 if rect cannot be allocated, otherwise returns id of found rect
  int GetRect( unsigned width, unsigned height, RECT &out );

  // returns allocated rect to big rectangle
  void FreeRect( int id );
};

void test()
{
  BigRect r( 10, 10 );

  RECT out;
  r.GetRect( 4, 4, out ); // rect found ({0,0,4,4} for example), returns 1
  r.GetRect( 5, 5, out ); // rect found ({4,0,9,5} for example), returns 2

  r.GetRect( 6, 6, out ); // no place found for rect, returns -1
  r.FreeRect( 2 );        // add {4,0,9,5} back to rect

  r.GetRect( 6, 6, out ); // rect found (4,0,10,6)
}

So I need algorithm for GetRect and FreeRect methods. Any ideas and links would be appreciated.

Josh Lee
  • 171,072
  • 38
  • 269
  • 275
pure cuteness
  • 1,635
  • 11
  • 26
  • Are there any restrictions on how the sub-rectangles are to be allocated? E.g. is there a goal to pack rectangles efficiently, or can you just stick them anywhere they will fit? – verdesmarald May 23 '11 at 14:32
  • @Jean-Paul Calderone. It's not homework. @veredesmarald of course it would be better to allocate them efficiently. – pure cuteness May 23 '11 at 14:34
  • @Jean-Paul Calderone, I'm not sure it can be a homework. It looks he need some sort of allocator on 2D heap, it could be pretty complicate to develop an efficient implementation that will minimize fragmentation. – Kirill V. Lyadvinsky May 23 '11 at 14:36
  • What are l,t,r,b? Can rectangles overlap? – Emile Cormier May 23 '11 at 14:39
  • 1
    @Emile Cormier, they mean "left,top,right,bottom". No, they can't overlap. As Kirill V. Lyadvinsky said it is sort of allocator on 2D heap. – pure cuteness May 23 '11 at 14:41
  • Can you specify any restrictions to the order in which the rectangles may be allocated or does this need to work on random input? – Axel Gneiting May 23 '11 at 14:44
  • @Axel, I don't understand your question. They can be allocated anywhere inside big rectangle, they just can't overlap. – pure cuteness May 23 '11 at 14:49
  • So really this is a tessellation / packing problem? – James May 23 '11 at 14:52
  • @pure cuteness: I think what Alex means is is it's possible to sort rectangles from largest to smallest before trying to allocate them. In other words, is it an online or offline bin packing problem. – Emile Cormier May 23 '11 at 14:53
  • @pure cuteness: You might get more help at the comp-sci stack exchange: http://cstheory.stackexchange.com/ – Emile Cormier May 23 '11 at 14:55
  • 1
    Well, I think it is better to explain background of problem. I need to place small pictures inside a big texture. So that is why I need to split it to small rectangles. – pure cuteness May 23 '11 at 14:59
  • @pure cuteness: In that case, it's an offline bin packing problem. You have all the small pictures at your disposal before packing them into the big picture, right? – Emile Cormier May 23 '11 at 15:01
  • 1
    I found some information here: http://www.csc.liv.ac.uk/~epa/surveyhtml.html . It's pretty theoretical, though. – Emile Cormier May 23 '11 at 15:02
  • @Emile Cormier, yep. It looks like something I need. Thank you, I'll check it. – pure cuteness May 23 '11 at 15:03
  • Why the close votes? He's looking for 2D packing algorithms. – Emile Cormier May 23 '11 at 15:06
  • I vote to re-open as well, it seems a valid question to me. – Nim May 23 '11 at 15:07
  • 1
    @pure cuteness: If you search for "texture packing" you'll also find some useful information. People in the gaming world have the same problem as you do. This guy posted some sample code: http://codesuppository.blogspot.com/2009/04/texture-packing-code-snippet-to-compute.html – Emile Cormier May 23 '11 at 15:08
  • See also: http://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm – Emile Cormier May 23 '11 at 15:15
  • Searching for "texture atlas" might also be helpful. – Emile Cormier May 23 '11 at 15:17
  • @Emile Cormier, damn, you are really cool, many thanks – pure cuteness May 23 '11 at 15:18

1 Answers1

7

What you're trying to do is online 2D bin packing. It's online because you don't have all your small pictures in hand before you attempt to pack them into the big picture. Furthermore some small pictures will be "deallocated" and their space will be freed up. On the other hand, an offline algorithm allows you to do things like sort your small pictures from largest to smallest before packing them.

Here's an article that surveys the state of the art in 2D packing: Survey on two-dimensional packing. It's quite theoretical.

This article A New Upper Bound on 2D Online Bin Packing cites other articles that describe online 2D packing algorithms.

People in the gaming world have a similar problem as you do; they call it texture packing or texture atlas. However, they use offline algorithms.

John Ratcliff posted a blog article on texture packing.

See also this related question on gamedev: https://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm

Community
  • 1
  • 1
Emile Cormier
  • 28,391
  • 15
  • 94
  • 122