Comment est-ce que l’emballage 2D bin est réalisé par programmation?

Il y a quelques questions similaires sur stackoverflow, mais aucune ne semble fournir une réponse tangible à une personne sans une solide compréhension des problèmes NP-hard et des algorithmes.

Comment effectue-t-on un empaquetage 2D d’objects rectangulars? Dans mon cas, j’essaie d’assembler plusieurs images en une seule image, pour l’utiliser comme une feuille de calcul, en utilisant le moins d’espace possible. Chaque image a probablement des limites très différentes, mais il n’y a pas de limites définies pour le conteneur.

J’espérais que quelqu’un avec une compréhension des algorithmes de conditionnement en bac pourrait expliquer comment cela peut être réalisé par programmation, plutôt que de fournir une vue d’ensemble de la méthode de conditionnement en bac.

J’ai googlé “bin packing code” et ce fut mon premier hit: http://codeincomplete.com/posts/2011/5/7/bin_packing/

En résumé, créez un arbre binary. Chaque twig de l’arbre contient un sprite. Chaque nœud feuille représente l’espace disponible. Initialement, l’arbre n’a que le nœud racine, qui représente tout l’espace disponible. Pour append une image-object à l’arborescence, recherchez dans l’arborescence un nœud inoccupé (feuille) suffisamment grand pour contenir l’image-object. Transformez ce nœud d’une feuille en une twig en définissant l’image-object en tant qu’occupant du nœud et en atsortingbuant deux nœuds au nœud. Un enfant représente l’espace restant à droite de l’image-object; l’autre représente l’espace restant sous le sprite et le premier enfant.

L’article que j’ai lié ci-dessus l’explique beaucoup plus en détail, avec des diagrammes et du code JavaScript. Il explique également comment développer dynamicment la feuille de sprite plutôt que de choisir une taille fixe à l’avance.

Tout ce dont vous avez besoin est ici: https://github.com/juj/RectangleBinPack

Il y a un papier et une implémentation C ++ décente.

Si vous avez besoin d’un pseudo-code encore plus simple, consultez ce site: http://www.blackpawn.com/texts/lightmaps/

Le “pack guillotine” est appelé emballage à base d’arbre.