Algo / à des coordonnées géo et poids de fichiers..
Bonjour,
J'ai un problème qui, je pense, n'est pas simple du tout... il y a déjà plusieurs manieres de le resoudre et je n'ai surement pas pensé à chacune.
C'est un script en Perl.
Voici ce que je souhaite:
J'ai une série (non finie) de rectangles représentant des images (des cartes!). Les rectangles sont localisés avec des coordonnées X;Y (à chaque coin).
Je connais la taille (en Mo) de chaque carte.
Le but est de préparer intelligemment une compilation sur un support tel qu'un CD ou un DVD, à savoir regrouper au mieux les cartes de façon homogène (quant à leur localisation).
1/ Idée1: Pour chaque nouveau CD, partir d'une carte, chercher les cartes les plus proches, autour, et continuer jusqu'à atteindre la limite du CD, puis prendre une autre carte et refaire la même chose. Le problème: à mon avis l'algo ne pourra pas être des plus rapides et j'aboutirai, à la fin, à ramasser des miettes (des cartes éparpillées).
2/ I2: Considérer chaque rectangle comme un point (le centre), et partir de bas en haut et de gauche à droite (on croit en Y et en X). Je vois à peu près comment faire l'algo de façon pas trop lente, je pense, mais je n'aurai pas un beau résultat car jamais les points ne seront nettement alignés (sur l'axe principal des Y) et donc des cartes proches entre elles, mais dont les points centraux ne sont pas colinéaires, risquent fort de ne pas se retrouver sur le meme CD. Je risque d'avoir un carte au Sud, un gros trou, une au nord, puis sur un nouveau CD une carte plus nord que la toute première mais tout de meme tres proche en X....
==> La capacité à optimiser le stockage sur CD est importante car c'est très souvent des Go de fichiers à organiser (fichiers allant de 20 à 120Mo en general).
Bref, je ne sais pas si je suis clair (j'essaie)... si mon prob vous intéresse, si vous avez des conseils, des idées, des questions, je suis preneur.
Bonne journée.
1 pièce(s) jointe(s)
Ca fonctionne, merci bcp :)
Reste à voir si ça donne un bon résultat dans tous les cas de figure, mais pour ce que j'ai testé, c'est plutôt réussi et efficace.
Actuellement:
-Je met toutes les cartes dans une liste generale.
-Je boucle tant que cette liste 'generale' contient des cartes:
-Je met toutes les cartes de la liste generale dans une nouvelle liste d'attente
-J'initialise une liste de média avec pour premiere carte la carte la plus en haut à gauche, en retenant le point centroide.
-Nouvelle boucle tant qu'on a des cartes en liste d'attente et tant le média n'est pas à sa capacité max:
-Je cherche la carte la plus proche du dernier point centroide retenu. Si je peux l'ajouter sans dépasser la capacité du média, je l'ajoute dans la liste du média et la supprime de la liste d'attente.
Lorsque j'ai atteint la capacité max, j'enregistre la liste média (fichier) et je soustraie les cartes qu'elle contient de la liste 'generale'.
Retour à la premiere boucle.
Voici ce que ça donne:
Le plus grand polygone est la zone capturée.
Les rectangles sont les cartes.
Les points les plus à gauche sont le CDn1 obtenu avec cet algo
Les pts du milieu, le CDn4, de droite le CDn7 (dernier).
Pièce jointe 1989
===
Les CD sont bien equilibrés... le seul inconvénient, peut-etre, est que ça crée un genre de 'cheminement' des cartes au lieu de prendre toute une zone 'circulaire'.
J'ai compris pourquoi, il faudrait, au lieu d'aller de proche en proche, chercher dans la 2è boucle la carte la plus proche du point le plus en haut à gauche... ainsi, je pense avoir des groupes de cartes plus jolis.
Si qqun a suivi, pensez-vous que j'aboutirais avec un dernier CD homogène (et pas ramasser des miettes) ?
Bonne journée.
1 pièce(s) jointe(s)
Amélioration de l'algo de répartition....
Bonjour!
Voici ce qu'on j'obtiens avec mon algo actuel:
Pièce jointe 2349
L'image ci-dessus est générée à la fin de l'algo pour afficher sa route.
On voit relativement bien sa logique.
Chaque CD est identifié par une couleur, le premier CD est celui le plus en haut à gauche de l'ensemble.
Le départ d'un CD est matérialisé par un point.
C'est globalement satisfaisant, mais sur ce cas de figure on remarque que certaines emprises seraient mieux placées dans le dernier CD qui n'est pas completement rempli.
J'ai donc pensé à un algo qui effectuera une seconde passe que je decris ci-dessous, mais il me manque pour cela une formule mathématique que je ne trouve pas:
comment calculer un centre de gravité (est ce vraiment cela?) de chaque groupe (CD) en tenant compte de la densité dans la répartition.
Je m'explique, pour le CD n°6 par exemple, le fait que la plupart des emprises se situent dans la partie nord devrait faire que mon centre de gravité soit attiré vers le nord, et ne soit pas simplement en plein centre (centroïde) des emprises extérieures (rectangle ou cercle minimum englobant l'ensemble des emprises).
Mon idée (pas encore testé) d'algo pour la seconde passe:
Code:
1 2 3 4 5 6 7 8 9 10
|
1 - Initialisation de l'algo
Calculer le centre de gravité (CG) de chaque groupe (tenant compte des densités)
2 - Boucle sur chaque groupe
<div style="margin-left:40px">2.1 - Trier les emprises (centroïdes) du groupe du plus éloigné du CG du groupe vers le plus rapproché.
2.2 - Boucle sur la liste des emprises triées par éloignement
<div style="margin-left:40px">2.2.1 - Sélectionner dans une liste de candidats les groupes dont le CG est plus proche de l'emprise que le CG du groupe actuellement proprietaire de cette emprise ET qui peuvent la recevoir (d'apres la contrainte de taille, soit la place qu'il reste dans le groupe)
2.2.2 - Trier les candidats obtenus par capacité disponible (le groupe le moins volumineux en tête de liste).
2.2.3 - Si on obtient un candidat (1er de la liste précédemment triée), déplacer l'emprise dans ce groupe et réinitiliser l'algorithme (-> 1)</div></div>
Fin quand plus aucun déplacement. |
Je pense qu'une fois codé, ça devrait resoudre le cas décrit par l'image.
Par contre, ça ne resoudra rien lorsque les groupes à proximités seront remplis à bloc... et là... je ne vois aucun moyen pour ce cas.
Si vous avez des remarques/conseils... et surtout si vous avez cette petite formule pour le centre de gravité :)
je vous en remercie.
Bonne journée.