GPS-Koordinatensuche -- R-Bäume

Question

Ich habe eine Liste von Listen in Form von

[ [ x1,.....,x8],[x1,.......,x8],...............,[x1,.....x[8]] ] . Die Anzahl der Listen in dieser Liste kann bis zu einer Million gehen. Jede Liste hat 4 GPS-Koordinaten, die die vier Punkte eines Rechtecks zeigen (angenommen, dass jeder Abschnitt in Form eines Rechtecks ist].

Problem : Angenommen ein neuer Punkt, ich muss bestimmen, auf welchem Segment der Punkt liegt und ein neues erstellen, wenn er auf keinem von ihnen liegt. Ich lade die Daten derzeit nicht in MySQL hoch, sie kommen einfach als einfache Textdatei. Ich erhalte die Koordinaten aus der Textdatei für jedes beliebige Auto.

Was ich versucht habe : Ich überlege, R-Bäume zu verwenden, um alle Punkte zu finden, die nahe am gegebenen Punkt sind. (Nahe == maximal 200 Meter). Aber selbst bei R-Bäumen scheinen es zu viele Optionen zu geben. R, R*, Hilbert.

Q1. Auf welche sollte man sich entscheiden?

Q2. Gibt es eine bessere Option als R-Bäume? Kann etwas schneller innerhalb der Liste durchsucht werden?

Vielen Dank.

[ {a1:[........]},{a2:[.......]},{a3:[.........]},.... ,{a20:[.....]}] .

Answer 1

Ist das Problem nicht "herauszufinden, ob ein gegebener Punkt innerhalb eines bestimmten Rechtecks im 2D-Raum liegt"?

Könnte das nicht in zwei Dimensionen getrennt werden? Vergib jedem Rechteck eine ID, trenne dann in Listen von eindimensionalen Bereichen ((id, x0, x1), (id, y0, y1)) und finde alle Bereiche in beiden Dimensionen, in die der Punkt fällt. (Ich bin ziemlich sicher, dass es sehr effiziente Algorithmen dafür gibt. Du könntest sogar bereits vorhandene Dinge wie zum Beispiel sqlite nutzen.) Dann schneide einfach die erhaltenen ID-Sets und du solltest alle Rechtecke finden, in die der Punkt fällt, falls es welche gibt. (Natürlich kannst du frühzeitig abbrechen, wenn einer der eindimensionalen Abfragen kein Ergebnis liefert.)

Ich bin mir nicht sicher, ob das schneller oder klüger ist als R-Bäume oder andere räumliche Indizes. Hoffe, das hilft trotzdem.

Answer 2

import random as ra

# mein _data enthält Tupel von GPS-Lesungen
# unter dem Schlüssel (Zeile, Spalte), wissend, dass die Größe von
# Zeile und Spalte 10 ist, ergibt sich eine Gesamtabdeckung des Rasters.
# Ein weiteres Wörterbuch könnte Zeilen-/Spaltenkoordinaten in bestimmte
# nützlichere Regionsnamen übersetzen

my_data = {}

def get_region(x,y,region_size=10):
    """Erstellen eines Tupels von Zeile/Spalte basierend auf
       den bereitgestellten Werten und der Dimension des Regionsquadrats.
       Es dient nur zur Demonstration und verwendet eine eher naive Berechnung als
       Koordinate / Rasterzellengröße"""
    row = int(x / region_size)
    col = int(y / region_size)
    return (row,col)

#mache einige Beispiele und baue my_data
for loop in range(10000):
    #simuliere einige Lesungen
    x = ra.choice(range(100))
    y = ra.choice(range(100))
    my_coord = get_region(x,y)
    if my_data.get(my_coord):
        my_data[my_coord].append((x,y))
    else:
        my_data[my_coord]= [(x,y),]

print my_data