Pythonic und effiziente Art und Weise von benachbarten Zellen in Gittern zu finden

Question

Ich baue eine Kachel-basierte Anwendung in Python Pyglet / openGL wobei werde ich brauche die alle benachbarten Zellen für eine bestimmte Zelle zu finden. Ich arbeite in einem Quadranten eines karthesischen Gitter. Jede Zelle weist einen x- und y-Wert seiner Position in dem Gitter (x_coord und y_coord) anzeigt. Dies sind keine Pixelwerte, sondern Rasterpositionen. Ich bin auf der Suche nach einer effizienten Art und Weise, die die benachbarten Zellen zu erhalten. Bei max gibt es acht mögliche benachbarten Zellen, sondern wegen der Grenzen des Gitters dort so wenig wie 3. Pseudo-Code für eine einfache, aber ineffiziente Ansatz sieht etwas wahrscheinlich so sein könnte:

def get_adjacent_cells( self, cell ):
     result = []
     x_coord = cell.x_coord
     y_coord = cell.y_coord
     for c in grid.cells:
          if c.x_coord == x_coord and c.y_coord == y_coord: # right
               result.append( c )
          if c.x_coord == x_coord - 1 and c.y_coord == y_coord + 1: # lower right
               result.append( c )
          if c.x_coord == x_coord - 1 and c.y_coord == y_coord: # below
               result.append( c )
          if c.x_coord == x_coord - 1 and c.y_coord == y_coord - 1: lower left
               result.append( c )
          if c.x_coord == x_coord and c.y_coord == y_coord - 1: right
               result.append( c )
          // -- similar conditional for remaining cells

Dies würde wahrscheinlich gut funktionieren, obwohl es wahrscheinlich ist, dass dieser Code bei jedem Rahmen ausgeführt werden muß und in einem größeren Raster kann es die Leistung beeinträchtigt. Alle Ideen für eine schlankere und weniger CPU-intensiv Ansatz? Oder soll ich nur Rolle bei diesem Ansatz?

Vielen Dank im Voraus.

Answer 1

Es war mir nicht klar, ob es andere Informationen in den Zellen als nur die x- und y-Koordinaten. Auf jeden Fall denke ich, dass eine Änderung der Datenstrukturen benötigt wird, um diese schneller zu machen.

ich davon aus, dass es sich um zusätzliche Informationen in den Zellen und machte grid.cells als Wörterbuch mit den Tasten Tupeln der Koordinaten zu sein. Ein ähnliches getan withgrid.cells als ein Satz sein könnte, wenn es nur die Koordinateninformationen in den Zellen ist.

def get_adjacent_cells( self, x_coord, y_coord ):
    result = {}
    for x,y in [(x_coord+i,y_coord+j) for i in (-1,0,1) for j in (-1,0,1) if i != 0 or j != 0]:
        if (x,y) in grid.cells:
            result[(x,y)] = grid.cells[(x,y)]

Je nachdem, was Sie mit den Daten zu tun, mögen Sie vielleicht nicht einen dict machen führen, aber hoffentlich Sie bekommen die Idee. Dies sollte viel schneller als Ihr Code sein, weil Ihr Code 8 Kontrollen macht auf jeder Zelle in grid.cells.

Answer 2

Der Code wird so langsam sein, wie groß das Raster ist, weil Sie Iterieren über die Zellen nur 8 von ihnen zu bekommen (von denen Sie bereits ihre Koordinaten kennen).

Wenn Sie Direktzugriff durch ihren Indizes tun können, schlage ich vor, etwa wie folgt:

adjacency = [(i,j) for i in (-1,0,1) for j in (-1,0,1) if not (i == j == 0)] #the adjacency matrix

def get_adjacent_cells( self, cell ):
     x_coord = cell.x_coord
     y_coord = cell.y_coord
     for dx, dy in adjacency:
          if 0 <= (x_coord + dx) < max_x and 0 <= y_coord + dy < max_y: #boundaries check
#yielding is usually faster than constructing a list and returning it if you're just using it once
              yield grid[x_coord + dx, y_coord + dy]

max_x und max_y sollen die Größe des Gitters sein, und die grid.__getitem__ sollte ein Tupel mit den Koordinaten akzeptieren, und die Zelle in dieser Position zurück.

Answer 3

Nun, dies wird nicht helfen, die Leistung jeder, aber Sie können Code Doppelarbeit vermeiden, indem er sagte

if abs(c.x_coord - x_coord) == 1 or abs(c.y_coord - y_coord) == 1:
    result.append(c)

Um die Leistung beeinträchtigt, Ihre Gitterzellen sollten wissen, wer ihre Nachbarn sind, entweder durch ein Attribut wie c.neighbors oder durch eine implizite Struktur, wie eine Liste von Listen, so dass Sie durch Koordinaten zugreifen können.

grid = [[a,b,c],
        [d,e,f],
        [g,h,i]]

Dann können Sie für nachbarschaftliche überprüfen Sie die Liste Indizes verwendet wird.

Answer 4

Dies ist wahrscheinlich die effizienteste Art und Weise zu suchen Nachbarn, wenn grid.cells als Set implementiert wird (obwohl es ist ein Fehler in der ersten if-Anweisung - Sie müssen Test auf Gleichheit x_coord + 1 anstatt zu x_coord) .

Allerdings grid.cells als eine Liste von Listen Implementierung Sie erlauben würde, auf einzelne Zellen durch Zeilen- und Spaltennummer zu verweisen. Es würde auch ermöglicht es Ihnen, die Gesamtanzahl der Zeilen und Spalten zu messen. get_adjacent_cells könnte dann arbeiten, indem man zuerst überprüfen, welche Kanten die aktuelle Zelle angrenzen, und dann die Nachbarn in allen anderen Richtungen sucht und sie in der Ergebnisliste angehängt wird.

Answer 5

In einem Raster, adjacency heißt, Sie brauchen nur noch einen Schritt von entweder koordinieren, um die andere zu erreichen, wenn ich nicht versehentlich oder hoch bin.

 if abs(c.x_coord -_coord +c.y_coord-y_coord) == 1
     print "they are adjacent!"

Answer 6

Das funktioniert mit numpy Arrays

def get_adjacent_cells(arr, selected_idxs):
    """
    >>> arr = np.ones((3,))
    >>> get_adjacent_cells(arr, {(1,)})
    {(0,), (1,), (2,)}
    >>> arr = np.ones((3,2))
    >>> get_adjacent_cells(arr, {(1,1)})
    {(0, 1), (1, 0), (1, 1), (2, 1)}
    >>> arr = np.ones((3,2,3))
    >>> {(0, 1, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
    >>> arr = np.ones((3,2,3))
    >>> get_adjacent_cells(arr, {(1,1,0), (0,1,0)})
    {(0, 0, 0), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
    """
    w = np.asarray(list(selected_idxs))
    new_idxs = []
    for col in range(w.shape[1]):
        w_ = w.copy()
        w_[:,col] += 1
        new_idxs.extend(list(w_))
        w_ = w.copy()
        w_[:,col] -= 1
        new_idxs.extend(list(w_))

    new_idxs = np.array(new_idxs)

    # remove out of bounds coordinates
    for col, dim_size in enumerate(arr.shape):
        new_idxs = new_idxs[(new_idxs[:, col] >= 0) & (new_idxs[:, col] < dim_size)]

    return selected_idxs.union(map(tuple, new_idxs))