Algorithme permettant de déterminer les coordonnées (x,y) des rectangles de manière à ce que l'aire du rectangle environnant soit minimale ?

Question

J'espère que mon titre a du sens, mais voici ce que j'essaie de faire :

J'ai n rectangles, chacun ayant une largeur de W _n et les hauteurs de H _n que je dois disposer de façon à ce que, sur un plan à deux dimensions (x,y), le rectangle dans lequel ils s'inscrivent tous prenne le moins de place possible. Je dois également être en mesure d'établir quelle (x,y) correspond à quel rectangle.

Je préférerais quelque chose en pseudo-code, mais je peux travailler avec plusieurs langages.

Merci de votre aide.

Answer 1

Il s'agit d'un problème difficile à résoudre de manière optimale, mais il existe des solutions qui ne sont pas trop difficiles à mettre en œuvre et qui représentent de bonnes approximations pour de nombreuses utilisations (par exemple pour les textures). Essayez de googler pour "rect(angle) packing" ... vous trouverez beaucoup de code qui résout le problème.

Answer 2

Il me semble que c'est un problème NP-complet. Un peu comme le problème du sac à dos. Ce qui signifie qu'il n'y a pas de véritable solution. Seulement de bonnes approximations.

Answer 3

Il s'agit d'une variante de l'emballage 2D. Le fait que votre conteneur soit flexible permet une plus grande optimisation et rend le défi plus difficile (comme dans difficile). Planificateur Drools (open source java) peut gérer cela. Il existe au moins une implémentation (voir la liste de diffusion des utilisateurs) avec Drools Planner (non open source). Si vous avez besoin d'un exemple open source pour commencer, l'équilibre des nuages dans drools-planner-examples est probablement un bon exemple.

Pour une vue d'ensemble des algorithmes que vous pouvez utiliser, voir ma réponse à une question similaire .

Answer 4

Votre problème est connu sous le nom de problème d'emballage 2D. Même le problème 1D est NP-hard. Voir aquí pour un bon article sur certaines approches, accompagné d'un exemple de code C#.

Voir aussi les questions suivantes :

• Comment puis-je déterminer de manière programmatique comment insérer des boîtes plus petites dans un paquet plus grand ?
• Où puis-je trouver des algorithmes d'emballage de bacs 2d en source ouverte ?