Come determinare in modo efficiente se un set di punti contiene due che sono chiusi

Question

Ho bisogno di determinare se un insieme di punti (ognuno dato da una tupla di float, ognuno dei quali è in [0, 1]) contiene due che sono entro una certa soglia, diciamo 0,01, l'una dall'altra. Dovrei anche menzionare che nella versione del problema che mi interessa, questi "punti" sono dati da tuple di lunghezza ~ 30, cioè sono punti in [0, 1]^30.

posso testare se qualsiasi due sono all'interno di questa soglia usando qualcosa come:

def is_near(p1, p2): 
    return sqrt(sum((x1 - x2)**2 for x1, x2 in zip(p1, p2))) < 0.01 # Threshold. 

Usando questo posso solo controllare ogni coppia utilizzando qualcosa di simile:

def contains_near(points): 
    from itertools import combinations 
    return any(is_near(p1, p2) for p1, p2 in combinations(points, r=2)) 

Tuttavia questo è quadratica nel lunghezza della lista, che è troppo lenta per la lunga lista di punti che ho.

Esiste un modo per risolvere questo problema?

Ho provato a fare le cose come scattare questi punti per una griglia in modo da poter utilizzare una mappa dizionario/hash per memorizzare loro:

def contains_near_hash(points): 
    seen = dict() 
    for point in points: 
     # The rescaling constant should be 1/threshold. 
     grid_point = tuple([round(x * 100, 0) for x in point]) 
     if grid_point in seen: 
      for other in seen[grid_point]: 
       if is_near(point, other): 
         return True 
      seen[grid_point].append(point) 
     else: 
      seen[grid_point] = [point] 
    return False 

Tuttavia questo non funziona quando

points = [(0.1149999,), (0.1150001,)] 

Come questi arrotondano a due diversi punti della griglia. Ho anche provato una versione in cui il punto è stato aggiunto a tutti i punti della griglia vicini, tuttavia, poiché gli esempi che voglio fare hanno ~ 30 coordinate, ogni punto della griglia ha 2^30 vicini che lo rendono completamente impraticabile.

Answer 1

Una coppia di punti può essere "vicini" solo se la loro distanza in almeno una dimensione è inferiore alla soglia. Questo può essere sfruttato per ridurre il numero di coppie candidate filtrando una dimensione dopo l'altra.

suggerisco:
- ordinare i punti in una dimensione (diciamo: x)
- trova tutti i punti che sono abbastanza vicino al punto successivo nella lista ordinata e mettere il loro indice in una set di candidati
- non utilizzare sqrt() ma la distanza quadratica (x1 - x2)**2 o anche abs(x1 - x2) per l'efficienza
- do che per la seconda dimensione così
- determinare l'intersezione delle due categorie, questi sono punti vicini tra loro

In questo modo, si evitano costose chiamate is_near(), si opera su insiemi più piccoli, si lavora solo con punti univoci e le ricerche di set sono molto efficienti.

Questo schema può essere facilmente esteso per includere più di 2 dimensioni.