GPS坐标搜索树

Question

我有一份清单

[[x1，…，x8]，[x1，…..x8]，………………，[x1，…..x[8]]]。这个列表中的列表数量可以达到一百万。每个列表有4个gps坐标，显示矩形的四个点（假设每个线段都是矩形的形式）。在

问题：给定一个新点，我需要确定该点落在哪个线段上，如果该点不在其中，则创建一个新线段。我现在还没有把数据上传到MySQL，它只是一个简单的文本文件。我从文本文件中找出每辆车的坐标。在

我尝试了：我正在考虑使用R-树来寻找所有接近给定点的点。（接近最大值=200米）。但即使在R-树中，似乎也有太多的选择。R、 希尔伯特。在

问题1。应该选择哪一个？在

问题2。有比R-树更好的选择吗？通过在列表中更快地搜索可以做些什么吗？在

非常感谢。在

[{a1:[………]}，{a2:[…..]}，{a3:[………]}，。。。。，{a20:[……]}]。在

Answer 1

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

Answer 2

问题不在于“找出给定点是否落在二维空间的某个矩形内”？在

可以在空间上分开，不是吗？给每个矩形一个ID，然后将其分成一维范围的列表（(id, x0, x1)，(id, y0, y1)），并找到点所在的两个维度中的所有范围。（我相当肯定有非常有效的算法来解决这个问题。见鬼，你甚至可以利用，比如说，sqlite）然后只要相交你得到的ID集，你就可以找到所有的矩形点，如果有的话。（当然，如果有一个一维查询没有返回结果，您可以提前退出。）

但不确定这是否比R-trees或other spatial indexes更快或更聪明。希望这有帮助。在