Discussion :

[spocky]

Bonjour à tous,

Je suis bloqué sur un projet personnel et c'est assez énervant !
J'essaye de déterminer la position optimale d'un centre pour soigner des patients grâce à une carte qui me donne une répartition de la population.
Cette carte m'indique 6 couleurs. Pour chaque couleur, elle me donne un nombre d'habitant par KM2.
J'aimerais placer un centre dans une région qui contient au moins 20 000 000 d'habitants.
Pour ce faire, j'ai pensé à une méthode qui me diviserait à chaque fois en 4 mon image et qui recalculerait si de nouveaux 20 000 000 d'habitant sont présents dans cette zone.

EX : Je parcours mon image à l'aide de deux boucles :

Code :

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

1
2
3
4
5
6
7
8
For i : N
    For j : M
        Somme des valeurs des pixels (en fonction de la couleur)
    End
End
if (Somme >= 20 000 000)
    Division de l'image en 4 
End

Réitération des deux boucles pour recalculer la somme et vérifier si le nombre d'habitant excède 20 000 000 ou non.
Si les 4 nouvelles images ont moins de 20 000 000 habitants, le centre sera placé au milieu de l'image avant division.
Si une ou plusieurs images ont plus de 20 000 000 habitants, alors le processus se répète dans l'image où les images concernées.

J'ai eu des résultats, mais avec une méthode laborieuse en incluant de nombreuses boucles les unes dans les autres et ne sait pas trop comment trouver une méthode itérative simple !
J espère avoir été clair et si l'un de vous à un peu de temps à consacrer à mon problème et à une idée je suis preneur !
Bonne journée !

[isangoma]

Salut,

La premiere chose qui me vient a l'esprit en lisant ta solution c'est les quadtree.
Si tu ne connais pas tu devrais regarder.

La solution que tu utilises, a savoir diviser en quatre, me semble loin d'etre optimale, mais bon.

Question. Si tu as quatre sous-images A,B,C,D avec A(30 millions), B (13 millions), C(13 millions) et D(13 millions).
Tu vas donc diviser A en quatre autres images, mais tu place un centre pour B,C,D ? Si oui ou ?
Comme B+C+D fait environ 40 millions, dois-tu placer deux centres ?

Sinon, pour optimiser ton programme, une fonction recursive me semble adapte ici.
A la louche je dirais un truc comme ca

Code :

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

1
2
3
4
5
6
7
8
9
10
 
fonction divise_et_place_centre(image population, tableau_de_points position_des_centres)
   Calculer la population de l'image
   Si population > 20 millions
      diviser l'image en quatre sous images
      creer quatre tableau_de_points
      rappeler la fonction divise_et_place_centre avec les quatre sous-images et tableau_de_points vide
      ajouter les quatre nouveau tableau_de_points au tableau_de_points "position_des_centres" en corrigeant les coordonees.
   Sinon
      Placer centre dans tableau_de_point

[spocky]

Merci beaucoup !
Quelle réactivité, c'est sympa !
Quadtree effectivement semble correspondre à ce que je veux faire ! Je vais m'y pencher un peu plus sérieusement ce weekend !

Pour répondre à ta question, effectivement ma méthode n'est pas des plus optimales et les 3 régions, B, C et D ne seront représentées par aucun centre..
Si tu as une autre méthode qui serait plus efficace je suis bien sur très intéressé !

[isangoma]

Salut,

Je ne suis pas vraiment expert dans ce type de probleme.
Cependant, je pense qu'un algo aleatoire pourrait donner une bonne solution.
En gros l'idee serait la suivante.

1. Calculer le nombre total d'habitant sur l'image
2. Calculer le nombre de centre N en divisant le nombre d'habitant par le nombre de centre par habitant
3. Selectionner N points au hasard sur l'image
4. Creer des zones autours des N points
5. Faire grandir les zones graduelement jusqu'a ce qu'elles contiennent le nombre d'habitants requis
6. Repeter 3,4,5 plusieurs fois et prendre la solution la plus satisfaisante.

Quelques remarques :
Quand une zone est pleine, elle ne grandit plus bien evidement.
Les zones ne sont pas forcement des carre ou des cercles.
Elles peuvent grandir de facon deterministe ou aleatoire.

Comme un algorithme de ce type est tres rapide, tu peux repeter les parties 3,4,5 de nombreuses fois.

Une maniere de regarder si une disposition est bonne :

• La distance moyenne des habitants au centre
• La variance du nombre d'habitant par centre
• Le nombre de personne non couverte par un centre

Voila bonne chance.