如何有效地检查一个GPS坐标是否接近成千上万个其他坐标？

Question

我有1100万个GPS坐标要分析，效率是我的主要问题。问题如下： 我想保持每50米半径只有一个GPS坐标（称为节点）。所以代码非常简单，我有一个集合G，对于G中的每个节点，我检查我要添加的节点是否与其他节点太接近。如果太近（<；50米），我就不加了。否则我会加上它。你知道吗

问题是集合G增长得很快，最后要检查是否要向集合中添加一个节点，我需要在数百万个元素上运行for循环。。。你知道吗

下面是节点类的简化代码：

from geopy import distance

class Node: #a point on the map
    def __init__(self, lat, long): #lat and long in degree
        self.lat = lat
        self.long = long

    def distanceTo(self, otherNode):
        return distance.distance((self.lat, self.long), (otherNode.lat, otherNode.long)).km

    def equivalent(self, otherNode):
        return self.distanceTo(otherNode) < 0.05 #50 meters away

以下是“添加”过程：

currentNode = Node(lat, long)

alreadyIn = False
for n in graph:
    if n.equivalent(currentNode):
        alreadyIn = True
        break

#set of Nodes
if alreadyIn == False:
    G.add(currentNode)

这不是节点集群的问题，因为我不尝试检测数据集中的任何模式。我只是想把50米半径内的节点分组。你知道吗

我认为最好的方法是有一个数据结构，给定的坐标返回True或False（如果集合中有相似的节点）。但是我不知道该用哪一个，因为我没有把环境划分成正方形而是圆形。（是的，节点a可以等价于B和C，而B和C不等价，但我真的不介意……）。你知道吗

谢谢你的帮助！你知道吗

Answer 1

对于这样的计算，使用面向对象的方法通常比较慢（尽管可读性更强）。你知道吗

您可以将纬度、经度转换为笛卡尔坐标的x、y、z，并从节点创建numpy数组，并使用scipy的非常快的cKDTree。它为这样的操作提供了几种方法，在您的例子中^{}可能是正确的方法。你知道吗