Algorythme pour optimisation de découpe rectangulaire [Résolu]

Messages postés
8
Date d'inscription
samedi 19 février 2005
Dernière intervention
13 mars 2014
- - Dernière réponse : ucfoutu
Messages postés
18039
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
- 31 mai 2016 à 20:25
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
Afficher la suite 

Votre réponse

18 réponses

Meilleure réponse
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Dernière intervention
5 avril 2013
3
Merci
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.

Merci jmf0 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources a aidé 98 internautes ce mois-ci

Commenter la réponse de jmf0
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Dernière intervention
5 avril 2013
0
Merci
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.
Commenter la réponse de jmf0
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Dernière intervention
5 avril 2013
0
Merci
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...)
Commenter la réponse de jmf0
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Dernière intervention
5 avril 2013
0
Merci
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....
Commenter la réponse de jmf0
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Dernière intervention
5 avril 2013
0
Merci
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à ...
Commenter la réponse de jmf0
Messages postés
2859
Date d'inscription
mardi 15 avril 2003
Dernière intervention
26 novembre 2013
0
Merci
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.
Commenter la réponse de Mayzz
Messages postés
2859
Date d'inscription
mardi 15 avril 2003
Dernière intervention
26 novembre 2013
0
Merci
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.
Commenter la réponse de Mayzz
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Dernière intervention
5 avril 2013
0
Merci
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 ....
Commenter la réponse de jmf0
Messages postés
8
Date d'inscription
samedi 19 février 2005
Dernière intervention
13 mars 2014
0
Merci
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
Commenter la réponse de JeePeeTGI
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Dernière intervention
5 avril 2013
0
Merci
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é.
Commenter la réponse de jmf0
Messages postés
4
Date d'inscription
mercredi 25 mai 2016
Dernière intervention
31 mai 2016
0
Merci
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.
Commenter la réponse de Fusion3D
Messages postés
417
Date d'inscription
vendredi 22 février 2008
Dernière intervention
7 janvier 2018
0
Merci
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



--
Commenter la réponse de CGSI3
Messages postés
4
Date d'inscription
mercredi 25 mai 2016
Dernière intervention
31 mai 2016
0
Merci
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
Commenter la réponse de Fusion3D
Messages postés
18039
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
0
Merci
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.
Commenter la réponse de ucfoutu
Messages postés
4
Date d'inscription
mercredi 25 mai 2016
Dernière intervention
31 mai 2016
0
Merci
Est-que vous pouvez concevoir cela ?
Commenter la réponse de Fusion3D
Messages postés
18039
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
0
Merci
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.
Commenter la réponse de ucfoutu
Messages postés
4
Date d'inscription
mercredi 25 mai 2016
Dernière intervention
31 mai 2016
0
Merci
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 ?
Commenter la réponse de Fusion3D
Messages postés
18039
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
0
Merci
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.
Commenter la réponse de ucfoutu

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.