Discussion :

[sidahmed]

Bonjour,

j'ai une surface en verre de dimension L * H, et je veux découper des morceaux rectangles de tailles différentes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Une surface à découper de taille L / H cm
 
n morceaux à découper :
rectangle 1 : l1 / h1 cm,
rectangle 2 : l2 / h2 cm,
...
rectangle n : ln / hn cm.

Comment je dois découper cette surface afin de réduire les chutes au minimum, sachant que chaque découpe se fait de bout en bout ?

Merci d'avance.

Cordialement,
Sidahmed.

[CedricMocquillon]

Bonjour, tes deux posts (celui-ci et le précédent) sont tout deux lié au problème de bin-packing (tes cadres correspondent au cas 1d et tes rectangles au cas 2d).
http://fr.wikipedia.org/wiki/Probl%C...de_bin_packing
C'est un problème NP-Difficile, il n'existe donc pas d'algorithme polynomial qui te donnera la solution optimale.

[alex_pi]

Bonjour,

j'ai une surface en verre de dimension L * H, et je veux découper des morceaux rectangles de tailles différentes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Une surface à découper de taille L / H cm
 
n morceaux à découper :
rectangle 1 : l1 / h1 cm,
rectangle 2 : l2 / h2 cm,
...
rectangle n : ln / hn cm.

Comment je dois découper cette surface afin de réduire les chutes au minimum, sachant que chaque découpe se fait de bout en bout ?

Merci d'avance.

Cordialement,
Sidahmed.

Qu'est ce que tu entends par réduire les chutes au minimum ? Parce qu'on peut prédire directement et exactement la surface de chutte (si tu parviens à effecture le découpage), puisqu'elle vaut
L*H - \Sum li*hi
Faut il minimiser le nombre de chute (ou ce qui revient au même, maximiser leur surface moyenne), ou même jouer sur l'écart type (typiquement, on peut préférer une chute de 49cm² et une de 1cm² à deux chutes de 25, ou pas :-p)

Bref, il me semble que le problème est mal posé (mais pour répondre à Cédric, c'est plus un problème de pavage de surface que de bin-packing)

[sidahmed]

Oui, c'est clair que la surface restante c'est L*H - la somme des surfaces des morceaux découpés.

il faut réunir au maximum les chutes !

[FrancisSourd]

C'est le problème de découpe 2D guillotine (2D Cutting Stock Problem), je te laisse faire du google là-dessus...

Une applet (trouvée mais non testée)
http://www.applicationprogram.net/glop21ns.aspx

[patmandrum]

Bonjour,
si vous avez à réaliser un grand nombre de découpe de verre de dimensions rectangulaires vous pouvez optimiser vos découpes avec un logiciel de découpe de verre (découpe 2D guillotine spécialisé dans la découpe du verre).
http://p.rozet.free.fr/FR/PV/vitragepro-pv1.php