Разбиение большого прямоугольника на маленькие (2D упаковка)

Question

Мне нужен алгоритм, который разбивает большой прямоугольник статического размера на маленькие.Идеальная реализация для меня выглядит следующим образом:

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)
}

Поэтому мне нужен алгоритм для методов GetRect и FreeRect.Будем благодарны за любые идеи и ссылки.

Answer 1

То, что вы пытаетесь сделать, это онлайновая упаковка 2D бункеров .Это онлайн, потому что у вас нет всех ваших маленьких картинок в руках, прежде чем вы попытаетесь упаковать их в общую картину.Кроме того, некоторые маленькие картинки будут «освобождены», и их пространство будет освобождено.С другой стороны, автономный алгоритм позволяет вам выполнять такие вещи, как сортировка маленьких изображений от самых больших до самых маленьких перед их упаковкой.

Вот статья, в которой рассматривается современный уровень в упаковке 2D: Осмотр на двухмерной упаковке .Это вполне теоретически.

В этой статье Новая верхняя граница для 2D-упаковки онлайн-бин цитирует другие статьи, в которых описываются алгоритмы 2D-упаковки в Интернете.

Людив игровом мире есть такая же проблема, как и у вас;они называют это текстура упаковки или текстура атлас .Однако они используют автономные алгоритмы.

Джон Рэтклифф опубликовал статью блога об упаковке текстур.

См. Также этот связанный вопрос по gamedev: https://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm