3

だから私は関数を持っています:

def connection(n,m,r):
          is_connected = ((x[n]-x[m])**2 + (y[n]-y[m])**2)**0.5
          if is_connected < 2*r:
              return n + " " + "connects with" + " " + m
          else:
              return "no connection"

これは基本的に、2 つの円 (インデックス n と m に対応する座標を持つ) が接続されているかどうかを確認します。n および m パラメータは、numpy.random 配列から取得されるデータセット x および y のインデックスを参照します。

array([[ 0.31730234,  0.73662906],
   [ 0.54488759,  0.09462212],
   [ 0.07500703,  0.36148366],
   [ 0.33200281,  0.04550565],
   [ 0.3420866 ,  0.9425797 ],
   [ 0.36115391,  0.16670599],
   [ 0.95586938,  0.52599398],
   [ 0.13707665,  0.6574444 ],
   [ 0.77766138,  0.56875582],
   [ 0.79618595,  0.7139309 ]])

配列は基本的に 10 セットの座標なので、x と y の 2 つのリストを作成しました (x は配列の最初の列、y は 2 番目の列です)。m と n は、これらのリストのインデックスです。したがって、n と m は配列内のインデックスに対応していますが、どうすればよいかわかりません。

私が今行っていることは、インデックスを手動で入力して、この配列内の 2 つの円が接続されているかどうかを確認することです。より効率的な方法でこれを行うことができる -for ループはありますか?

4

5 に答える 5

4

とにかく違うことをしているはずです。残念ながら、cKDTreeはるかに高速な には必要な機能がありませんが、他の方法でもKDTree速度が大幅に向上するはずです (そして、はるかにエレガントに解決できます)。

from scipy.spatial import KDTree
from itertools import chain

tree = KDTree(circles)

# unfortunatly only a list of lists, because there may be a different amount
# also the point itself is included every time.
connections = tree.query_ball_tree(tree, 2*r)

# if all you want is a list of lists of what connects with what
# connections is already what you need. The rest creates a connectivity matrix:    

repeats = [len(l) for l in connections]
x_point = np.arange(len(circles)).repeat(repeats)
y_point = np.fromiter(chain(*connections), dtype=np.intp)

# or construct a sparse matrix here instead, scipy.sparse has some graph tools
# maybe it even has a better thing to do this.
connected = np.zeros((len(circles),) * 2, dtype=bool)
connected[x_point, y_point] = True

cKDTree残念ながら使用しませんが、これによりO(N^2)複雑さが軽減されます...もちろん、len(circles)が小さい場合、それは問題ではありませんが、ブロードキャストを使用することができます (またはdistance_matrixからもscipy.spatial):

distances = np.sqrt(((circles[:,None,:] - circles)**2).sum(-1))
connected = distances < (2 * r)

# if you need the list of lists/arrays here you can do:
connections = [np.flatnonzero(c) for c in connected]

ただし、2 番目の方法はメモリを大量に消費するモンスターであり、circles小さい場合にのみ有効であることに注意してください。

于 2012-12-30T11:03:26.993 に答える
1

編集:以下は、セバーグの最後の方法の単なる拡張バージョンであることに気付きました...

(非常に) 数千の要素のように、データ セットが小さい場合は、numpy を使用して総当たり攻撃を行うことができます。

import numpy as np
n = 10 # the number of circles
circles = np.random.rand(n, 2) # the array of centers
distances = circles.reshape(n, 1, 2) - circles.reshape(1, n, 2)
# distances now has shape (n, n, 2)
distances = np.sqrt(np.sum(distances**2, axis=2))
# distances now has shape (n, n)
# distances[i, j] holds the distance between the i-th and j-th circle centers

半径のどの円が重なり合っているかを確認したい場合は、次のrようにすることができます。

r = 0.1
overlap = distances < 2 * r
# overlap[i, j] is True if the i-th and j-th circle overlap, False if not

rこれらの最後の 2 行は、より多くの計算を必要とする前の手順を実行する必要なく、必要な任意の値に再利用できます。

不必要なメモリを大量に使用するため、(適度に)大きなデータセットでは機能しなくなりますが、すべてのループは numpy によってフードの下で実行されるため、高速である必要があります。

于 2012-12-30T16:01:05.140 に答える
0

いくつかの回答を確認した後、コードを完全に変更する新しい回答を作成しました。

def check_overlap(circleA, circleB, r):
    # your code.
    # in each circle you have [x-coord, y-coord]

circles = [
    [0.34, 0.74], [0.27, 0.19],
    [0.24. 0.94], [0.64, 1.42]]

for a, b in ((a,b) for a in circles for b in circles):
    if a != b:
        check_overlap(a, b, r)

これにより、コードで何をしているのかが明確になります。Pythonは読みやすさがすべてです。

注:最後の関数はitertools.productを使用するのと同じですが、インポートしません。

于 2012-12-30T11:12:57.843 に答える
0

あなたは地図を使うことができます

これを行うには、単純に接続を変更して円をパラメーターとして受け入れ、円のr一部として を使用します。

def connection(circle):
    n, m, r = circle
    is_connected = ((x[n]-x[m])**2 + (y[n]-y[m])**2)**0.5
    if is_connected < 2*r:
        return n + " " + "connects with" + " " + m
    else:
        return "no connection"

リストを円とその半径のリストにします。

circles = array([
   [ 0.31730234,  0.73662906, r],
   [ 0.54488759,  0.09462212, r],
   [ 0.07500703,  0.36148366, r],
   [ 0.33200281,  0.04550565, r],
   [ 0.3420866 ,  0.9425797 , r],
   [ 0.36115391,  0.16670599, r],
   [ 0.95586938,  0.52599398, r],
   [ 0.13707665,  0.6574444 , r],
   [ 0.77766138,  0.56875582, r],
   [ 0.79618595,  0.7139309 , r]])

次に、これを行うだけです:

map(connection, circles)

r が外部またはメンバーの場合、これを使用します。

def connection(coord):
    n, m = coord
    is_connected = ((x[n]-x[m])**2 + (y[n]-y[m])**2)**0.5
    if is_connected < 2*r:
        return n + " " + "connects with" + " " + m
    else:
        return "no connection"

coords = array([
   [ 0.31730234,  0.73662906],
   [ 0.54488759,  0.09462212],
   [ 0.07500703,  0.36148366],
   [ 0.33200281,  0.04550565],
   [ 0.3420866 ,  0.9425797 ],
   [ 0.36115391,  0.16670599],
   [ 0.95586938,  0.52599398],
   [ 0.13707665,  0.6574444 ],
   [ 0.77766138,  0.56875582],
   [ 0.79618595,  0.7139309 ]])

map(connection, coords)

または、現在の形式を維持して、少し醜い実装を行うこともできます。そして、私はあなたがどこrから入手したのかまだ知りません。

for item in circles:
    connection(item[0], item[1], r)
于 2012-12-30T10:41:05.567 に答える
0

簡単な例は次のとおりです。

# m is your array
rows = m.shape[0]
for x in range(rows):
    for y in range(rows)[x+1:]:
        # x, y correspond to indices of two circles
        conn = connection(x, y, r)
于 2012-12-30T10:39:58.800 に答える