Voici mon problème : j’ai plein d’images de formes rectangulaires, et je cherche à les regrouper de la façon la plus optimale possible en une seule grosse image, elle aussi rectangulaire… Par “façon la plus optimale possible”, j’entends “en minimisant la surface totale inutilisée”.
Alors forcément j’ai quelques idées pour le faire moi-même, mais je me dis qu’un problème aussi générique a sûrement déjà dû intéresser des gens bien plus compétents que moi. Donc j’aimerais bien trouver des travaux là-dessus. Mon principal problème étant que je ne parviens pas à décrire le problème suffisamment bien que pour que Google me vienne en aide.
Au cas ou le problème deviendrait très complex et le nombre de solution possible infini ou presque tu peux toujours chopper un algorythme génétique.
Il y a plein de lib en Java et C que j’avais trouvé pour mon travail de fin d’étude.
Maintenant faus les essayer et toujours savoir parfaitenement définir ton problème et savoir résumer les performances en un seul nombre.
C’est assez puissant mais faut quand même faire gaf que ce soit pas surdimensionner comme solution par rapport à ton problème
Mais non mais non, un truc bien deterministe suffit largement pour obtenir une solution. De la a prouver qu’elle est optimale c’est une autre histoire mais dans un probleme a deux dimensions comme ca, ca casse pas trois pates a un canard comme on dit
megar : merci pour les liens, ça s’approche un peu de ce que je cherche à faire, mais la différence est que les images dont je dispose ont une taille bien définie, ils ne sont pas redimensionnables.
glop : j’ai du mal à saisir ce que tu veux dire… si tu es ironique parce que le problème est très dur, je précise que je cherche juste à approcher une “bonne” solution, pas une solution optimale… si par contre le problème te paraît très simple, c’est qu’on a pas du bien se comprendre, donc j’explique un peu mieux :
disons que j’ai n rectangles :
rec 1 : 65 x 78
rec 2 : 142 x 24
rec 3 : 50 x 90
…
rec n : 73 x 100
je cherche le plus petit rectangle (en surface) qui me permette d’y ranger tous les autres, sans chevauchement
ton pb est assez repandu en ingenieurie…(err on va dire Industrial Engineering).
Je te propose de chercher au rayon " bin packing algorithm". Ca a beaucoup d applications dans des domaines tres different (chargement, optimnization d espace au sol, capacity scheduling …)
un coup de google te renverra certain mots clef et des liens/soft (pas de pub):
Il y a une tres abbondante litterature sur le sujet. Si tu veux, je peux essayer de retouver un bouquin.
De memoire, ce sont des algos heuristic ( donc l’optimalite est a prouver, mais a -20% de l optimal tout le monde est content)
Une approche est de commencer a placer les plus gros bloc et de completer par les plus petit.
Un autre, si il ya une relation entre les photos de proche en proche,se base sur la theorie des graphes et les manipulation de matrices qui font avec.
J’espere que sa te donnera des directions et des idees.
Ouaip, tu trouveras ton bonheur en Recherche Opérationnelle, normalement… C’est effectivement une variante des “sacs à dos”. Pour simplifier la modélisation de ton problème, n’oublie pas que chaque image a une seule orientation possible (contrairement à un pavé par exemple). Ce message a été édité par xentyr le 02/09/2004
L’imprimerie a aussi recours à ce genre d’algo de façon optimiser le nombre de “planche” à utiliser pour l’impression de différents motifs. La planche étant de taille fixe.
Un des moyens est de parcourir toutes les solutions avec un algo récursif. “Simple” et efficace.
Si tu cherches une solution approchée tu peux utiliser des algos comme le recuit simulé (simulated annealing). Il a l’avantage d’être simple à implémenter et on peut fixer le nb d’itérations. Après tu vas en ch… pour trouver une fonction d’éval et les systèmes de voisinage, mais ça doit être possible. Sinon y a des méthodes comme les algos évolutionnistes et les algos génétiques qui marchent bien.
Pour le fun, tu peux tester les algos comme les colonies de fourmis et essaims particulaires.
Excellent ! Merci à tous, j’ai trouvé une énorme quantité d’articles qui parlent d’algorithmes me permettant de faire ce que je veux. En fouillant un peu dans tout ça, je devrais trouver un bon compromis entre complexité d’implémentation et qualité du résultat.
Bah euh moi j’aurai utilisé un bête quadtree, avec un système permettant d’optimiser éventuellement l’ordre dans lequel les blocs sont placés histoire de trouver un ordre assez proche de l’idéal…
Ca a le mérite d’être ultra simple, ultra rapide, et pas si loin d’une solution optimale (même si c’en est clairement pas une).
'fin bon ça me semble archi proche d’un cache texture en VRAM (coucou la PS2), et pour ça un quadtree, c’est bien.
[url="http://does.eng.buffalo.edu/publications/publications/DETC99_DAC-8588.pdf"]AN EXTENSION OF THE ORTHOGONAL PACKING PROBLEM THROUGH DIMENSIONAL FLEXIBILITY [/url][/quote]
