Trovare i vicini in un array bidimensionale

Question

C'è un modo semplice per trovare i vicini (ovvero gli otto elementi attorno a un elemento) di un elemento in un array bidimensionale? A parte sottrarre e aggiungere all'indice in diverse combinazioni, come questa:

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

... E così via.

Answer 1

(pseudo-codice)

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]; 
     } 
    } 
    } 
} 

Naturalmente, che prende quasi come molte linee come la soluzione hard-coded originale, ma con questo è possibile estendere la "quartiere" per quanto è possibile (2-3 o più celle di distanza)

Answer 2

array[i][j] ha vicini

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] 

Questo è probabilmente il miglior/modo più semplice e veloce è quello di elencare tutti i possibili solo vicini di casa. Assicurati di fare un indice di controllo senza limiti.

Alcune lingue potrebbero offrire un modo rapido per farlo, ma non ne conosco nessuna.

Answer 3

Molto dipende dai dati dell'utente. Ad esempio, se l'array 2D è una matrice logica, è possibile convertire le righe in numeri interi e utilizzare le operazioni bit a bit per trovare quelle desiderate.

Per una soluzione più generica, penso che tu sia bloccato con l'indicizzazione, come la soluzione di SebaGR.

Answer 4

alternativa al @SebaGR, se la vostra lingua supporta questo:

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]); 
} 

leggero vantaggio in leggibilità, prestazioni possibili se è possibile allocare staticamente i delta.

Answer 5

Penso che Ben abbia ragione nel suo approccio, anche se potrei riordinarlo, forse per migliorare la località.

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

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

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

Uno stratagemma per evitare problemi di controllo dei limiti, è quello di rendere le dimensioni dell'array 2 più grandi del necessario. Così, un po 'questa matrice

3 1 4 
1 5 9 
2 6 5 

è effettivamente implementato come

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 

poi mentre sommando, posso pedice da 1 a 3 in entrambe le dimensioni ed i riferimenti ad array sopra sono garantiti per essere valido e non ha alcun effetto sulla somma finale. Sto presupponendo c, e nullo pedici basati per esempio

Answer 6

righe e colonne sono il numero totale di righe e colonne

Definire una struct cellIndex o una classe. O puoi semplicemente restituire i valori attuali invece degli indici.

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

Ecco un esempio JavaScript lavorando da @seb pseudo codice originale:

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

anche se cicli for innestati in list comprehension è un po 'brutto questo è più breve:

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

Ecco un metodo conveniente in 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 

Assumendo pos è un oggetto Punto 2D e array è un array 2D.

Answer 11

Ecco il codice per 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; 
    } 

con la classe "Cell", cercando in questo modo:

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

Dato che in una matrice intorno ad un elemento ci sono solo 8 elementi, è possibile utilizzare la matrice per memorizzare valori di indice diversi.Ad esempio,

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 */ 

poiché entrambi gli array contengono solo 8 valori, quindi lo spazio potrebbe non essere un problema.