Encontrar vecinos en una matriz bidimensional

Question

¿Hay una manera fácil de encontrar los vecinos (es decir, los ocho elementos alrededor de un elemento) de un elemento en una matriz bidimensional? En lugar de simplemente restar y agregar al índice en diferentes combinaciones, como esta:

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

... Y así sucesivamente.

Answer 1

(pseudo-código)

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

Por supuesto, que tiene casi tantas líneas como la solución codificada original, pero con éste se puede ampliar el "barrio" tanto como sea posible (2-3 o más células de distancia)

Answer 2

array[i][j] tiene vecinos

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] 

Esa es probablemente la manera más rápida/más fácil es simplemente una lista de todos los vecinos posibles. Sin embargo, asegúrese de hacer el índice de la verificación encuadernada.

Algunos lenguajes pueden ofrecer una forma abreviada de hacerlo, pero no conozco ninguno.

Answer 3

Mucho depende de lo que sean sus datos. Por ejemplo, si su matriz 2D es una matriz lógica, puede convertir filas en enteros y usar operaciones en modo bit para encontrar las que desee.

Para una solución más general, creo que está atascado con la indexación, como la solución de SebaGR.

Answer 4

una alternativa a @SebaGR, si su idioma es compatible con esto:

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

Ligera ventaja de facilitar la lectura, rendimiento posible si se puede asignar estáticamente los deltas.

Answer 5

Creo que Ben tiene razón en su enfoque, aunque podría reordenarlo, posiblemente para mejorar la localidad.

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] 

Un truco para evitar problemas de comprobación de límites, es hacer que las dimensiones de la matriz 2 grande de lo necesario. Por lo tanto, un poco de matriz como este

3 1 4 
1 5 9 
2 6 5 

se implementa realmente como

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 

entonces mientras sumando, puedo subíndice de 1 a 3 en ambas dimensiones, y las referencias de matriz anteriormente se garantiza que sea válido y no tienen efecto en la suma final. Asumo c, y cero subíndices base para el ejemplo

Answer 6

Filas y Cols son el número total de filas y cols

Definir un struct cellIndex o clase. O simplemente puede devolver los valores reales en lugar de los índices.

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

Aquí es un ejemplo de trabajo de Javascript @seb pseudo código original:

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

aunque bucles for anidados en las listas por comprensión es un poco feo esto es más corto:

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

Aquí hay un método conveniente 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 

Asumiendo pos es un objeto 2D Point y array es una matriz 2D.

Answer 11

Aquí hay un código para 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 clase "Cell" con este aspecto:

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

Dado que en una matriz alrededor de un elemento sólo hay 8 elementos, se puede use una matriz para almacenar diferentes valores de índice. Por ejemplo,

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

dado que ambas matrices contienen solo 8 valores, entonces el espacio podría no ser un problema.