"Percolation" dans une grille en 2D [Résolu]

Signaler
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020
-
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
-
Bonjour,
Je viens ici pour vous faire partager un problème qui me hante depuis déjà plusieurs semaines...

Dans le cadre d'un projet de simulation informatique (c'est un modèle de ségrégation de Schelling pour celle et ceux que ça intéresse) je suis amené à étudier la transition de phase de mon système. N'ayez crainte pas de physique dans ce qui m'amène ici ! En effet, cette étude ce ramène tout d'abord à analyser, dans une grille (typiquement celle-ci, si l'insertion de l'image c'est bien passé)

la taille des groupes se formant. De manière plus claire, la grille est peuplé de trois agents différents : des case rouge, verre, et blanc. Comme vous pouvez le voir, ces cases se rassemble en agrégat de différente taille : c'est ces tailles que je veux déterminer.

Vous imaginez bien que j'ai quand même creuser la question, je sais que ce problème peut se ramener à un problème de percolation (d'où le titre). J'ai par ailleurs déjà essayé plusieurs méthodes que je serais ravie de vous expliquer si vous le voulez.

Voilà désolé d'avance pour mon orthographe que j'imagine déplorable, mais j'ai trop codé pour aujourd'hui...

6 réponses

Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775
bonjour,
merci de nous tenir au courant de tes réflexions.
as-tu une question?
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020

Comme je l'ai dis, j'avais d'abord pensé à une méthode de percolation. Je parcours ma grille dans sa totalité, en prenant soit de ne pas marquer deux fois les mêmes cases. Une fois une nouvelle case sélectionné, je prend en compte ses quatre voisins. Mais je me heurte à un problème : il est alors difficile de repartir vérifier les "voisins des voisins" et ainsi de suite. J'ai penser à une méthode de récursion mais j'ai du mal à le conceptualiser, d'où ma présence ici.

Avez-vous une idée ?
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775
comme c'est ton projet, il est sans doute préférable que tu trouves une méthode. j'imagine, en effet, que c'est une partie importante du projet, et de l'apprentissage.
en quoi les méthodes essayées ne sont pas satisfaisantes?
en quoi est-il difficile de repartir ensuite vérifier les voisins des voisins? pourquoi était-ce simple la première fois, et en quoi est-ce devenu plus compliqué?
si tu devais faire le travail à la main, comment t'organiserais-tu? cela pourrait te permettre de trouver des méthodes.

n'hésite pas à rédiger le résultat de tes réflexions, et à les partager.
tu as probablement accumulé pas mal de notes depuis déjà plusieurs semaines.
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020

Je possède déjà une méthode, je veux alors avoir si il en existe d'autre, plus efficace et collant davantage à mon problème (qui est d'ailleurs extrêmement minime dans le cadre de mon projet, qui est, je vous rassure, non scolaire)

Le problème de la méthode de percolation est qu'elle m'oblige à avoir un début bien spécifique, un sens et une fin. Par exemple, le problème de l'algorithme de percolation que j'ai réalisé allait toujours vers le bas (il essayait, entre autre de percoler).
Pour ce qui est de la récursion, j'ai un problème de visualisation, je ne suis pas coutumier de ce genre de méthode.

J'ai bien sûr déjà écrit à la mains ce que je voulais faire :
-On parcours un par un les case de la grille, qui est peuplé de 0, 1 ou 2 initialement (les valeurs anciennes);
-si la case a une valeur anciennes, on commence par sortir ça valeur, la remplacer par une nouvelle (typiquement i+j+3 avec i les lignes et j les colonnes, un +3 pour qu'il n'y est pas de doublons);
-on teste c'est quatre voisin, si un de ses voisins est égale à la valeur anciennes, on la remplace par la nouvelles valeur;
-on refais le teste pour tout les voisins similaire, on s'arrête de tester les voisins dès qu'une case n'a plus de voisins similaire.
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775
peux-tu montrer le programme que tu as écrit?
si je comprends bien, il ne te donne pas le résultat attendu. est-ce exact? quel résultat donne-t'il?
n'hésite pas à faire une petit exemple avec des données.

je suppose que le programme n'applique pas la méthode que tu voulais faire. pourquoi?
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775
quand tu réfléchis à comment tu ferais à la main, il faut te mettre dans la situation d'un robot. un robot assez simple, qui n'a pas de compréhension de ce qu'est une image, qui ne voit que chacun des points individuellement.
un peu comme un humain qui travaillerait avec l'image tournée vers la table, dont il devrait retourner une case pour en voir la couleur, et qui ne peut en retourner que une à la fois.
quand tu écris "on refais le teste pour tout les voisins similaire", il me semble que tu ignores cet aspect du problème.
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775
tu n'as pas répondu à cette question. je te l'ai posée pour t'aider à trouver la solution.
en quoi est-il difficile de repartir ensuite vérifier les voisins des voisins? pourquoi était-ce simple la première fois (pour les voisins), et en quoi est-ce devenu plus compliqué (pour les voisins des voisins)?
nous sommes face à cette même difficulté en faisant le travail à la main (sans avoir une compréhension de la globalité de l'image).
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775
moi je ferais ainsi:
case en cours = case en haut à gauche
tant que la case en cours est dans le dessin:
si couleur de la case en cours est une couleur d'origine:
remplirforme(case en cours)
case en cours = case suivant la case en cours

remplirforme(lacasededepart):
couleurforme = couleur de la case de départ
codeforme=i+j+3
couleur de case de départ = codeforme
ajouter les 4 voisins de la case de départ dans liste à faire
tant que liste à faire n'est pas vide:
retirer une case de la liste à faire, appellons-là casedetravail
si couleur de casedetravail = couleurforme :
couleur de case de travail = codeforme
ajouter les 4 voisins de la case de travail dans liste à faire
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775
un exemple de code:
import math
def colorie(dessin,nbcoul):
    resume=[]
    long=len(dessin)
    for lll in dessin:
        if len(lll) != long:
            raise Exception("Oups, ce n'est pas un carré!")
        for c in lll:
            if c < 1 or c>nbcoul:
                raise Exception("Oups, mauvaise couleur("+str(c)+")!")
    caseencours = (0,0)
    nforme=0
    while not caseencours== None:
        if dessin[caseencours[0]][caseencours[1]] <=nbcoul: 
            resume.append(remplirforme(dessin,nbcoul,caseencours,nforme))
            nforme += 1
        col = caseencours[1] + 1
        lig= caseencours[0]
        if col == len(dessin):
            col = 0
            lig += 1
        if lig == len(dessin):
            caseencours = None
        else:
            caseencours=(lig,col)
    return(resume)
def remplirforme(couleur,ncoul,lacasededepart,nf):
    surface=0
    couleurforme = couleur[lacasededepart[0]][lacasededepart[1]]
    codeforme=nf + couleurforme*10**(1+int(math.log(len(couleur)**2+ncoul,10)))
    listafair=[]
    listafair.append((lacasededepart[0],lacasededepart[1]))
    while len(listafair)>0:
        casedetravail=listafair.pop(0)
        if casedetravail[0] >=0 and casedetravail[0] < len(couleur) \
               and casedetravail[1] >= 0 and casedetravail[1] < len(couleur):
            if couleur[casedetravail[0]][casedetravail[1]] == couleurforme :
                couleur[casedetravail[0]][casedetravail[1]] = codeforme
                surface += 1
                listafair.append((casedetravail[0]+1,casedetravail[1]))
                listafair.append((casedetravail[0]-1,casedetravail[1]))
                listafair.append((casedetravail[0],casedetravail[1]+1))
                listafair.append((casedetravail[0],casedetravail[1]-1))
    return(lacasededepart, couleurforme,surface)
ncouleurs=3
taille=9
kouleurs=[[3 for i in range(taille)] for j in range(taille)]
kouleurs[4][4]=1
kouleurs[4][5]=1
kouleurs[5][4]=1
kouleurs[5][5]=1
kouleurs[8][8]=2
kouleurs[3][3]=2
kouleurs[3][4]=2
kouleurs[4][2]=2
kouleurs[5][2]=2
kouleurs[6][3]=2
print(colorie(kouleurs,ncouleurs))
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020

Je vous remercie de prendre autant de temps pour m'aider.
Mon programme tournais à l'infinie, une boucle while n'avait alors jamais sa condition remplie.
En faite, pour être plus précis, à chaque fois que je trouve une case similaire, je relance ma fonction de teste de voisin. Ma fonction de teste de voisin agrémente de 1 les variables g,d,h,b (pour gauche droite haut bas) pour que je sache qu'elle voisin similaire ont été trouver et leur position relatif, ça me permet de tester successivement les voisins. Tant que g,d,h,b sont implémenté, la boucle continue. Si toutes ces variables ont pris la valeur 0, la boucle s'arrête et ça veut dire qu'aucun voisin proche n'a été trouver.
Voici le code sur le quel je travaille en ce moment.
La première fonction est là pour initialiser mon tableau. Il est utilise dans le cadre de mon projet.
Pour les conditions aux limites j'ai choisi un plan fermer sur ces bords.
J'espère qu'il sera lisible tout de même !

##importation des modules
import numpy.random as rd
import numpy as np
import copy


##définition des fonctions

def init_tab(nb_b,N) :
    tab=np.zeros((N,N),dtype=int)
    nb=(N**2-nb_b)/2
    for i in np.arange(nb*2) :
        x=rd.randint(0,N)
        y=rd.randint(0,N)
        while tab[x][y]==1 or tab[x][y]==2 :
            x=rd.randint(0,N)
            y=rd.randint(0,N)
        if i%2==0 :
            tab[x][y]=1
        else :
            tab[x][y]=2
    return tab


def test_voisin(tab,i,j):
    a=i+j+3
    valeur=tab[i][j]
    tab[i][j]=a
    g=0
    d=0
    h=0
    b=0
    if i>0 and tab[i-1][j]==valeur :
        g+=1
        tab[i-1][j]=a
    if i<N-1 and tab[i+1][j]==valeur :
        d+=1
        tab[i+1][j]=a
    if j>0 and tab[i][j-1]==valeur:
        h+=1
        tab[i][j-1]=a
    if j<N-1 and tab[i][j+1]==valeur :
        b+=1
        tab[i][j+1]=a
    return tab,a,g,d,h,b

def coloration(tab) :
    N=len(tab)
    for i in range(N):
        for j in range(N):
            valeur=tab[i][j]
            if valeur==0 or valeur==1 or valeur==2 :
                tab,a,g,d,h,b=test_voisin(tab,i,j)
                while g!=0 and d!=0 and h!=0 and b!=0 :
                    if g!=0 :
                        tab,a,g,d,h,b=test_voisin(tab,i-1,j)
                    if d!=0 :
                        tab,a,g,d,h,b=test_voisin(tab,i-1,j)
                    if h!=0 :
                        tab,a,g,d,h,b=test_voisin(tab,i,j+1)
                    if b!=0 :
                        tab,a,g,d,h,b=test_voisin(tab,i,j-1)

##programme principale
N=10
b=10

tab_test=init_tab(b,N)
tab=percolation(tab_test)
print(tab)
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775
suggestion: remplacer les lignes 34 et 35 par
test_voisin(tab, i-1 , j)  
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020

Pour ce qu'il s'agit de ce que vous m'avez proposer, cela fonctionne très bien (petit plus à la fonctionnalité raise que je ne connaissais pas et qui je pense me sera très utile !)
Vous utilisé une méthode que j'avais déjà testé sans succès, celle où je m'était inspirer des méthodes de percolation.

Il ne me reste plus qu'à savoir ce qui cloche dans mon programme et à moi l'étude de la transition de phase de mon système de ségrégation social !!
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020
>
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021

Je ne vois pas pourquoi vous dites ça. Si cette algorithme fonctionne, il colorera tout les groupes de voisins d'une couleur différentes. Ainsi, il sera très simple d'en extraire leur nombre et la taille de chaque groupe.
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775 >
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020

j'écris cela parce qu'il me semble clair qu'il est mal conçu, et ne peut fonctionner.
j'ai fait une suggestion d'algorithme et une suggestion de programme, pourquoi ne pas t'inspirer de l'un ou l'autre?
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020
>
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021

J'ai bien sûr conçus un algorithme fonctionnel en me basant sur vos indications, je vous transmettais juste ce que j'avais fais au moment de poster mon problème ici; conformément à votre demande.
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775 >
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020

peux-tu alors marquer la discussion comme résolue?
Messages postés
13791
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
6 janvier 2021
775 >
Messages postés
7
Date d'inscription
mercredi 23 décembre 2020
Statut
Membre
Dernière intervention
27 décembre 2020

si tu préfères un programme récursif:
import math
def colorie(dessin,nbcoul):
    resume=[]
    long=len(dessin)
    for lll in dessin:
        if len(lll) != long:
            raise Exception("Oups, ce n'est pas un carré!")
        for c in lll:
            if c < 1 or c>nbcoul:
                raise Exception("Oups, mauvaise couleur("+str(c)+")!")
    caseencours = (0,0)
    nforme=0
    while not caseencours== None:
        if dessin[caseencours[0]][caseencours[1]] <=nbcoul: 
            resume.append(remplirforme(dessin,nbcoul,caseencours,nforme))
            nforme += 1
        col = caseencours[1] + 1
        lig= caseencours[0]
        if col == len(dessin):
            col = 0
            lig += 1
        if lig == len(dessin):
            caseencours = None
        else:
            caseencours=(lig,col)
    return(resume)
def traiteunecase(couleurs,couleurf,codef,lacase):
    ajout=0
    if lacase[0] >=0 and lacase[0] < len(couleurs) \
               and lacase[1] >= 0 and lacase[1] < len(couleurs):
            if couleurs[lacase[0]][lacase[1]] == couleurf :
                couleurs[lacase[0]][lacase[1]] = codef
                ajout=1
                ajout=ajout+traiteunecase(couleurs,couleurf,codef,(lacase[0]+1,lacase[1]))
                ajout=ajout+traiteunecase(couleurs,couleurf,codef,(lacase[0]-1,lacase[1]))
                ajout=ajout+traiteunecase(couleurs,couleurf,codef,(lacase[0],lacase[1]+1))
                ajout=ajout+traiteunecase(couleurs,couleurf,codef,(lacase[0],lacase[1]-1))
    return(ajout)
def remplirforme(couleur,ncoul,lacasededepart,nf):
    surface=0
    couleurforme = couleur[lacasededepart[0]][lacasededepart[1]]
    codeforme=nf + couleurforme*10**(1+int(math.log(len(couleur)**2+ncoul,10)))
    surface=surface + traiteunecase(couleur,couleurforme,codeforme,lacasededepart)
    listafair=[]
    listafair.append((lacasededepart[0],lacasededepart[1]))
    while len(listafair)>0:
        casedetravail=listafair.pop(0)
        if casedetravail[0] >=0 and casedetravail[0] < len(couleur) \
               and casedetravail[1] >= 0 and casedetravail[1] < len(couleur):
            if couleur[casedetravail[0]][casedetravail[1]] == couleurforme :
                couleur[casedetravail[0]][casedetravail[1]] = codeforme
                surface += 1
                listafair.append((casedetravail[0]+1,casedetravail[1]))
                listafair.append((casedetravail[0]-1,casedetravail[1]))
                listafair.append((casedetravail[0],casedetravail[1]+1))
                listafair.append((casedetravail[0],casedetravail[1]-1))
    return(lacasededepart, couleurforme,surface)
ncouleurs=3
taille=9
kouleurs=[[3 for i in range(taille)] for j in range(taille)]
kouleurs[4][4]=1
kouleurs[4][5]=1
kouleurs[5][4]=1
kouleurs[5][5]=1
kouleurs[8][8]=2
kouleurs[3][3]=2
kouleurs[3][4]=2
kouleurs[4][2]=2
kouleurs[5][2]=2
kouleurs[6][3]=2
print(colorie(kouleurs,ncouleurs))