列出到线的距离内的所有点 [英] List all points within distance to line

问题描述

我有一个坐标列表 a .我想指定半径 r ，然后在 a 中任意点的指定半径内列出2D网格上的所有点，以及每个网格的最小距离-指向 a 中的任意点.由于 a 很充实(〜1000-2000点)，所以我想尽可能地提高效率.

I have a list of coordinates a. I want to specify a radius r and then list all points on a 2D grid within the specified radius of any point in a, together with the minimum distance of each of those grid-points to any point in a. Since a is substantial (~1000-2000 points) I want to be as efficient as possible.

到目前为止，我的实现使用此代码列出点给定半径内的所有坐标；然后在 a 中的所有坐标上进行迭代；然后将输出展平，取一个集合(将有很多重复项)-这是直线上任意点的指定半径内的坐标集-然后计算该集合的最小距离为 a 使用 scipy.spatial.distance.cdist :

My implementation so far uses this code to list all coordinates within the given radius of a point; then iterates that over all coordinates in a; then flattens the output, takes a set (there will be MANY duplicates) - this is the set of coordinates within the specified radius of any point on the line - then calculates the minimum distances of that set to a using scipy.spatial.distance.cdist:

import numpy as np
np.random.seed(123)
a = np.random.randint(50, size=(100, 2))

def collect(coord, sigma: float =3.0):
    """ create a small collection of points in a neighborhood of some point 
    """
    neighborhood = []
    
    x=coord[0]
    y=coord[1]

    X = int(sigma)
    for i in range(-X, X + 1):
        Y = int(pow(sigma * sigma - i * i, 1/2))
        for j in range(-Y, Y + 1):
            neighborhood.append((x + i, y + j))

    return neighborhood

rad = 10
coord_list = [collect(coord, rad) for coord in a]
coord_set = np.array(list(set([val for sublist in coord_list for val in sublist])))

from scipy.spatial import distance

dists = distance.cdist(coord_set, a).min(axis=1)

结果:

coord_set
> array([[26, 21],
       [18, 17],
       [50,  6],
       ...,
       [14, 47],
       [15, 12],
       [ 7,  8]])

dists
> array([2.23606798, 5.65685425, 1.41421356, ..., 3.16227766, 3.        ,
       1.41421356])

有人可以通过任何方式改进它并使其更有效吗?

Does anyone have any ways I can improve this and do it more efficiently?

推荐答案

让我们仔细检查您的实现.请注意，您已经蓄势待发，并已在 collect 中部分计算了距离度量.

Let's inspect your implementation carefully. Notice that you are already poised and partially compute a distance metric in collect.

1. 如果将 neighborhood 设置为 dict 而不是 list ，该方法由具有最小距离值的网格点作为键，该怎么办?您可以完全消除对 set 和 cdist 的调用.
2. 如果 a 可以包含浮点值，则您的范围应从 int(coord [0]-rad)到 int(coord [0] + rad)+ 1 . int(0.5-10)是 -9 ，而 int(0.5)-10 是 -10 ./li>
3. 您可以将半径与平方半径进行比较，因此最终结果只需一次取平方根即可.

1. What if you made neighborhood a dict instead of a list, keyed by grid point with a value of minimum distance. You could entirely eliminate the call to set and cdist.
2. If a can contain float values, you should your range from int(coord[0] - rad) to int(coord[0] + rad) + 1. int(0.5 - 10) is -9, while int(0.5) - 10 is -10.
3. You can compare to the squared radius, so you don't need to take the square root except once for the final result.

第2点和第3点是相对较小的改进.

Points 2 and 3 are relatively minor improvements.

这里是一个例子:

rad = 10
rad2 = rad**2

points = {}

for coord in a:
    for x in range(int(np.ceil(coord[0] - rad)), int(coord[0] + rad) + 1):
        dx2 = (x - coord[0])**2
        chord = np.sqrt(rad2 - dx2)
        for y in range(int(np.ceil(coord[1] - chord)), int(coord[1] + chord) + 1):
            d2 = dx2 + (y - coord[1])**2
            key = x, y
            points[key] = min(d2, points.get(key, rad2))

要将其转换为numpy数组:

To convert this into numpy arrays:

grids = np.array(list(points.keys()))
nearest = np.sqrt(np.fromiter(points.values(), count=len(points), dtype=float))

这篇关于列出到线的距离内的所有点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！