Recherche de voisins dans un tableau à deux dimensions

Question

Existe-t-il un moyen facile de trouver les voisins (c'est-à-dire les huit éléments autour d'un élément) d'un élément dans un tableau à deux dimensions? À court de seulement soustraire et ajouter à l'index dans différentes combinaisons, comme ceci:

array[i-1][i] 
array[i-1][i-1] 
array[i][i-1] 
array[i+1][i] 

... Et ainsi de suite.

Answer 1

(pseudo-code)

row_limit = count(array); 
if(row_limit > 0){ 
    column_limit = count(array[0]); 
    for(x = max(0, i-1); x <= min(i+1, row_limit); x++){ 
    for(y = max(0, j-1); y <= min(j+1, column_limit); y++){ 
     if(x != i || y != j){ 
     print array[x][y]; 
     } 
    } 
    } 
} 

Bien sûr, cela prend presque autant de lignes que la solution codée en dur d'origine, mais avec celui-ci vous pouvez étendre le « voisinage » autant que vous le pouvez (2-3 cellules ou plus)

Answer 2

array[i][j] a voisins

array[i-1][j] 
array[i][j-1] 
array[i-1][j-1] 
array[i+1][j] 
array[i][j+1] 
array[i+1][j+1] 
array[i+1][j-1] 
array[i-1][j+1] 

C'est probablement le moyen le plus rapide est/la plus facile à la liste que tous les voisins possibles. Assurez-vous de faire l'index hors de la vérification liée si.

Certaines langues peuvent offrir un raccourci, mais je n'en connais aucune.

Answer 3

Cela dépend beaucoup de vos données. Par exemple, si votre tableau 2D est une matrice logique, vous pouvez convertir des lignes en entiers et utiliser des opérations au niveau du bit pour trouver celles que vous voulez.

Pour une solution plus générale, je pense que vous êtes coincé avec l'indexation, comme la solution de SebaGR.

Answer 4

une alternative à @SebaGR, si votre langue prend en charge ceci:

var deltas = { {x=-1, y=-1}, {x=0, y=-1}, {x=1, y=-1}, 
       {x=-1, y=0},    {x=1, y=0}, 
       {x=-1, y=1}, {x=0, y=1}, {x=1, y=1} }; 
foreach (var delta in deltas) 
{ 
    if (x+delta.x < 0 || x + delta.x >= array.GetLength(0) || 
     y+delta.y < 0 || y + delta.y >= array.GetLength(1)) 
     continue; 

    Console.WriteLine("{0}", array[x + delta.x, y + delta.y]); 
} 

Léger avantage dans la lisibilité, la performance possible si vous pouvez allouer statiquement les deltas.

Answer 5

Je pense que Ben a raison dans son approche, bien que je puisse le réorganiser, pour éventuellement améliorer la localité. Une astuce pour éviter les problèmes de vérification des limites est de rendre les dimensions du tableau 2 plus grandes que nécessaire. Ainsi, une petite matrice comme celui-ci

3 1 4 
1 5 9 
2 6 5 

est effectivement mis en œuvre comme

0 0 0 0 0 
0 3 1 4 0 
0 1 5 9 0 
0 2 6 5 0 
0 0 0 0 0 

puis en additionnant, je peux indicer de 1 à 3 dans les deux dimensions, et les références du tableau ci-dessus sont garantis pour être valide et n'ont aucun effet sur la somme finale. Je suppose c, et zéro à base de l'indices exemple

Answer 6

lignes et des colonnes sont le nombre total de lignes et

Col.

Définir une struct cellIndex ou classe. Ou vous pouvez simplement renvoyer les valeurs réelles au lieu des index.

public List<CellIndex> GetNeighbors(int rowIndex, int colIndex) 
{ 
var rowIndexes = (new int[] { rowIndex - 1, rowIndex, rowIndex + 1 }).Where(n => n >= 0 && n < Rows); 

var colIndexes = (new int[] { colIndex - 1, colIndex, colIndex + 1 }).Where(n => n >= 0 && n < Cols); 

return (from row in rowIndexes from col in colIndexes where row != rowIndex || col != colIndex select new CellIndex { Row = row, Col = col }).ToList(); 
} 

Answer 7

Voici un exemple de travail Javascript de @seb pseudo-code d'origine:

function findingNeighbors(myArray, i, j) { 
    var rowLimit = myArray.length-1; 
    var columnLimit = myArray[0].length-1; 

    for(var x = Math.max(0, i-1); x <= Math.min(i+1, rowLimit); x++) { 
    for(var y = Math.max(0, j-1); y <= Math.min(j+1, columnLimit); y++) { 
     if(x !== i || y !== j) { 
     console.log(myArray[x][y]); 
     } 
    } 
    } 
} 

Answer 8

private ArrayList<Element> getNeighbors(Element p) { 
    ArrayList<Element> n = new ArrayList<Element>(); 

    for (int dr = -1; dr <= +1; dr++) { 
     for (int dc = -1; dc <= +1; dc++) { 
      int r = p.row + dr; 
      int c = p.col + dc; 

      if ((r >= 0) && (r < ROWS) && (c >= 0) && (c < COLS)) { 
       // skip p 
       if ((dr != 0) || (dc != 0)) 
        n.add(new Element(r, c)); 
      }    
     } 
    } 

    return n; 
} 

Answer 9

bien imbriquée pour les boucles dans compréhensions de liste est un peu laid c'est plus courte:

def neighbours(m, i, j): 
    return [m[x][y] for x in [i-1,i,i+1] for y in [j-1,j,j+1] if x in range(0,len(m)) and y in range(0,len(m[x])) and (x,y) != (i,j)] 

Answer 10

Voici une méthode pratique en Python:

def neighbors(array,pos): 
    n = [] 
    string = "array[pos.y+%s][pos.x+%s]" 
    for i in range(-1,2): 
     for j in range(-1,2): 
      n.append(eval(string % (i,j))) 
    return n 

En supposant que pos est un objet 2D point et array est un tableau 2D.

Answer 11

ici est un code C#:

public Cell[,] MeetNeigbours(Cell[,] Grid) 
    { 
     for (int X = 0; X < Grid.GetLength(0); X++) 
     { 
      for (int Y = 0; Y < Grid.GetLength(1); Y++) 
      { 
       int NeighbourCount = 0; 
       for (int i = -1; i < 2; i++) 
       { 
        for (int j = -1; j < 2; j++) 
        { 
         if (CellExists(Grid, (X + i)), (Y + j) && (i != 0 && j != 0)) 
         { 
          Grid[X, Y].Neighbours[NeighbourCount] = Grid[(X + i), (Y + j)]; 
         } 
         if(!(i == 0 && j == 0)) 
         { 
          NeighbourCount++; 
         } 
        } 
       } 
      } 
     } 
     return Grid; 
    } 

    public bool CellExists(Cell[,] Grid, int X, int Y) 
    { 
     bool returnValue = false; 
     if (X >= 0 && Y >= 0) 
     { 
      if (X < Grid.GetLength(0) && Y < Grid.GetLength(1)) 
      { 
       returnValue = true; 
      } 
     } 

     return returnValue; 
    } 

avec la "cellule" classe qui ressemble à ceci:

public class Cell 
{ 
    public Cell() 
    { 
     Neighbours = new Cell[8]; 
    } 

    /// <summary> 
    /// 0 3 5 
    /// 1 X 6 
    /// 2 4 7 
    /// </summary> 
    public Cell[] Neighbours; 
} 

Answer 12

Puisque dans une matrice autour d'un élément, il y a seulement 8 éléments, vous pouvez utiliser le tableau pour stocker différents index values.For par exemple,

int iarr[8] = {-1,-1,-1,0,0,+1,+1,+1}; 
    int jarr[8] = {-1,0,+1,-1,+1,-1,0,+1}; 
    for(int i = 0 ; i < 8 ; i++) 
    { 
    if(arr[x-iarr[i]][y-jarr[i]] == 1) 
    { 
    //statements 
    } 
    } 
    /* x and y are the position of elements from where you want to reach out its neighbour */ 

puisque les deux tableau contient seulement 8 valeurs, alors l'espace pourrait ne pas être un problème.