Discussion :

[Chekov]

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.

[Graffito]

Bonjour,

Je me baserai sur l'idée1 :

Pour choisir la carte de départ d'un CD, choisir la carte qui a le plus de contiguité avec les CD déjà créés (on compte le nombre de CD contigus).
Pour choisir les cartes suivantes du CD, choisir parmi les cartes contigues à celles du CD en cours celles des carte qui a le plus de contiguité avec les CD déjà créés.

Avant de démarrer, on définit, comme un CD déjà créé, un CD avec des cartes virtuelles representant les bords extérieurs de la zone.

Critère additionnel pour départager des ex-aequo : choisir la carte la plus éloignée du centre.

sauf gros écarts de latuitude ou près des poles, La contiguité devrait pouvoir se définir par une fonction assez simple de comparaison des coordonnées des centre :
Contiguité= (|X2-X1|<= (largeur max d'une map x 1.3)) ou (|Y2-Y1|<= (hauteur max d'une map x 1.3))

[Chekov]

Rebonsoir,

Merci pour cette réponse rapide. Ca me parait une bonne piste...
par contre, - je fais peut etre erreur, je ne suis pas un matheux - mais la formule de la fin ne me parait pas adapté à mon cas de figure:

Contiguité= (|X2-X1|<= (largeur max d'une map x 1.3)) ou (|Y2-Y1|<= (hauteur max d'une map x 1.3))

Je serai en effet rarement proche des poles (et jamais tout pres: de l'ordre lat < 70° dans tous les cas).
Par contre, ma zone contenant les cartes n'est pas totalement recouverte de cartes. Donc je pense que "largeur max d'une map x 1.3" n'est pas le mieux à faire.... je me trompe?

[Graffito]

Bonjour,

Si la carte est pas totalement recouverte de map, il faudrait la "compléter" par des maps de taille nulle qui rempliraient les trous.

Pour la formule, j'ai suppposé que les maps étaient approximativement toutes de même taille.

Le facteur 1.3 est plutot à titre d'illusrtration. De façon plus rigoureuse, les 2 cartes seront contigues si la différence des coordonnées des centres des 2 maps contigues est comprise entre la difference maximum et 2 fois la difference minimum.

[Chekov]

Mmh je vais essayer avec cette base là. Sauf que je ne vais pas parler de contiguité car ca me parait bien compliqué de remplir la zone de cartes nulles sachant que les cartes n'ont pas toutes la meme taille (ca peut varier pas mal, et je cherche un algo qui s'adapte au max de situations).

Mais le principe de proche en proche sera pas mal je crois, en revenant des qu'un CD est complet au point le plus en haut à gauche des cartes restantes (si le premier CD part de la carte la plus proche du point le plus en haut à gauche de la zone couvrant les cartes).

Ca parait correct comme ca ?

[Chekov]

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).


===
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.

[Graffito]

Bonjour,

Pour le problème des m"miettes", je reviens sur :

-Je cherche la carte la plus proche du dernier point centroide retenu.

Il me semble qu'il faudrait quand même faire un choix plus subtil parmi les plus quelques cartes les plus proches à savoir prendre en priorité une future miette. La probabilité d'être une miette me sembe être à l'inverse du nombre de carte proches dans la liste d'attente.

[Chekov]

Il me semble qu'il faudrait quand même faire un choix plus subtil parmi les plus quelques cartes les plus proches à savoir prendre en priorité une future miette. La probabilité d'être une miette me sembe être à l'inverse du nombre de carte proches dans la liste d'attente.

Il faut que je fasse plus d'essais, mais l'interprétation est encore assez longue, donc je vais commencer par faire un export graphique du resultat final pour ensuite tester les différents cas.

J'ai essayé avec la seconde methode dont je parlais un peu avant: au lieu de prendre le dernier point (la derniere carte ajoutée), je conserve pour reference le point HG. Le résultat est plus joli je trouve, mais j'ai conservé les deux possibilité car l'une et l'autre donnent des resultats satisfaisants.

A priori, je ne pense pas avoir de miettes si ma référence est toujours le point HG car si une carte passe au travers à un passage, elle sera prise au suivant.
(je ne sais pas si c'est clair.... ).

La subtilité à laquelle je pensais était pour optimiser encore mieux l'expoitation de l'espace de stockage: actuellement, j'ai 2 fonctions importantes:
La principale, "creer_compilation()", qui contient les 2 boucles (celle qui tourne tant qu'on a des cartes, et celle qui tourne tant qu'il reste de la place sur le CD).
On recupere la carte la plus proche du point de reference (soit le point HG ou la derniere carte capturée, selon ce qu'on parametre) et si elle rentre sur le CD, on l'ajoute. Sinon on arrete le CD et on en cree un nouveau.

Et "index_point_le_plus_proche(point_xy,profondeur_int,liste_array).
Cette derniere trie les centroides liste_array par proximite croissante par rapport à point_xy, et renvoit ensuite l'index (initial de la liste_array) correspondant à la profondeur demandée.
CàD:profondeur 0 est l'index du centroide le plus proche de point_xy.
prof 1, le deuxieme centroide le plus proche, etc...

Pour le moment, profondeur est toujours 0.

Je songeais, au moment du test si la carte capturée ne rentre pas sur le CD courant, incrementer la profondeur successivement jusqu'à trouver une carte qui rentre sur le CD (les cartes pouvant avoir des poids très differents entre elles).
Mais la manière dont l'implémenter n'est pas encore tout à fait claire dans ma tete... (... ce type de prog est assez nouveau pour moi).
Bien sur, en faisant cela, on perd en homogénéité des zones, mais l'optimisation des CD peut etre un critere important (bien sur, configurable).

Il faut que je trouve où inclure ma boucle pour tester les différentes profondeurs dans ceci (c'est du Perl, mais je pens eque c'est comprehensible avec les commentaires):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
	while (il_reste_des_cartes_non_compilees) {
	$index_media++;
	my $occupation_media = 0; # Espace occupé (/ $capacite_media=640Mo)
 
	# On commence par créer les listes de traitement (centroides ("x y"), nom carte (dataset), poids (Ko)).
	my @liste_centroides;
	my @liste_datasets;
	my @liste_poids;
	my @media; # Liste receptrice compilée
 
		foreach my $ds_a_compiler (keys %zone_totale) { 
# On ajoute ayux listes de traitement les datasets restant dans %zone_totale
# Chaques groupe (poid,nom,centroidie) a le meme index dans les 3 listes.
		} # Fin foreach
 
	my $point_de_reference;
	my ($index) = &index_point_HG(@liste_centroides); # Recupere le centroide le plus en haut à gauche
 
	# Deplace le premier element dans le nouveau media.
	push @media, "$liste_datasets[$index];$liste_centroides[$index];$liste_poids[$index]";
	$point_de_reference = $liste_centroides[$index]; # Conserve la trace du dernier centroide ajouté au media (le plus Haut Gauche)
 
	$occupation_media += $liste_poids[$index]/1024; # Maj de l'occupation du media
 
	# [ Je Retire l'element des listes de traitement ]#
 
	# Cette boucle va créer le média n°$index_media (nouvelle compile) avec les datasets restants, jusqu'à atteindre $capacite_media.
 
		while (($occupation_media < $capacite_media) && (il_reste_des_cartes)) {
 
		# Il s'agit maintenant de récupérer le prochain point de @liste_centroides le plus proche de $point_de_reference
 
   # C'est ici qu'intervient ma profondeur (=0: 1er point le plus proche)
		my($index)=&index_point_le_plus_proche($point_de_reference,0, @liste_centroides);
 
 
		# On a la carte suivante la plus proche. Il faut s'assurer qu'on dispose de la place sur le media pour l'ajouter:
			if ($occupation_media+($liste_poids[$index]/1024) <= $capacite_media) {
			print "Ajout au media courant\n";
			# On ajoute la carte
			push @media, "$liste_datasets[$index];$liste_centroides[$index];$liste_poids[$index]";
			$occupation_media += $liste_poids[$index]/1024; # Maj de l'occupation du media
 
				if ($config{strategie} eq "2") { # Strategie 2 ('centrée')
				#$point_de_reference = point HG de la compile; ON NE MODIFIE PAS LE POINT DE REF SI ON VEUT CENTRER (ce sera le point HG initial de la compile)
				} # FIn if
				else { # Strategie 1 ('proche en proche')
				$point_de_reference = $liste_centroides[$index]; # Maj du dernier point. ("x y")
				} # Fin else
 
 
			# [ Retire l'element des listes de traitement ] #
 
			} # Fin if AJout
 
			else { # Plus de place (sans gestion de profondeur)
			# On considere le cd rempli
			$occupation_media = $capacite_media; # Pour sortir de la boucle
			} # Fin else
 
 
		} # Fin while
 
	print "La compilation $index_media vient d'etre cree!\n";
 
	# J'enregistr @media dans un fichier et je retire ses cartes de la liste %zone_totale (toutes les cartes restantes).
 
	} # Fin de while generale (tant qu'il reste des datasets à compiler

Voilà...

[Graffito]

Bonjour,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

optimiser encore mieux l'expoitation de l'espace de stockage

.
A priori, je dirai que ce serait au détriment du groupage par zone.

On pourrait être envisager un système de permutation entre 2 CD qui échangerait des maps sur la "frontière" des CD. Cela permettrait de mieux "remplir" le CD le plus plein et de libérer plus de place dans l'autre.
mais j'ai du mal à imaginer l'algo travaillant sur l'ensemble des CD .

[Chekov]

Ca me parait limité en effet... mais dans la plupart des cas, le plus important sera de stocker sur le moins de CD possibles... meme si c'est au detriment de l'organisation des cartes. Celle vient en seconde priorité.

Effectivement, ce que tu dis pourrait tourner à la fin, lorsque tous les CD sont créés, un algo cherche le CD le moins rempli, et cherche de la place pour déplacer chaque carte sur les autres CD.... si on arrive à vider 1 CD comme ca, c intéressant, sinon, on ne change rien. Je vais ajouter ça, ce n'est pas bien compliqué.

[chebreg]

Je ne sais pas pour quoi. mais en lisant le problème, j'ai pensé à l'algorithme des K-means (en bon français : la classification automatique par nuées dynamiques).

cette algorithme permet de constituer des groupes (K groupes) en utilisant une fonction de distance.

en grosomodo l'algorithme se déroule ainsi :
[ N élément; K groupe; K noyaux (les noyanus sont les centre du groupe); Distance(fonction qui calcule la distance entre un élément et un groupe) ]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
1- Constitué aléatoirement K groupe à partir des éléments disponibles
2- calculer le noyau de chaque groupe
3- Initialiser le compteur de changement
4- pour chaque Groupe faire
        pour chaque Element du groupe faire
          * affecter l'élément au plus proche groupe Trouvé
          * si l'élément change de groupe Incrementer le compteur de changement
        fin pour
    fin pour
5- Si le compteur de changement dépace un seuil alors Aller à 2

tu peut utiliser une variante de cet algorithme en combinant la fonction distance avec la contrainte "capacité du groupe" et avoir qq chose d'intéressant.

et bonne chance pour ton prob.

[Chekov]

Merci, je regarde ça et je testerai un algo sur cette base pour voir la différence avec celui que j'ai déjà.
J'avais vaguement pensé à qqchose comme ca avant de commencer, mais je ne connaissais pas ce domaine.

[Chekov]

Bonjour!

Voici ce qu'on j'obtiens avec mon algo actuel:


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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Chekov]

La formule que je cherchais etait toute bete, c le centre de gravité, ou barrycentre (je crois), soit la moyenne de tous les x et y.

J'approche du but, mais g encore qq bugs à corriger.