Forum d'entraide PHPFrance

Bonjour à tous,

Récemment je me suis posé une question, je suis certain que la réponse existe quelque part mais mes recherches sur Google n'ont rien donné. Est-ce que quelqu'un saurait comment joindre plusieurs images de tailles différentes en une grande image en perdant le moins de place possible.

Je m'explique, prenez par exemple cette planche de smilies, disons que je veuille en faire une seule image et je veux que cette image soit la plus petite possible. Si tous les smilies avaient la même taille ce serait facile, il suffirait de faire un carré dont la mesure est la racine carrée du nombre de smilies (un carré de 3x3 s'il y a 9 smilies) ou alors un facteur similaire (4x2 pour 8 smilies, etc...). Mais lorsque chaque image a une taille différente c'est la pagaille Je suis perduadé que cette question a été posée dans des quiz d'algorithmie mais je n'arrive pas à formuler ma recherche correctement chez Google, donc si quelqu'un a une piste je lui en serai très reconnaissant.

PS: ce n'est absolument pas urgent, pour moi ça n'a pour l'instant aucune application pratique, c'est juste théorique

Je serais tenté par une approche du coté d'une largeur moyenne et d'une hauteur moyenne, en ajoutant à ça le nombre d'images et essayer de définir combien d'image je dois mettre en hauteur et combien sur la largeur pour obtenir un carré. À partir de là, il faudrait trouver les combinaisons possibles pour créer des lignes et/ou des colonnes ayant la valeur la plus proche et ainsi déterminer la ligne la plus longue et/ou la colonne la plus longue pour former un carré dans lequel toutes mes images rentrent.

Enfin ça reste une idée

moi j'irais demander ca a des matheux c'est plus dans leur corde, les questions de pavages..

http://les-mathematiques.u-strasbg.fr/p ... st.php?f=2

Ou dans le forum Algorithmes de Developpez.com

Dur dur de connaître le nom de tous ceux qui existent...

Hey ! Y a un matheux sur PHPFrance !!!
Ben oui, c'est moi... Pourquoi ?

Ton problème se classe dans la catégorie "Recherche opérationnelle".
Déjà, ça aidera à affiner sa recherche.

Ensuite, je te propose l'algorithme suivant :

1. calcul de la surface totale = somme des surfaces individuelles
   (10*3) + (3*4) + (7*1) + (2*3) + (3*2) = 61
2. identification des grilles légèrements supérieures ou égales à la surface totale :
   A : 62 = 31 * 2 (ou 2 * 31)
   B : 63 = 9 * 7
   C : 63 = 7 * 9
   D : 64 = 8 * 8
   E : 65 = 5 * 13
   F : 65 = 13 * 5
   etc.
3. élimination des grilles incompatibles
   les grilles A, B, C, D et E sont incompatibles
   car une pièce a une hauteur de 10 et ne rentrera pas.
4. faire des essais avec les grilles restantes

Ça ne résoud pas le problème,
mais ça limite rapidement et efficacement le champ des possibles.

NB : Je suppose que les pièces ont un sens
et donc que leurs hauteurs et largeurs ne peuvent être inversées.

Merci pour toutes ces réponses.

J'ai oublié de préciser que je ne suis pas du tout un matheux, même si j'aime beaucoup les nombres. J'avais pensé au forum de Développez, mais j'ai lu trois topics et je ne pense pas que j'arriverais à exploiter ce type de réponse.

albat, je note précieusement ton truc sur la surface et les grilles, ça a l'air d'aller dans le bon sens Et j'irai creuser Wikipedia pour la recherche opérationnelle.

PS: mon exemple sur les smilies est plutôt pertinent en y réfléchissant, je me demande si on pourrait remplacer tous les smilies statiques par une planche de CSS sprites

Vu sur Zend Developper Zone, ça existe déjà, ça s'appelle ImageMerge et fait partie du framework Kabuki, en Java. Reste plus qu'à convertir ce monstre en... PHP...

Note pour plus tard, Imagick::appendImages est une option potentielle.

Si t'as terminé ton script, ça m'intéresserait bien de le voir. Même si Kabuki l'a déjà fait, on peut le refaire pour optimiser Hehe

Enfin voilà, j'aimerais savoir où t'en es

Il est aussi possible de faire un algo fait maison, par exemple une solution d'algorithme fait maison serait un algorithme d'essais successifs avec élagage par heuristique, c'est à dire tenter toutes les possibilités, mais établir une heuristique pour éliminer les possibilités qui ne peuvent pas être meilleures que la meilleure solution déjà trouvée.
On peut par exemple placer la première pièce en haut à gauche, et la suivante en haut à gauche au dessous de la première ou à droite de la première, etc... En prenant la meilleure solution celle qui minimise la taille de la solution, sachant que l'on a une certaine règle de proportionnalité entre la hauteur et la largeur...

Bref, si tu veux plus de renseignement quant à mon idée, je peux essayer d'élaborer l'algorithme.

Je ne peux que confirmer que c'est bien un problème de recherche opérationnelle.
Ce genre de problème après avoir été formulé sous forme d'une fonction objective et d'une série de contrainte se résout avec un solveur. (par exemple dans excell) qui se chargera de trouver la "meilleure" solution (celle qui prend le moins de place, ici) parmis d'autres.

Je ne peux que confirmer que c'est bien un problème de recherche opérationnelle.
Ce genre de problème après avoir été formulé sous forme d'une fonction objective et d'une série de contrainte se résout avec un solveur. (par exemple dans excell) qui se chargera de trouver la "meilleure" solution (celle qui prend le moins de place, ici) parmis d'autres.

Je ne suis pas d'accord que ca se règle avec un solveur, un solveur n'est pas capable d'optimiser la recherche, parce qu'une telle recherche est de complexité exponentielle, ce qui veut dire qu'avec des tailles de données conséquentes, on fait exploser le nombre de calculs, d'où l'indispensabilité d'une heuristique, donc de développer soi même l'algorithme.
Mais par contre, on est d'accord sur le fait que c'est à priori le seul type d'algorithme qui pourrait donner la solution.

Les programmeurs de Tétris, ils ont pas la solution ?

Ok ok je sors... ----------------> []

Si t'as terminé ton script

Il n'y a pas de script, c'est entièrement théorique, désolé.

Je ne suis pas d'accord que ca se règle avec un solveur, un solveur n'est pas capable d'optimiser la recherche, parce qu'une telle recherche est de complexité exponentielle, ce qui veut dire qu'avec des tailles de données conséquentes, on fait exploser le nombre de calculs, d'où l'indispensabilité d'une heuristique, donc de développer soi même l'algorithme.
Mais par contre, on est d'accord sur le fait que c'est à priori le seul type d'algorithme qui pourrait donner la solution.

Un solveur est tout à fait capable de maximiser ou de minimiser une fonction objective et donc de faire de l'optimisation, tant que le problème connait une solution finie. Comme ici, le but est de minimiser une surface, ça ne devrait pas poser de problème.