Création d'un logiciel sur le principe de TETRIS

[invite12449f59]

Bonjour,

Voilà le challenge à résoudre:

D'un côté une surface,celle d'un mur: hauteur/longueur
ex: 3,50m x 2,70m

De l'autre: 114 formats différents de toiles sur châssis (considérons les comme des figures géométriques carrées ou rectangulaires)

Comment en entrant les données de surface d'une part et les 114 formats d'autre part obtenir toutes les combinaisons possibles pour couvrir le mur?
Merci aux programmeurs qui voudront bien se pencher sur ce problème que je dois résoudre pour lancer un nouveau concept déco.
-----

[bzh_nicolas]

Une fonctions récursive me semble le plus adapté.

[invite12449f59]

Merci tout d'abord de vous interesser à mon problème.Reste qu'il me faut à présent comprendre ce qu'est une fonction récursive...Et ce que j'en fais.

[DomiM]

Pour ajouter un tableau sur le mur on peut faire comme si on écrivait un texte
En gros ça serait ça avec quelques test suplémentaire

ym=2,7
do 
  ym=ym-EcritLigne(3,50)
while ym>0

Function EcritLigne(d)
  ym=0
  for i=1 to 114
    if f[i,0]<d then
      d=d-f[i,0]
      if ym<f[i,1] then
        ym=f[i,1]
      endif
      ajouteTableau(i)
    endif
  next i
  EcritLigne=ym
End function

[A voir en vidéo sur Futura]

[Philou67]

J'aurais tendance à penser que ce problème relève de la recherche opérationnelle, et qu'un algorithme glouton me semblerait adapté.

Au retour de la pose café, j'essayerai de proposer une algorithme (mais à priori, c'est un problème classique de placement et d'optimisation : il existe sans doute un algorithme bien nommé pour cela).

[invite12449f59]

Merci tout d'abord aux membres dont la réactivité à ma question m'impressionne. A la lecture de vos réponses je me dis qu'un point qui n'est pas de détail vous aura peut être échappé.Chacun son job et la programmation n'est pas le mien.Je fonctionne à l'intuition et en inventant ce concept (à mi chemin entre l'art contemporain,la muséographie et l'architecture intérieure) je n'avais qu'un seul mot à ma disposition: algorithme.Lequel,comment,aucu ne idée...Mais une fois créé l'outil de calcul les applications (avec leur aspect très ludique et créatif) pourraient se révéler passionnantes,notamment du point de vue des rapports colorés (la perception rétinienne de chaque couleur étant influencée par celles qui l'entourent (théorie de Chevreul dont les pointillistes et tout l'art abstrait du XXème se sont inspirés).Bon je ne m'étends pas sur l'histoire de l'art,encore une fois chacun son job. Ce qui est certain c'est qu'il s'agit en effet d"un problème classique de placement et d'optimisation". Ce qui est non moins certain c'est que la rencontre entre l'art et la science est un enjeu passionnant à mon sens.

[DomiM]

On sait que le plan peut être pavé par les format An (A4,A3,A2,A1,A0)
donc en centrant chacune de vos toiles sur le format An le plus proche le problème se simplifie

[Philou67]

J'en viens donc à mon idée d'algorithme glouton (heuristique) : l'idée principale est de tenter de placer les plus grosses pièces en premier. Chaque pièce posée découpe l'espace disponible en deux, créant ainsi deux espaces rectangulaires disponibles à remplir.
Si l'on considère que les œuvres d'arts n'ont pas de sens de visualisation, on peut considérer que l'espace peut être découpé selon deux sens (donc récursivement, si l'une des voies ne donne pas de résultat, il faudra explorer l'autre).
De même, il existe 4 possibles de placement, à chaque coin de l'espace. On pourra soit explorer les 4 voies, soit ne considérer que le placement en haut à gauche.

pieces[114] = (...) // renseigner les 114 pièces
espaces[] = (...)   // renseigner l'espace disponible
placements[] = ()
Trier le tableau pieces[] par ordre de taille décroissant (critère : soit la surface, soit une critère à deux clés : largeur puis hauteur)
Appeler Placer(pieces, espaces, placements)

function Placer(pieces[], espaces[], placements)

Si pieces est vide
  Afficher "Solution", placements
Sinon
  Pour espace parmi tous les espaces[]
    Si la pièces[0] tient dans espace
      placements[] <- pièces[0]
      supprimer pièces[0]
      remplacer dans espaces[], espace par 2 espaces résultant du découpage horizontal suite au placement
      Appeler Placer(pièces, espaces, placements)
      remplacer dans espaces[], les 2 espaces précédent par 2 espaces résultant du découpage vertical
      Appeler Placer(pièces, espaces, placements)
    Finsi

  Pour espace parmi tous les espaces[]
    Si la pièces[0] tournée à 90° tient dans espace
      placements[] <- pièces[0] tournée à 90°
      supprimer pièces[0]
      remplacer dans espaces[], espace par 2 espaces résultant du découpage horizontal suite au placement
      Appeler Placer(pièces, espaces, placements)
      remplacer dans espaces[], les 2 espaces précédent par 2 espaces résultant du découpage vertical
      Appeler Placer(pièces, espaces, placements)
    Finsi
  FinPour
Finsi

Je ne suis absolument pas sûr que cet algorithme soit correct, et surtout qu'il donne une solution.

[invite12449f59]

3 cas de figure peuvent se présenter. Dans le 1er et le 2nd cas,le sens de visualisation est à prendre en compte (vertical ou horizontal),dans le 3ème cas,aucune importance.
1er cas: Accrochage de n oeuvres à optimiser sur un panneau (exploitation muséographique ou galerie)
2ème cas: insertion d'une ou plusieurs oeuvres dans le "tetris" (le reste du mur étant couvert de n toiles monochromes). A noter que les oeuvres signées comme les monochromes qui les entourent sont toujours réalisés sur des chassis standard (parmi les 114 formats existants).
3ème cas: Le mur est uniquement composé de chassis monochromes (de différentes couleurs). Dans ce cas pas de sens d'accrochage requis.
J'ai scanné 2 petits croquis qui vous permettraient de visualiser la chose mais pour l'instant je n'ai pas trouvé l'option me permettant de les joindre.
Sur le mur qui m'a servi de test il y a dix formats différents.En l'ocurrence:
6 chassis 50x50
3 chassis 50x100
2 chassis 70x 100
1 chassis 100x100
2 chassis 40x120
1 chassis 40x50
1 chassis 30x40
4 chassis 50x65
1 chassis 10x15
2 chassis 15x15

Parmi les n options possibles: remplacer par exemple le 50x50 par 25 10x10. ou partiellement 16 10x10 par 4 20x20,etc,etc...Combien de combinaisons possibles pour une surface donnée? Il faudrait que je puisse vous communiquer les dimensions des 114 formats pour tester. En tout cas encore merci pour votre intérêt.