Как я могу использовать Shapely, чтобы обнаружить все точки, которые ближе чем N метров? - PullRequest
Новая
       15

Как я могу использовать Shapely, чтобы обнаружить все точки, которые ближе чем N метров?

1 голос
/ 26 марта 2019

Скажем, у меня есть список точек (координаты в метрах): 

points = [(1, 1), (2, 2), (-1, 3), ..., (1000, 1000)]

И я хочу использовать библиотеку Shapely, чтобы вернуть все точки (от points), которые находятся в радиусе N метров, до некоторого указанного источника, например, (3, 3).

Обновление: если я выполню: 

import numpy as np
points = [(1, 1), (2, 2), (3, 4), (100, 100), (5, 5), (1, 2)]
points_array = np.array(points)
print(points_array.shape)  # prints [n,2] where n is the number of points
max_distance = 2
origin = np.array([3, 3])
distance_array = np.sqrt((points_array - origin) ** 2)
near_points = points_array[distance_array < max_distance]
print('near points', near_points)

Я получаю 

(6, 2)
near points [2 2 3 4 2]

, что выглядит немного странно, потому что я не ожидал нечетного количества элементов, даже если получу [(2, 2), (3, 4), 2=?]

Ответы [ 3 ]

4 голосов
/ 26 марта 2019

Быстрые вычисления для большого количества данных лучше всего обрабатывать с помощью numpy.Вместо создания фигурных объектов по координатам и использования встроенной функции расстояния гораздо проще (для точек !, а не для многоугольников) рассчитать расстояние с помощью массива-пустышки.Если вы хотите сделать то же самое для линий и многоугольников и использовать ближайшие расстояния, shapely - ваш друг. 

import numpy as np
points_array = np.array(points)
print(points_array.shape)  # prints [n,2] where n is the number of points
max_distance = 100
origin = np.array([3, 3])

Теперь вычислите евклидовы расстояния как квадратную сумму разностей по оси 1 (координаты).

distance_array = np.sqrt(np.sum((points_array - origin) ** 2, 1))

И найдите точки, где расстояние меньше, чем max_distance

near_points = points_array[distance_array < max_distance]

Чтобы сравнить бесшумные решения с другими ответами с точки зрения скорости, я рассчитал ответы длятот же набор из 1e6 случайных точек:

  • Приведенный выше код занимает 49 мс
  • оптимизированное решение Питера Коллингриджа: 44 мс
  • Решение для списка по vurmax (с использованием понимания списка)см. ниже): 2,88 с (в 60 раз медленнее)
  • Список решений с оптимизацией Питера Коллингриджа: 2,48 с
  • Игрушечное стройное решение от Christian Sloper: 15,2 с (в 300 раз медленнее) 
points_vurmax = [(x,y) for x,y in points_array 
                 if math.sqrt((x - origin[0])**2 + (y - origin[1])**2) < max_dist]
points_vurmax2 = [(x,y) for x,y in points_array 
                  if (x - origin[0])**2 + (y - origin[1])**2 < max_dist ** 2]
2 голосов
/ 26 марта 2019

Не будет столь же быстрым, как решения для numpy, но вот один в форме. 

from shapely.geometry import MultiPoint

m = MultiPoint(points)
circle = Point(3,3).buffer(N)
[p for p in m if circle.covers(p) ]

возвращает точки в виде правильных точек.

0 голосов
/ 26 марта 2019

Вам не нужно использовать shapely.Функция расстояния просто:

d = math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

Вам даже не нужна numpy или любая другая библиотека, кроме std math

from math import sqrt

points = [(1, 1), (2, 2), (-1, 3)]
target = (3, 4)
distance = 3
for x, y in points:
    if math.sqrt((x - target[0])**2 + (y - target[1])**2) < distance:
        print(x, y)

(OfКонечно, вы можете использовать numpy, если у вас огромное количество баллов и вам нужно быстро их обработать)

...