Partitionnement d'un grand rectangle à un petit rectangle (emballage 2D)

Question

J'ai besoin d'un algorithme qui divise un grand rectangle de taille statique en petits rectangles. Une implémentation parfaite pour moi ressembler à ceci:

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

donc j'ai besoin algorithme pour GetRect et FreeRect méthodes. Toutes les idées et les liens seraient appréciés.

Answer 1

Ce que vous essayez de faire est en ligne 2D bin emballage. C'est en ligne parce que vous n'avez pas toutes vos petites images en main avant d'essayer de les emballer dans la grande image. De plus, certaines petites images seront "désallouées" et leur espace sera libéré. D'autre part, un algorithme hors ligne vous permet de faire des choses comme trier vos petites images du plus grand au plus petit avant de les emballer.

Voici un article qui passe en revue l'état de l'art dans l'emballage 2D: Survey on two-dimensional packing. C'est assez théorique.

Cet article A New Upper Bound on 2D Online Bin Packing cite d'autres articles qui décrivent des algorithmes d'empaquetage 2D en ligne.

Les gens dans le monde des jeux ont un problème similaire à celui que vous rencontrez. ils l'appellent texture emballage ou texture atlas. Cependant, ils utilisent des algorithmes hors ligne.

John Ratcliff a posté un blog article sur l'emballage de la texture.

Voir aussi cette question connexe sur gamedev: https://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm