我有以下形式的清单清单
[[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/