Python中的对称“字符串”矩阵

Question

我有一组（相当大的）经纬度的gps点，外加一个名称；例如：

A    30.22    20.45
B    31.00    20.45
...

现在，我需要建立一个矩阵，告诉我A是否与B“接近”（<1 km）。但是我不需要计算每对，因为如果A接近B，那么B就是接近到A。在不执行所有计算的情况下构建此矩阵（或其一半）的最佳方法是什么？

我有一组（相当大的）经纬度的gps点，外加一个名称；例如：A 30.22 20.45 B 31.00 20.45 ...现在我需要建立一个矩阵，告诉我A是否为“ ...

Answer 1

问题与众所周知的closest pair of points problem非常相似。您可以找到一些解决方案here。在这种情况下，可以在O（nlogn）时间中找到最佳解。但是，我认为并非如此。