algorythme pour optimisation de découpe rectangulaire Résolu

Question

Bonjour,

Je me suis donné comme défi la réalisation d'un programme en vb6 qui me permettra de déterminer le 'best fit' d'un nombre 'x' de pièces carrées ou rectangulaires dans différents formats de feuille de matériaux tel que le contre-plaqué.  Je me suis vite rendu compte que sans un algorythme on devient rapidement limité.  Quelqu'un pourrait m'informer sur un algo existant que je pourrais consulter et utiliser?  

Merci

jmf0 · Answer

Bonjour,

Tu ne trouveras pas d'algo réel à ce sujet... seulement quelques approches.

Je m'y étais frotté sans réel succès il y a une dizaine d'années et avait fini par laisser une certaine place à des déplacements manuels (en essais) par glissers/déposers des "morceaux"...

Attention : inclure les "rognes" de l'outil qui sert à découper (et elles ne sont pas toujours là... selon que le morceau est "à l'intérieur" ou non) et ces rognes dépendent de nombreux facteurs, en fonction de l'outil lui-même, du matériau à découper, ... voire, dans certains cas... de la température ambiante et de celle générée par la découpe elle-même.

Bonne chance et amitiés.

jmf0 · Answer

Tu peux peut-être commencer par lire ceci :
http://www.developerfusion.com/article/5540/bin-packing/
(Désolé que ce soit en anglais)
Puis télécharger le zip et analyser.
Mais ne te fais pas trop d'illusions (relis ce que j'ai écrit plus haut...)

jmf0 · Answer

Re....

Bon...
J'ai cherché partout dans mon fouillis si j'avais gardé, par hasard, mes essais de l'époque...
Plus rien (j'ai apparemment jeté un vieux disque dur qui m'encombrait).
Je me rappelle toutefois que le meilleur essai s'était inspiré des méthodes utilisées par des pupitreurs pour optimiser la taille et la répartition, sur le disque dur, des fichiers gérés par le feu système d'exploitation Pick, à savoir : définition de "modulos" et "séparateurs". Le tout nécessitant la recherche de nombres premiers les plus proches.
Essaye de faire une recherche sur le Web avec les mots Pick, Modulo et Séparateur, pour le cas où il resterait quelque-chose sur ce que c'était....

jmf0 · Answer

Re...
Je n'ai hélà trouvé que ceci, qui temontrera dequoi parlait mon message précédent :
http://www.techno-science.net/?onglet=glossaire&definition=11543
Attarde-toi sur cette partie :

L'adressage à l'intérieur d'un fichier se fait au moyen d'une fonction de hachage (hash coding), [b]basée sur l'espace primaire
 et le modulo ( En arithmétique modulaire, on parle de nombres congrus modulo n Le terme modulo peut aussi être associé à...)/b
 couramment attribués au fichier, avec application d'un [b]algorithme à la clé de l'enregistrement, et gestion de chaînages de
 partitions (pages mémoire) lorsque nécessaire/b.

Je m'étais largement inspiré de l'algo dont il s'agit ici (en gras).
Tente de retrouver quelque-chose de précis à propos de cet algo là ...

jmf0 · Answer

Ah oui (les "bulles" remontent l'une après l'autre) :
J'ai oublié, dansd mon premier message, de citer un autre critère important :
Il concerne la détermination des déchets "utililes/utilisables"... et celà passe par encore d'autre critères, en fonction des matériaux, de leur vocation, des besoins futurs "raisonnablement prévisibles" etc... et comme les choses ne sont pas toujours simples, l'obligation de définir ces critères-là au "coup par coup" (y compris si l'on s'est fabriqué une petite base de données à exploiter à ce propos).
Dur dur, comme tu vois...
Tu as toute ma sympathie.

Mayzz · Answer

Et voila jmf ! Tu l'a fait fuir ! 

T'es fier de toi j'espère ^^


Si le déboguage est l'art d'enlever les bogues, la programmation doit être l'art de les créer.

Mayzz · Answer

Remarque, ce serait une bon moyen de faire le ménage sur le forum bombarder les boulets de messages remplis d'informations (je précise que je ne dis pas cela pour toi JeePeeTGI).

++

Si le déboguage est l'art d'enlever les bogues, la programmation doit être l'art de les créer.

jmf0 · Answer

Bonjour, Mayzz

Ce n'est pas dit du tout... (attendons lundi, pour voir...)
Il s'est embarqué sur un projet fort complxe et très intéressant.... 
Reste à savoir s'il est opiniâtre ou s'il n'est que vélléitaire...
A voir, donc ....

JeePeeTGI · Answer

Je n'ai malheureusement pas eu le temps de donner signe de vie avant aujourd'hui.  J'apprécie énormément que vous ayez pris le temps de me répondre et vais regarder cela dans le sens proposé.  J'ai déjà une ébauche fort intéressante même si elle ne respecte pas les protocoles de programmation standards.  J'avoue que dans chacun des programmes que j'ai fait, je débute toujours par faire la première ébauche en style 'naïf' sans aucune forme d'optimisation.  Je peaufine une fois que cela fonctionne.  jmf0, j'ai déjà prévu tenir compte des pertes et de ce que j'appelle les 'retailles utilisables' en fonction du matériel à découper. Donc présentement je tiens compte de la mise à l'équerre de la feuille, du 'trait de scie'(variable selon la lame utilisée... donc l'outil utilisé), de la dimension minimale de la retaille utilisable en fonction du matériel utilisé et finalement la perte.  De plus il fait déjà le calcul de feuille pleine et obtient des résultats à +/- une unité du nombre que l'on peut obtenir selon des logiciels spécialisés en vente sur internet.  J'en suis à la feuille partielle et c'est là que je me casse les dents présentement. Merci et si jamais d'autres infos vous revenait... le gars de Québec(moi) appréciera

jmf0 · Answer

D'ac...
Salue en attendant pour moi TOUT le Québec et si tu vas du côté de Chicoutimi ou en Gaspésie et passe là où il convient au moment où il convient : salue également la première ouananiche qui apparaîtrait... (et n'hésite pas à lui demander des conseils, à elle également : elle s'y connait en matière d'acrobaties en tous genres, les unes plus innattendues que les autres...)  
Tu as mon amitié.

Fusion3D · Answer

Bonjour,
j'ai besoin d'avoir un programme comme il est question dans cette discutions! Je cherche de l'aide SVP!
C'est pour un site Web en ligne.

CGSI3 · Answer

Bonjour Fusion 3D,

Créer  tu  devra   ( comme moi et d'autres ...)

Perso je suis sur ceci depuis 2 semaines et voici mon idée

Tu as  n  formes rectangulaires

Options a peut être préciser ou intégrer
- Utilisation de Doublons ?
- Rotation des formes a 90 degrés permise ? (je me limite a cet angle)

Associer 2 formes entres elles, pour fabriquer un rectangle englobant ces 2 formes et trouver l'espace encore disponible

Entre 2 Rectangles tu as différents test a effectuer


B
A  AB      A sur B  et A a coté de B  

=> C sera le rectangle résiduel sauf si les 2 rectangles ont une de leurs dimensions identique  => alors tu as une association parfaite

(si tu intègre la rotation, tu tourne un des rectangles et refais ces 2 tests de base)

Dans les 2 cas  on cherche la plus grande longueur dans une des dimensions(Largeur par exemple)  (la plus petite servira a trouver le vide laissé) 
et la somme des 2 autres longueur dans la dimension restante (2D)
(Hauteur par exemple)

=> on vient de créer un Nouveau rectangle  
On test si un des rectangles de base  (et que l'on viens de créer ) peut s’insérer dans le vide laissé  

Attention ici aux doublons et aux dimensions
Si toutes les formes de bases sont présentent   on ajoute cela aux solutions trouvés ...  avec le vide qui lui correspond

On donnera la solution avec le vide le moins conséquent

Tu n as rien préciser, mais si tu dois découper tes rectangles dans une plaque,  il convient également de connaitre les dimension de cette plaque pour tester que tout ceci rentre bien dans ta plaque a découper ...
Il y a donc un test a faire a un moment donné ...

Je te laisse réfléchir a ceci ...

Pour finir cette méthode permet de découper ta plaque par cisaillement  (d un bout a l autre de la plaque et en ligne droite)

Bonne Prog 
CGSI3


 
--

Fusion3D · Answer

Merci de votre réponse, mais en premier je doit trouver de l'aide pour obtenir ou concevoir les calcul.

Je préférais acheté un code source qui me permettrai de faire l'optimisation pour la découpe des panneaux. 

mon site Web : http://logicieldecuisine.com

ucfoutu · Answer

Bonjour,
Il ne s'agit pas simplement de calculs (ces derniers restant simples : addition de largeurs, addition de hauteurs), mais de bien bien bien bien plus : toutes les combinaisons de "découpes" et comparaison (seulement alors, tes "calculs") des "déchets" non utilisables.
Et tout cela : en tenant compte : du matériau à découper, de l'outil utilisé pour la découpe, etc ... et de la détermination des dimensions des déchets qui n'auraient aucun usage (pas les mêmes en ce qui concerne du carton et des feuilles d'or, par exemple ...).
Il n'existe à ma connaissance jusqu'à présent (y compris sur le marché) aucun logiciel de découpe  à la fois utile, rapide, précis et "universel).
On pourrait en parler très longuement (une fois de plus ...) . J'ai préféré aller ainsi directement à la remise des pieds sur terre.

EDIT : aucune tentative de conception d'un tel "produit" ne serait pensable sans, avant toute autre chose, une base de données recensant tous les déchets (les "chutes") susceptibles de trouver un jour une utilisation ultérieure (et cela : en fonction uniquement de l'expérience acquise et des constats faits).
 
________________________
Nul ne saurait valablement coder ce qu'il ne saurait exposer clairement.

Fusion3D · Answer

Est-que vous pouvez concevoir cela ?

ucfoutu · Answer

Je ne m'y amuserais même pas.
Et dis-voir, c'est toi, qui veut concevoir, non ?
Tu n'es tout de même pas venu ici pour que l'on conçoive à ta place un tel outil !
Et maintenant : regarde bien cette image de découpe :

En gris foncé : les rectangles à obtenir
en rouge les entames de l'outil de découpage
en beige : les chutes
Si j'avais en charge un atelier de découpe, je comprendrais cette découpe si le matériau coûtait très cher. Dans le cas contraire (du bois blanc, par exemple) , je me séparerais sans aucun état d'âme de l'ouvrier (alors très coûteux) s'y étant amusé.
J'arrête personnellement mon intervention là. 
________________________
Nul ne saurait valablement coder ce qu'il ne saurait exposer clairement.

Fusion3D · Answer

C'est exactement ce que je veux faire !

Le problème est que j'ai pas les connaissances pour concevoir les calcule et c'est pour cette étape que je recherche de l'aide.

Quelqu'un peut-il m'aider ?

ucfoutu · Answer

Quels calculs ? Tu les as déterminés ?
La partie "calculs" n'est pas du développement, mais des mathématiques. Le développement intervient pour les exprimer, une fois déterminés.
Détermine donc tes calculs. Reviens ensuite.

EDIT : avant de tenter de jouer à l'apprenti/découvreur, commence donc par :
1) la création d'une base de données évolutive concernant les chutes possiblement réutilisables ou vendables. Je dis bien évolutive car, pour être exploitable, une telle base de données devra, selon le matériau concerné :
- définir les dimensions minimum des chutes (je dis bien les dimensions et non la surface) "exploitables"
- donner à chaque article ainsi défini un coefficient d' "intérêt". Ce coefficient ne pourra qu'être le résultat de l'empirisme (chutes finalement exploitées ou peu exploitées ou jamais exploitées dans les faits). Cela signifie une table parallèle des chutes (gestion de leur stock), avec leur fréquence d'utilisation éventuelle
Rien que cette étape-là, c'est du boulot (et de conception, et de modélisation, et de temps d'expérience)
2) réfléchir sur le coût de l'utilisation d'un outil de découpe (encore une fois : en fonction du matériau, de sa valeur, etc ...)
Lorsque ce coût est élevé, il est souvent plus rentable de diminuer le nombre des découpes, quitte à partir des bords pour aller vers le centre (et avoir des chutes à l'intérieur plutôt que sur les bords).
Comme tu le vois (ces quelques réflexions de tout début) ce que tu cherches à faire est d 'une grande complexité, ne saurait être "universel", nécessite une analyse -basée sur l'empirisme- des besoins, des spécificités, des coûts comparatifs réels (y compris salariaux) , etc ...
Voilà. Je pense avoir dit l'essentiel (bien que ce ne soit pas, très loin de là, la totalité) 
Rien que ces deux étapes nécessiteront beaucoup de réflexion, une parfaite connaissance des besoins et des différents coûts et une durée d' "observation" (plusieurs mois au moins) suffisante en fonction de ce qui est déjà constatable et constaté dans l'état actuel des choses (avec des découpes "humaines", c'est à dire sans logiciel).
 
________________________
Nul ne saurait valablement coder ce qu'il ne saurait exposer clairement.

Algorythme pour optimisation de découpe rectangulaire

18 réponses

Votre réponse

Discussions similaires