On connaît le problème : comment tirer le meilleur parti d'une surface pour en faire le maximum de pièces ? J'ai un projet de rangement en sous-pentes pour 8 m linéaires d'une hauteur de 1 m, divisé en 9 modules selon 4 configurations différentes (armoires, étagères, bloc tiroir, meuble d'ordi). J'utilise du cp de merisier de la baltique de 2 cm d'épaisseur. C'est 54 tablettes et autres pièces à tirer de 15 m², soit 7 feuilles de 1m50 x 1m50 au minimum.
Alors j'ai tenté différentes approches naïves pour déterminer la meilleure façon de faire, tout en me renseignant sur les recherches ayant cours sur le sujet. C'est utile en recherche opérationnelle, pour la logistique bref, pas mal d'intérêts sont présents. Trop pour ici, mais je met des pointeurs à tout hasard.
Et là, j'ai trouvé la librairie python rectpack de secnot sur pypi.org. Code source sur github.
L'auteur s'est inspiré de l'ouvrage et du code de Jukka Jylang - A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing (2010) (voir ici pour le code).
Une trentaine de minutes plus tard, j'avais écrit un programme permettant de produire du code Openscad permettant de représenter le débit pour tester la performance à partir de ma feuille de débit. Le code est extrêmement simple. On définit la liste de pièces, la liste de feuilles à débiter, on créé un objet packer en précisant l'algorithme souhaité, on exécute le packer, et on obtient la liste des pièces pour chaque feuille, avec leurs coordonnées.
Le résultat est meilleur que ce que j'ai obtenu avec les approches précédentes (c.f les trois premières illustrations), et plusieurs ajustements sont possibles, dont le mode (à la volée ou d'un coup), la stratégie de remplissage des feuilles (quatre stratégies), le tri des pièces (sept options), le choix de l'algorithme (Skyline, MaxRects, Guillotine) et de ses variantes (8 pour Skyline, 6 pour MaxRects, 28 pour Guillotine).
Discussions
Salut pchartrand,
Intéressant. Certaines de tes captures montrent que ça ne donne pas forcément des coupes guillotines (traversantes). Ca sera pas forcément évident à couper avec un scie
Pour aller plus loin et si le CPP te fait pas peur, je t'invite à regarder du côté de PackingSolver. C'est le projet qui va s'intégrer à OpenCutList 7.0.
Sinon, il y a aussi quelques autres solutions par ici.
Merci Boris Beaulant. En effet, pour l'exemple 4, Soit le comportement par défaut de la librairie, les coupes ne sont pas traversantes, ce qui ne convient pas. Pour l'exemple 5, par contre, les coupes en profondeur sont traversantes pour les cinq premières feuilles après une passe, puis après deux ou trois passes pour deux dernières. C'est l'algorithme Guillotine Best Short Side Fit pour déterminer la section à sélectionner + Short Axis Split pour déterminer l'orientation de la coupe.
Même si je préfère le python, le C++ ne me fait pas peur, ce sont les politiques de licences de Sketchup et des autres CAD qui me retiennent. J'utilise Openscad et Freecad pour cette raison.
En tout cas je vois que tu as bien potassé la question, merci pour les pointeurs.
Connais tu OpenCutList ?
Je serais intéressé de savoir qu'elle algorithme y est utilisé.
Boris Beaulant précise que c'est la librairie PackingSolver écrite en C++ qui est utilisée dans OCL.
xyloweb qui sera sur la v7
Pour le moment c’est le code de Martin en Ruby qui fait le calepinage.
merci pour l'info
J’utilise OpenSCAD qui me sort les pièces à découper. Pour l’instant je faisais le calepinage en utilisant un logiciel en ligne, mais j’aimerais bien avoir une solution sans service en ligne, ça a l’air d’une bonne piste.
J’en parlais ici :
Idem pour PackingSolver, je garde ça dans un coin.
Merci !
Je t'ai envoyé un script python qui sait lire la sortie de ton script et générer une feuille de débit en Openscad par messagerie interne.
pchartrand C’est gentil ça, il faut que j’essaye :)