algorithm - 如何查找位置点集是否包含距离大于 1 公里的点

Question

我有一组用户，每个用户都有一组由经纬度表示的点(n~5000)。 我需要找到静态用户。 “静态”是指没有超过 1 公里的点对的用户。最好的算法是什么？

Answer 1

一组点中任意一对点之间的最大距离称为该组的直径。

这是一种基于凸包的高效算法，用于解决此问题:

• http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_ss_07w/Webprojects/Qinbo_diameter/2d_alg.htm
• http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2000/MS/diameter/node2.html

由于您可能不关心此处的准确性，因此更容易找到所有点的最小和最大纬度和经度，并测试由这些极值定义的框的一侧是否大于某些临界点。假设您不关心北极或南极附近的用户，这是可行的。