Voisinage de "cases" dans une liste

Bonsoir,
J'avoue avoir hésité avec le forum algorithme...
Mais mon implémentation est immédiate et en Python, alors...
J'ai une liste qui est une "matrice" de valeurs, construite basiquement ainsi :

Code:

---

1 2 3 4 5 6

atoms=[] for i in range(N): atoms.append([]) for j in range(N): atoms[-1].append(0)

---

J'aimerais connaitre, pour chaque point de la liste pris à un instant donné, l'ensemble de ses voisins, leur état, et ce de la manière la plus simple.
Il est en effet évident que les points au milieu de la liste voient 8 voisins, ce qui se code facilement, mais pour ce qui est des cases au bord (voire aux coins !)...
Voilà, le problème est posé.
Si un modérateur pense qu'il est plus approprié pour le forum algo, je suis désolé :wink:

Si c'est juste pour calculer le nombre de voisins d'un point, tu prends le même que celui que tu as pour un point intérieur de la matrice mais tu vérifie à chaque fois que le point que tu testes est bien dans la matrice

Code:

---

1 2 3 4 5 6

def voisin(mat, i, j): nbvoisins = 0 if (i-1>=0) and (j-1>=0) and (mat[i][j] == mat[i-1][j-1]): nbvoisins+=1 if (i-1>=0) and (mat[i][j] == mat[i-1][j]): nbvoisins+=1 if (i-1>=0) and (j+1<len(mat[i]) and (mat[i][j] == mat[i-1][j+1]): nbvoisins+=1 ...

---

Si tu veux calculer la matrice complète des voisins, le plus rapide, c'est de faire comme ceci

matvoisins = matrice ( N+2 , M+2 ) où (N,M) sont les dimensions de ta matrice principale et initiallement matvoisins est rempli de 0
puis tu parcours ta matrice principale et chaque fois que tu tombes sur un point important (dont la valeur est la valeur à tester pour les voisins), tu incrémente chaque point voisin dans matvoisin. Et là tu n'as plus de souci sur les effets de bord.

Code:

---

1 2 3 4 5 6 7 8

for i in len(mat): for j in len(mat[i]): if mat[i][j] == value: matvoisins[i-1][j-1] += 1 matvoisins[i-1][j] += 1 matvoisins[i-1][j+1] += 1 matvoisins[i][j-1] += 1 ...

---

PS: c'est vrai que ca aurait eu plus sa place dans le forum algorithme mais ce sont les algos que j'utilise au boulot ;) (donc pas besoin de chercher forcément plus loin). Sinon peut-être qu'avec une recherche sur "voisins" dans le forum algo tu trouveras quelques posts sur ce sujet.

L'inconvénient que je voyais, c'est que les listes sont appelables dans les deux sens. Autrement dit, dans une liste de 10 éléments de 0 à 9, en passant [-1] on a le dernier, ce qui peut arriver, ne serait-ce que dans le cas i=0, j=1...
Comment détecter cela, l'éviter en quelque sorte ?

Citation:

---

Envoyé par progman

L'inconvénient que je voyais, c'est que les listes sont appelables dans les deux sens. Autrement dit, dans une liste de 10 éléments de 0 à 9, en passant [-1] on a le dernier, ce qui peut arriver, ne serait-ce que dans le cas i=0, j=1...
Comment détecter cela, l'éviter en quelque sorte ?

---

dans les 2 exemples que je t'ai proposé, ce n'est pas possible d'appeler l'élément -1

Bon, je me suis trompé dans le deuxième exemple, il y a un décalage dans les index entre matvoisins et mat qu'il ne faut pas oublier

Code:

---

1 2 3 4 5 6 7 8 9 10 11

for i in len(mat): for j in len(mat[i]): if mat[i][j] == value: matvoisins[i][j] += 1 matvoisins[i][j+1] += 1 matvoisins[i][j+2] += 1 matvoisins[i+1][j] += 1 matvoisins[i+1][j+2] += 1 matvoisins[i+2][j] += 1 matvoisins[i+2][j+1] += 1 matvoisins[i+2][j+2] += 1

---

Sinon, si tu veux utiliser de véritables matrices au lieu de liste de liste, tu peux regarder les modules numarray ou numpy ( http://python.developpez.com/outils/Librairies/ )

numarray est trop lent, et vu l'appli, ça ne sert à rien, mes listes sont au plus de 100*100...avec des valeurs type str.
J'avoue, je suis désolé, ne pas saisir pourquoi ce sont les voisins que l'on a dans le deuxième exemple (corrigé), car j+2 va nous emmener une case plus loin, donc ce n'est plus le voisin au sens strict ?
Je pensais y aller carrément "à la barbare", c'est à dire, en mettant un certain nombre de "if".
Mais ça m'embête...

Citation:

---

Envoyé par progman

J'avoue, je suis désolé, ne pas saisir pourquoi ce sont les voisins que l'on a dans le deuxième exemple (corrigé), car j+2 va nous emmener une case plus loin, donc ce n'est plus le voisin au sens strict ?
Je pensais y aller carrément "à la barbare", c'est à dire, en mettant un certain nombre de "if".
Mais ça m'embête...

---

matvoisins a des dimensions supérieures de 2 à celles de matprinc
Donc en gros, la case (1,1) dans matvoisin correspond au nombre de voisins de la case (0,0) dans matprinc => d'où l'ajout de +1 à chaque index.
Les cases contenant un index 0 dans matvoisin (case du bord) ne sont là que pour éviter les conditions quand tu ajoutes tes voisins

exemple sur une matrice binaire
matprinc:
1 1 0
0 1 1
0 0 1

matvoisin nombre de voisins pour les 1
1 2 1 0 0
1 2 3 3 1
1 2 3 3 2
0 1 3 2 2
0 0 1 1 1