我有以下形式的清单清单
[[x1,.....,x8],[x1,....,x8],......,[x1,.... .x [8]]。该列表中的列表数量最多可以达到一百万。每个列表有4个gps坐标,这些坐标显示一个矩形的四个点(假设每个段都是矩形形式)。
问题:给定一个新点,我需要确定该点落在哪个段上,如果没有落在该段上,则创建一个新段。到目前为止,我还没有将数据上传到MySQL,它以简单的文本文件形式出现。我从任何给定汽车的文本文件中找到坐标。
我尝试过的事情:我正在考虑使用R树来查找所有接近给定点的点。 (近== 200米最大)。但是即使在R树中,似乎也有太多选择。 R,R *,希尔伯特。
Q1。应该选择哪一个?
Q2。有比R树更好的选择吗?可以通过在列表中更快地搜索来完成某些事情吗?
非常感谢。
[{a1:[........]},{a2:[.......]},{a3:[.........]},.... ,{a20:[.....]}]。
最佳答案
问题不是“确定给定点是否在2D空间中的某个矩形内”吗?
那可以在维度上分开,不是吗?给每个矩形一个ID,然后分成一维范围((id, x0, x1)
,(id, y0, y1)
)的列表,并找到该点所属的两个维的所有范围。然后,只要将获得的ID集相交,就应该找到该点所属的所有矩形(如果有的话)。 (当然,如果任何一维查询均未返回结果,则可以提早退出。)
不知道这是否会比R树或other spatial indexes更快或更聪明。希望这对您有所帮助。
关于python - GPS坐标搜索-R树,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/6568109/