Блог

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

 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 amp;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 методов. Любые идеи и ссылки будут оценены.

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

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

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

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

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

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