グリッド内の隣接するセルを見つけることのPython的かつ効率的な方法

StackOverflow https://stackoverflow.com/questions/2373306

  •  24-09-2019
  •  | 
  •  

質問

私は特定のセルの隣接セルのすべてを見つける必要がありますここで

私はpyglet / OpenGLを使用してPythonでタイルベースのアプリケーションを構築しています。私はデカルト格子の1つの象限で働いています。各セルは、グリッド（x_coordとy_coord）におけるそれの位置を示すxとyの値を有します。これらは、ピクセル値、むしろグリッド位置ではありません。私は、隣接するセルを取得するための効率的な方法を探しています。最大で8つの可能な隣接セルがありますが、シンプル3.擬似コードは、まだおそらく非効率的なアプローチは、このようなものに見えるようため、グリッドの境界の数とがあるかもしれません。

を 
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
それは、このコードはすべてのフレームを実行する必要がありますし、大きなグリッドで、それがパフォーマンスに影響を与える可能性がある可能性が高いということですが、

これはおそらく、うまく動作します。より多くの合理化とより少ないCPUを集中的アプローチのための任意のアイデア？それとも、はずこのアプローチには、私だけでロール？

事前に感謝します。

役に立ちましたか？

解決

ただ、xとy座標よりも細胞内の他の情報があった場合は、それは私には明確ではありませんでした。いずれにせよ、私は、データ構造の変化は、この高速化するために必要であると思います。

私は余分な情報が細胞中に存在すると仮定し、キーの座標の組であると辞書としてgrid.cellsしました。同様の事は、存在する場合、細胞内の座標情報セットとしてwithgrid.cellsを行うことができる。

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

あなたがデータで何をしたいのかに応じて、辞書を引き起こすようにしたいではないかもしれませんが、うまくいけばあなたのアイデアを得ます。あなたのコードがgrid.cells内のすべてのセルに8つのチェックを行っているので、これはあなたのコードよりもはるかに高速である必要があります。

他のヒント

大があなたのグリッドであるとして、あなたのコードがちょうど（あなたが既にそれらの座標を知っている）それらの8を取得するために、細胞の上にあなたのためにしている反復処理、遅いようになるだろうされます。

あなたは、それぞれのインデックスによるランダムアクセスを行うことができる場合、私は次のようなものを提案します：

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とmax_yは、グリッドの大きさになっている、とgrid.__getitem__は、座標タプルを受け入れて、その位置に細胞を戻すことになっている。

さて、このいずれかのではないのヘルプパフォーマンスしますが、あなたが言うことでコードの重複を避けることができます。

if abs(c.x_coord - x_coord) == 1 or abs(c.y_coord - y_coord) == 1:
    result.append(c)
あなたは座標によってアクセスできるように

のパフォーマンスに影響を与えるために、あなたのグリッドセルは、リストのリストのように、c.neighborsのような属性を使用して、または暗黙的な構造のいずれかを介して、彼らの隣人が誰であるかを知っている必要があります。

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

そして、あなたはリストのインデックスを使用して隣人をチェックすることができます。

grid.cellsがセットとして実装されている場合、

これはおそらく、隣人を探すために最も効率的な方法です（最初のif文に誤りがありますけれども - あなたはむしろx_coordよりx_coord + 1に等しいかどうかをテストする必要があります）ます。

しかし、リストのリストとしてgrid.cellsを実装するあなたは、行と列の数によって、個々のセルを参照できるようになります。また、あなたが行と列の合計数を測定することができるようになります。 get_adjacent_cellsは、その後、最初のエッジが現在のセルに接するチェック、作品が他のすべての方向に隣人を検索し、結果リストにそれらを追加することができます。

グリッドで

、隣接手段あなたは、私が誤ってか、高いじゃない場合は、他に到達するために座標のいずれかの一工程のみを必要とします。

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

と

この作品 

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))
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top