La ricerca di vicini di casa in una matrice bidimensionale

C’è un modo semplice per trovare i vicini di casa (che è, gli otto elementi intorno ad un elemento di un elemento in un array bidimensionale? Breve di soli sottraendo e aggiungendo all’indice in diverse combinazioni, come questo:

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

… E così via.

InformationsquelleAutor Emil Svansø | 2009-03-16



17 Replies
  1. 29

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

    Del corso, che dura quasi come molte linee dell’originale hard-coded soluzione, ma con questo si può estendere il “quartiere” per quanto è possibile (2-3 o più celle di distanza)

    • Aggiungere il codice per l’istruzione if per controllare limiti superiori e inferiori ed è perfetto.
    • Non sono sicuro che lui vorrebbe farlo; egli di ricerca, per tutti e 8 i vicini di casa, non solo di tipo verticale e | o orizzontale. O mi sono perso qualcosa?
    • Joel dice che se si fa questo ai bordi, senza alcun confine di controllo, si ottiene un indice di fuori dei limiti di eccezione come cercare qualcosa di simile array[-1][4].
    • Capito, andrà a correggere ora, grazie.
    • Buon lavoro, grazie!
  2. 13

    Penso che Ben è corretto nel suo approccio, anche se potrei riordinare, per eventualmente migliorare 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]
    

    Un trucco per evitare la verifica dei limiti di problemi, è quello di rendere le dimensioni di una matrice 2 più grandi del necessario. Così, un po ‘ matrix come questo

    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 la somma, posso indice da 1 a 3 in entrambe le dimensioni, e l’array di riferimenti di cui sopra sono garantiti per essere valido, e non hanno alcun effetto sulla somma finale.
    Sto assumendo c, e zero a base di indici, per esempio

    • EvilTeach grazie
    • Buona idea per la verifica dei limiti, è venuto qui per vedere se potevo evitare in qualsiasi modo e questa soluzione può andare bene!
  3. 5

    un’alternativa a @SebaGR, se la lingua non 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 il delta.

    • Buona proposta, ma un cattivo stile, in modo da non dare un voto positivo. Meglio evitare di continuare e utilizzare la condizione positiva.
  4. 5

    Qui è un esempio di Javascript da @seb originale pseudo codice:

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

    array[i][j] ha vicini di casa

    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]
    

    Che probabilmente è il più veloce/più semplice è fare un elenco di tutti i possibili vicini di casa. Assicurati di fare index out of bound checking però.

    Alcune lingue potrebbero offrire una scorciatoia modo di fare questo, ma non so di qualsiasi.

  6. 2

    Qui è 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 è qualche Punto 2D oggetto e la matrice è una matrice 2D.

    • Credo che dovremmo escludere i=j=0, e aggiungere la verifica dei limiti, se necessario.
  7. 2

    Questa è un’implementazione di @Seb risposta in python3+ conciso e utilizza generatori per la prestazione massima:

    def neighbours(pos, matrix):
        rows = len(matrix)
        cols = len(matrix[0]) if rows else 0
        for i in range(max(0, pos[0] - 1), min(rows, pos[0] + 2)):
            for j in range(max(0, pos[1] - 1), min(cols, pos[1] + 2)):
                if (i, j) != pos:
                    yield matrix[i][j]
    
  8. 1

    Griglia (vettoriale 2D o una dimensione… non è qui il problema)

    X & Y coordinate dell’elemento (o semplicemente passare il vostro elemento del vettore da ref…)

    int neighbour(const Grid & g, const size_t & x, const size_t & y) {
        for (int i = -1; i < 2; ++i)
            for (int j = -1; j < 2; ++j)
                if (x + i >= 0 && x + i < g.row && y + j >= 0 && y + j < g.col)
                    //Do some stuff
        return 0;
    }
    
  9. 0

    Molto dipende da quali sono i suoi dati. Per esempio, se la matrice 2D è una logica matrice, è possibile convertire le righe di numeri interi e l’uso di operazioni bit per bit per trovare quelli che si desidera.

    Per scopi più generali soluzione penso che sei bloccato con l’indicizzazione, come SebaGR soluzione.

  10. 0

    Righe e le Colonne sono numero totale di righe e di colonne

    Definire un Indicecella struct o di classe. Oppure si può semplicemente restituire i valori effettivi invece di 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();
    }
    
  11. 0
    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;
    }
    
  12. 0

    anche se di cicli for annidati nella genericità elenco è 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)]
    
  13. 0

    qui è un po ‘ di codice di 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 “Cella” di classe di questo tipo:

    public class Cell
    {
        public Cell()
        {
            Neighbours = new Cell[8];
        }
    
        ///<summary>
        ///0 3 5
        ///1 X 6
        ///2 4 7
        ///</summary>
        public Cell[] Neighbours;
    }
    
  14. 0

    Perché in una matrice intorno ad un elemento che ci sono solo 8 elementi, è possibile utilizzare un array per memorizzare diversi valori di indice.Per 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 */
    

    dal array contiene solo 8 valori , quindi spazio potrebbe non essere un problema.

  15. 0

    L’approccio di solito faccio è descritto sul fondo di questo blog:
    https://royvanrijn.com/blog/2019/01/longest-path/

    Invece di inserire a mano il sapere o avere due cicli nidificati mi piace usare un singolo numero intero ciclo per 8 ‘’ indicazioni e utilizzo (i % 3)-1 e (i /3)-1; do di controllare il blog con le immagini.

    Non nido di profondità ed è facilmente scritto, non un sacco di codice necessario!

  16. 0

    Questo è stato davvero utile per me in un progetto recente, quindi ecco @Seb ‘s pseudo-implementazione del codice in swift. Questo è supponendo che la matrice bidimensionale quadrato:

    func adjacentIndexPaths(to indexPath: IndexPath) -> [IndexPath] {
    var neighboringSquareIndexes: [IndexPath] = []
    
    //gridSquareCount is the size of the 2D array. For example, in an 8 x 8 [[Array]], gridSquareCount is 8
    let maxIndex = gridSquareCount - 1
    var neighborRowIndex = max(0, indexPath.section - 1)
    var neighborColumnIndex = max(0, indexPath.row - 1)
    
    while neighborRowIndex <= min(indexPath.section + 1, maxIndex) {
        while neighborColumnIndex <= min(indexPath.row + 1, maxIndex) {
            if neighborRowIndex != indexPath.section || neighborColumnIndex != indexPath.row {
                neighboringSquareIndexes.append(IndexPath(row: neighborColumnIndex, section: neighborRowIndex))
            }
            neighborColumnIndex += 1
        }
        neighborRowIndex += 1
        neighborColumnIndex = max(0, indexPath.row - 1)
    }
    
    return neighboringSquareIndexes }
    
  17. 0

    JS esempio :

        function findingNeighbors(myArray, i, j){
            return myArray.reduce(function(a, b, c){
                if(Math.max(0, i-1) <= c && c <= Math.min(i+1, myArray.length-1)){
                    a = a.concat(
                        b.reduce(function(d, e, f){
                        if(f == j && c == i)
                            return d;
                        if(Math.max(0, j-1) <= f && f <= Math.min(j+1, myArray.length-1))
                            d.push(e)
                        return d;
                        },[])
                    );
                }
                return a;
            },[]);
        }
    

Lascia un commento