Wie effizient zu bestimmen, ob eine Reihe von Punkten zwei enthält, die nahe sind

Question

Ich muss bestimmen, ob eine Reihe von Punkten (jeweils durch ein Tupel von Schwimmern gegeben, die jeweils in [0, 1]) enthält zwei, die sind innerhalb einer Schwelle, sagen wir 0,01, voneinander. Ich sollte auch erwähnen, dass in der Version des Problems, das mich interessiert, diese "Punkte" durch Tupel der Länge ~ 30 gegeben sind, dh sie sind Punkte in [0, 1]^30.

Ich kann testen, ob zwei beliebige wie innerhalb dieser Schwelle mit etwas sind:

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

Mit diesem kann ich nur jedes Paar überprüfen mit so etwas wie:

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

Dies ist jedoch quadratisch in der Länge der Liste, die für die lange Liste der Punkte, die ich habe, zu langsam ist.

Gibt es eine Möglichkeit, dies zu lösen?

Ich habe versucht, Dinge wie schnappen, diese Punkte zu einem Raster zu tun, damit ich ein Wörterbuch/Hash-Karte verwenden, um sie zu speichern:

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 

Allerdings funktioniert das nicht, wenn

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

Da diese auf zwei verschiedene Gitterpunkte runden. Ich habe auch eine Version versucht, bei der der Punkt an alle benachbarten Gitterpunkte angehängt wurde, da die Beispiele, die ich machen möchte, ~ 30 Koordinaten haben, jeder Gitterpunkt hat 2^30 Nachbarn, was dies völlig unpraktisch macht.

Answer 1

Ein Punktpaar kann nur "nahe" sein, wenn der Abstand in mindestens einer Dimension kleiner als der Schwellenwert ist. Dies kann ausgenutzt werden, um die Anzahl der Kandidatenpaare zu reduzieren, indem eine Dimension nach der anderen gefiltert wird.

Ich schlage vor:
- sortieren Sie die Punkte in einer Dimension (sagen wir: x)
- alle Punkte finden, die in der sortierten Liste zum nächsten Punkt nahe genug sind und setzen ihren Index in eine set von Kandidaten
- nicht sqrt() verwenden, aber der quadratische Abstand (x1 - x2)**2 oder sogar abs(x1 - x2) für Effizienz
- tun, dass für die zweite Dimension als auch
- die intersect beiden Sätze bestimmen, sind diese Punkte in der Nähe von ihnen

Auf diese Weise vermeiden Sie teure is_near() Aufrufe, arbeiten auf viel kleinere Sets, arbeiten nur mit eindeutigen Punkten, und Set-Lookups sind sehr effizient.

Dieses Schema kann einfach um mehr als 2 Dimensionen erweitert werden.