Поиск GPS-координат - R-деревья

Question

У меня есть список списков в виде

[[x1, ....., x8], [x1, ......., x8], ..............., [x1 ,. .... х [8]]]. Количество списков в этом списке может доходить до миллиона. Каждый список имеет координаты 4 gps, которые показывают четыре точки прямоугольника (предполагается, что каждый сегмент имеет форму прямоугольника).

Проблема: Учитывая новую точку, мне нужно определить, на какой сегмент падает точка, и создать новый, если он не попадает ни в один из них. На данный момент я не загружаю данные в MySQL, это простой текстовый файл. Я узнаю координаты из текстового файла для любой машины.

Что я пробовал: я думаю об использовании R-деревьев, чтобы найти все точки, которые находятся близко к данной точке. (Около == 200 метров максимум). Но даже в R-деревьях кажется, что вариантов слишком много. R, R *, Гильберт.

Q1. Какой из них следует выбрать?

Q2. Есть ли лучший вариант, чем R-деревья? Можно ли что-то сделать, выполнив более быстрый поиск в списке?

Большое спасибо.

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

Answer 1

Не проблема ли "найти, попадает ли данная точка в определенный прямоугольник в 2D-пространстве" ?

Это могло бы быть разделено размерно, не так ли? Дайте каждому прямоугольнику идентификатор, затем разделите его на списки одномерных диапазонов ((id, x0, x1), (id, y0, y1)) и найдите все диапазоны в обоих измерениях, в которые попадает точка. (Я совершенно уверен, что для этого есть очень эффективные алгоритмы Черт возьми, вы могли бы даже использовать, скажем, sqlite.) Затем просто пересекайте наборы идентификаторов, которые вы получаете, и вы должны найти все прямоугольники, в которые попадает точка, если таковые имеются. (Конечно, вы можете выйти раньше, если один из одномерных запросов не даст результата.)

Не уверен, что это будет быстрее или умнее, чем R-деревья или другие пространственные индексы . Надеюсь, это поможет в любом случае.

Answer 2

import random as ra

# my _data will hold tuples of gps readings
# under the key of (row,col), knowing that the size of 
# the row and col is 10, it will give an overall grid coverage.
# Another dict could translate row/col coordinates into some 
# more usefull region names

my_data = {}


def get_region(x,y,region_size=10):
    """Build a tuple of row/col based on
       the values provided and region square dimension.
       It's for demonstration only and it uses rather naive calculation as
       coordinate / grid cell size"""
    row = int(x / region_size)
    col = int(y / region_size)
    return (row,col)


#make some examples and build my_data
for loop in range(10000):
    #simule some readings
    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