Pavage avec des rectangles de taille variable minimisant la surface.

[Linda338]

Bonjour,

J'ignore où je mets vraiment les pieds avec ce problème de géométrie, je cherche un moyen
pour organiser des rectangles dont les dimensions sont aléatoires, pour les agencer de façon à ce qu'ils prennent
le moins d'espace possible dans une surface rectangulaire la plus carrée possible (en minimisant le plus possible
le rapport entre largeur et hauteur)

J'ai bien quelques idées comme classer ces rectangles par taille etc... mais ça semble tout de même compliqué à résoudre.
Je joins une image où j'essaie de le faire manuellement. (j'ai laissé des espaces pour qu'on puisse comprendre l'agencement,
je ne suis même pas sûr qu'il s'agisse du meilleure qui soit)

Le problème me semble assez difficile à chercher sur internet. je vois mal comment trouver une page qui parle exactement
de ce problème à moins d'avoir de la chance, ça ressemble à un problème de pavage ça se rapporte problablement à cette discipline d'ailleurs
mais je n'en suis pas sûr.


j'espère avoir été suffisament clair, merci d'avance pour vos réponses.

-----

[CM63]

Bonjour,

C'est un problème que l'on rencontre dans différentes branches de l'industrie: textile, plastiques, tôlerie, chaque fois qu'on veut découper des surfaces données dans une grande surface. Le plus dur est de trouver les mots clef pour trouver de la doc là dessus. En plus, certains de ces algorithmes sont peut-être brevetés (non pas comme algorithme puisque ce n'est pas possible en France, mais comme procédés).
Je vais regarder un peu.

[tchitchou]

Bonjour à tous, les mots clefs, ça va être
optimisation découpe
calepinage,
il existe des logiciels qui font.

[CM63]

Bonjour,

J'ai vu ici un solution , peut-être pas la meilleure, mais qui a le mérite d'être relativement simple:
- on commence par classer les petits rectangles dans l'ordre croissant de surface,
- ensuite on les pose dans cet ordre sur la grande surface, en essayant à chaque fois les deux possibilités de pose ("horizontalement" et "verticalement")

Avec cet algorithme on ne serait pas arrivé à la solution que tu donnes pour ton exemple, puisque des rectangles plus petits sont posés après des plus grands. Donc il y a certainement moyen de trouver mieux.

A plus.

[A voir en vidéo sur Futura]

[Linda338]

Merci à tous

Effectivement, j'ai tout de même réussi à trouver un documents qui en parlait hier (une thèse de doctorat, c'est un peu décourageant) et c'est bel et bien ce domaine d'optimisation
de découpe qui traite le plus du sujet. En même temps, moi, c'est pas pour de la découpe et je vois mal pourquoi des ingénieurs industriels pourraient vouloir absolument centrer leurs rectangles.
mais c'est inspirant. bon, dans quarante ans je reviens avec la solution (si la terre est toujours là)

[tchitchou]

Si tu gougles "gratuit optimisation découpe", tu tombes sur des softs qui font ça... gratuitement, donc.

Je suis mal à l'aise pour en proposer, parce que je n'en ai essayé aucun, mais ça existe, ça est sûr.

[Linda338]

merci,
en fait je cherche vraiment un algorithme pour pouvoir l'intégrer dans un autre programme.
c'est pour ça qu'un logiciel ne m'intéresse pas vraiment dans ce cas, même si je suis persuadé qu'ils doivent très bien le faire.

[CM63]

Bonjour,

Une autre suggestion:
- classer les rectangles dans l'ordre croissant des largeurs,
- les empiler horizontalement
- les classer dans l'ordre des longueurs et voir si l'empilement vertical est meilleur

A plus.

[Linda338]

Bonjour, je redéterre un peu le sujet. Bon il est évident qu'avec mes connaissances actuels. Je ne résoudrais jamais ce problème , il est hors de ma portée. Cela dit je trouve que c'est passionnant d'y réflechir et par exemple j'aurais voulu savoir s'il existait des méthodes bien connues pour simplement vérifier que ces rectangles sont contigus sans se chevaucher. Parvenir à solutionner ce problème serait déjà beaucoup pour moi.
Je pourrais "brutalement" vérifier pour chaque rectangle venant s'ajouter à la construction géométrique qu'il n'y a pas de chevauchement avec ceux qui sont déjà présent. J'aurais alors un processus simplement itératifs. L'ennui c'est que j'ai beaucoup de rectangles à positionner (512) dans ce cas, le nombre de test devient vite énorme. Quelqu'un a une idée ? Merci d'avance

[CM63]

Bonjour,

...vérifier que ces rectangles sont contigus sans se chevaucher.

Etant donné que les rectangles sont disposés horizontalement ou verticalement, mais jamais en biais, cela doit être relativement simple. Il suffit de stocker leurs positions et de les comparer.

A plus.

[Kissagogo27]

Bonjour, perso je ferais l'inverse , classer du plus grand au plus petit, et commencer par placer un grand, puis en tournant, classer la liste du plus grand au plus petit ... mais comme il existe 2 possibilités hauteur ou largeur on peut arriver a un blocage avec l'impossibilité de placer la pièce suivante ... il faut donc garder la possibilité de remonter la liste pour changer la position du plus grand possible ( si possible ) et relancer le placement ...

ensuite il faut décider soit de peupler les coins en premier, soit de les mettre a la suite bord par bord . . .
après décider le bord a bord pour test, ou avec marge de découpe avec l'épaisseur de l'outil etc etc ..

pour le test de chevauchement, il faut forcément une carte en mémoire de la zone a remplir, des emplacements pris , des emplacements libres , donc une routine avant chaque placement qui détermine le premier point libre d'une zone en X et Y , soit en tableau, ou graphiquement ...

l'important c'est la méthodologie, ensuite ça ne reste qu'une astuce de programmation .