GPS坐标搜索-R-树

我有一个列表的形式GPS坐标搜索-R-树

[[x1，.....，x8]，[x1，....... ，x8]，...............，[x1，..... x [8]]]。该清单中的清单数量可能高达一百万。每个列表有4个gps坐标，显示一个矩形的四个点（假设每个分段都是矩形的形式）

问题：给定一个新点，我需要确定点落在哪个段并创建一个新的，如果它不属于它们的话，我现在不会将数据上传到MySQL中，它只是一个简单的文本文件，我从任何给定的汽车的文本文件中找到坐标

我尝试过：我正在考虑使用R-tree来找到所有靠近给定点的点（最大接近== 200米），但即使在R树中，也似乎也是如此许多选择R，R *，希尔伯特

Q1。哪一个应该选择？ Q2302。有没有比R-trees更好的选择？可以通过在列表中更快地搜索来完成某些工作吗？

非常感谢。

[{a1：[........]}，{a2：[.......]}，{a3：[.........]}， ....，{a20：[.....]}]。

来源

2011-07-04 crazyaboutliv

是否可以在保存坐标点时计算段引用？那么我可能只用一个字典，其中的关键字是段，然后检查“if mydict.get（region）：listofcoordinates.append（newones）else mydict [region] = [newcoordinates]”，如果该区域已经存在或不。 – Damian

不是问题“找到一个给定的点是否落在2D空间一定矩形内”？

这可以在尺寸上分开，不是吗？给每个矩形一个ID，然后分成一维范围列表（(id, x0, x1),(id, y0, y1)），并找到所有这两个方面的范围内的点（我相当肯定有这个非常有效的算法。哎呀，你甚至可以利用sqlite已经）。然后只是相交的ID集，你应该找到所有矩形点，如果有的话。（当然，如果单维查询中的任何一个都没有返回结果，你可以提早退出。）

不知道这是否比R-trees或other spatial indexes更快或更聪明。无论如何希望这有助于。

来源

2011-07-04 12:47:36 AKX

谢谢。我还没有考虑利用现有的Db方法实际上:(我应该给它更认真的想法 – crazyaboutliv

我在想，如果我使用DB，它会是可扩展的吗？会有单点故障吗？如果我使用lucene？请问这有助于改变吗？我想用B和B +树，它不会是可扩展的。请纠正我，如果我错了 – crazyaboutliv

取决于数据库，我猜。（但是，如果我没有记错的话，只能在MyISAM表上 - 不知道这是否与您的部署有关。） – AKX

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

来源

2011-07-04 10:08:50 Damian

这是如何回答OP询问的任何问题？ – Constantinius

它提出了一种不同的网格工作方法，而不是试图找出当前阅读与以前所有阅读的关系，但我认为它可以解决潜在的问题。也许不会，我们会看到的。 – Damian

我找到了最小和最大的经度，并分成20个区间，我只是像上面提到的那样在字典中存储区间。我很乐意回答R-trees部分，因为他们看起来仍然是更好的选择，尤其是有太多的细分市场（我真的会有太多的细分市场） – crazyaboutliv

GPS坐标搜索-R-树

回答

相关问题