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"

这基本上可以查看两个圆（具有对应于索引 n 和 m 的坐标）是否连接。n 和 m 参数是指数据集 x 和 y 中的索引，它们来自 numpy.random 数组：

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（x 是数组的第一列，y 是第二列）。m 和 n 是这些列表中的索引。因此， n 和 m 对应于数组中的索引，但我不确定如何？

我现在一直在做的是手动输入索引以查看该数组中的任何两个圆圈是否连接 - 是否有一个 -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]

但请注意，第二种方法是一个内存饥渴的怪物，只有circles在很小的情况下才有用。

于 2012-12-30T11:03:26.993 回答
1

编辑：刚刚意识到以下只是seberg最后一种方法的扩展版本......

如果您的数据集很小，例如（非常）几千个元素，您可以使用 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，而无需执行更密集的上一步计算。

它使用了大量不必要的内存，因此对于（中等）大型数据集会崩溃，但由于所有循环都由 numpy 运行，因此它应该很快。

于 2012-12-30T16:01:05.140 回答
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 回答
0

you can use map

to do so, simply change connection to accept a circle as its parameter, and have the r as part of the circle

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"

and have your list be a list of circles AND their radius.

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

then simply do this:

map(connection, circles)

if the r is external, or a member then you want to use this:

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)

or you can keep your current format, and do a slightly uglier implementation. and i still dont know where you get the r from.

for item in circles:
    connection(item[0], item[1], r)
于 2012-12-30T10:41:05.567 回答
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 回答