python - GPS坐标搜索--R树

Question

我有一个

形式的列表列表

[ [ x1,.......,x8],[x1,.......,x8].......,[x1,. ....x[8]] ] 。该列表中的列表数量最多可达一百万。每个列表有 4 个 gps 坐标，显示矩形的四个点(假设每个线段都是矩形的形式)。

问题:给定一个新点，我需要确定该点落在哪个线段上，如果不落在任何线段上，则创建一个新点。我现在还没有将数据上传到 MySQL，它以一个简单的文本文件的形式出现。我从文本文件中找出任何给定汽车的坐标。

我尝试了什么:我正在考虑使用 R 树来查找所有靠近给定点的点。 (近 == 最大 200 米)。但即使在 R 树中，似乎也有太多选择。 R,R*,希尔伯特。

Q1。应该选择哪一个？

Q2。有比 R 树更好的选择吗？可以通过在列表中更快地搜索来完成某些事情吗？

非常感谢。

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

Answer 1

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

那可以在维度上分开，不是吗？给每个矩形一个 ID，然后分成一维范围列表((id, x0, x1), (id, y0, y1))并找到所有点落入的两个维度的范围。(我相当确定有非常有效的算法。哎呀，你甚至可以利用，比如说，sqlite。)然后只需与你获得的 ID 集相交，你应该找到所有矩形如果有的话，重点在于。 (当然如果单维查询没有返回结果也可以提前退出。)

不确定这是否比 R 树或 other spatial indexes 更快或更智能尽管。希望这有帮助。