On a donné quelques rectangles qui peuvent être mis en rotation, trouver un rectangle englobant la zone minimale

Question

Donc, je suis en train de mettre en œuvre un algorithme qui prend un certain nombre de rectangles en entrée et tente de les emballer dans un rectangle de surface minimale . Les rectangles peuvent tous être pivotés de 90 degrés. Je me rends compte que ceci est semblable au problème d'empaquetage de casier, mais je suis incapable de trouver un bon algorithme qui tient compte de la rotation. J'ai trouvé un article qui en parle longuement here et même si je comprends l'article lui-même, j'espérais trouver quelque chose de plus simple.

Des suggestions?

-Edit-

Je pense que je mal exprimé le problème plus tôt. On nous donne un certain nombre de rectangles, de sorte que chacun peut être tourné de 90 degrés. Nous devons trouver un rectangle qui s'adapte à tous les rectangles donnés de façon à ce que deux rectangles ne se chevauchent pas, tout en minimisant la surface du rectangle englobant. Le problème auquel je suis confronté ici est que l'on nous demande de trouver le minimum, au lieu d'avoir un rectangle englobant et de vérifier si les rectangles donnés correspondent ou quelque chose de ce genre.

Answer 1

J'ai eu de bons résultats en utilisant cet algorithme:

http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy

Edit:

L'algorithme décrit dans le lien que je fournis vous donnera un « Oui » ou « Non » répondre à la question de savoir si un ensemble donné de rectangles peut être placé dans un rectangle englobant spécifique. Pour trouver le rectangle englobant minimum, vous pouvez exécuter l'algorithme à plusieurs reprises. Fondamentalement, calculer une borne inférieure et une limite supérieure pour le rectangle englobant, puis faire une recherche binaire pour trouver la solution minimale qui tombe dans ces limites. Je suppose que le rectangle englobant est une taille fixe dans une dimension (c'est-à-dire que la largeur est constante, recherchant une longueur minimale ou vice versa). Si la largeur et la longueur du rectangle englobant peuvent varier, alors c'est plus difficile et cela peut ne pas fonctionner.

Un simple (mais naïve) méthode de calcul d'une borne limite inférieure et supérieure serait le suivant:

Limite inférieure - Le cas le plus est que tous les rectangles peuvent être emballés parfaitement sans espace perdu. Donc, additionnez la surface de tous les rectangles d'entrée et calculez la longueur du rectangle englobant requise pour cette zone. Limites supérieures - Le pire des cas est que chaque rectangle doit être empilé sur une "rangée" séparée, pour chaque rectangle d'entrée, calculez min(width, height) et additionnez-les (par exemple, les rectangles d'entrée faux sont empilés les uns sur les autres en utilisant la largeur minimale ou hauteur de chaque entrée de sorte que l'autre dimension de l'entrée ne dépasse pas la largeur du rectangle englobant).

Si vous travaillez un peu plus difficile, vous pouvez améliorer les bornes inférieures et supérieures de manière significative à réduire l'espace de recherche, mais cela devrait vous donner un point de départ.