Comment indexer une liste de points pour des recherches plus rapides des points voisins?

Question

Pour une liste de points (x, y), j'essaie de trouver les points voisins pour chaque point.

from collections import defaultdict 
from math import sqrt 
from random import randint 

# Generate a list of random (x, y) points 
points = [(randint(0, 100), randint(0, 100)) for _ in range(1000)] 

def is_nearby(point_a, point_b, max_distance=5): 
    """Two points are nearby if their Euclidean distance is less than max_distance""" 
    distance = sqrt((point_b[0] - point_a[0])**2 + (point_b[1] - point_a[1])**2) 
    return distance < max_distance 

# For each point, find nearby points that are within a radius of 5 
nearby_points = defaultdict(list) 
for point in points: 
    for neighbour in points: 
     if point != neighbour: 
      if is_nearby(point, neighbour): 
       nearby_points[point].append(neighbour) 

Est-il possible que je peux index points pour accélérer la recherche ci-dessus? Je pense qu'il doit y avoir un moyen plus rapide que O (len (points) ** 2).

Edit: les points en général pourraient être flotteurs, non seulement ints

Answer 1

ceci est une version avec une grille fixe où chaque point de la grille contient le nombre d'échantillons qui sont là.

La recherche peut alors être réduite à l'espace autour du point en question.

from random import randint 
import math 

N = 100 
N_SAMPLES = 1000 

# create the grid 
grd = [[0 for _ in range(N)] for __ in range(N)] 

# set the number of points at a given gridpoint 
for _ in range(N_SAMPLES): 
    grd[randint(0, 99)][randint(0, 99)] += 1 

def find_neighbours(grid, point, distance): 

    # this will be: (x, y): number of points there 
    points = {} 

    for x in range(point[0]-distance, point[0]+distance): 
     if x < 0 or x > N-1: 
      continue 
     for y in range(point[1]-distance, point[1]+distance): 
      if y < 0 or y > N-1: 
       continue 
      dst = math.hypot(point[0]-x, point[1]-y) 
      if dst > distance: 
       continue 
      if grd[x][y] > 0: 
       points[(x, y)] = grd[x][y] 
    return points 

print(find_neighbours(grid=grd, point=(45, 36), distance=5)) 
# -> {(44, 37): 1, (45, 33): 1, ...} 
# meadning: there is one neighbour at (44, 37) etc... 

pour plus optimzation: les tests pour x et y pourrait être précalculée pour une GridSize donnée - la math.hypot(point[0]-x, point[1]-y) aurait pas à faire alors pour chaque point.

et il peut être une bonne idée de remplacer la grille par une matrice numpy.

---

MISE À JOUR

si vos points sont float s vous pouvez toujours créer une grille int pour réduire l'espace de recherche:

from random import uniform 
from collections import defaultdict 
import math 

class Point: 
    def __init__(self, x, y): 
     self.x = x 
     self.y = y 

    @property 
    def x_int(self): 
     return int(self.x) 

    @property 
    def y_int(self): 
     return int(self.y) 

    def __str__(self): 
     fmt = '''{0.__class__.__name__}(x={0.x:5.2f}, y={0.y:5.2f})''' 
     return fmt.format(self) 

N = 100 
MIN = 0 
MAX = N-1 

N_SAMPLES = 1000 


# create the grid 
grd = [[[] for _ in range(N)] for __ in range(N)] 

# set the number of points at a given gridpoint 
for _ in range(N_SAMPLES): 
    p = Point(x=uniform(MIN, MAX), y=uniform(MIN, MAX)) 
    grd[p.x_int][p.y_int].append(p) 


def find_neighbours(grid, point, distance): 

    # this will be: (x_int, y_int): list of points 
    points = defaultdict(list) 

    # need to cast a slightly bigger net on the upper end of the range; 
    # int() rounds down 
    for x in range(point[0]-distance, point[0]+distance+1): 
     if x < 0 or x > N-1: 
      continue 
     for y in range(point[1]-distance, point[1]+distance+1): 
      if y < 0 or y > N-1: 
       continue 
      dst = math.hypot(point[0]-x, point[1]-y) 
      if dst > distance + 1: # account for rounding... is +1 enough? 
       continue 
      for pt in grd[x][y]: 
       if math.hypot(pt.x-x, pt.y-y) <= distance: 
        points[(x, y)].append(pt) 
    return points 

res = find_neighbours(grid=grd, point=(45, 36), distance=5) 

for int_point, points in res.items(): 
    print(int_point) 
    for point in points: 
     print(' ', point) 

la sortie ressemble à quelque chose comme ceci:

(44, 36) 
    Point(x=44.03, y=36.93) 
(41, 36) 
    Point(x=41.91, y=36.55) 
    Point(x=41.73, y=36.53) 
    Point(x=41.56, y=36.88) 
... 

pour plus de commodité Points est maintenant une classe. peut ne pas être nécessaire si ...

selon la façon dont les points denses ou rares sont, vous pouvez aussi représenter la grille comme un dictionnaire pointant vers une liste ou Points ...

également la fonction find_neighbours accepte un départ point consistant en int s seulement dans cette version. cela pourrait aussi être raffiné.

et il y a beaucoup de place pour l'amélioration: la plage de l'axe y peut être restreinte en utilisant la trigonométrie. et pour les points à l'intérieur du cercle, il n'y a pas besoin de vérification individuelle; la vérification détaillée doit seulement être faite près du bord extérieur du cercle.