算法 - 在地图上对位置进行分组
Algorithm - grouping locations on map
我有一个包含 n 个位置的列表，每个位置都包含纬度、经度和时间戳。这些位置将固定在地图上。
但是，需要将靠近的位置分组，以最近更改的位置为中心，这样地图就不会被图钉淹没。
我最初的想法是：
- 按时间戳对位置进行排序
- Select最新位置
- 计算到 n-1 个位置的最新位置的距离
- Select 半径内的那些位置，比如 5 公里，然后将它们从列表中删除
- 重复步骤 2-4
此方法有效，但效率极低。最坏的情况是〜O（n ^ 2）。
是否有任何算法可以更好地执行？
要击败二次运行时间，请使用索引。
关于纬度和经度，您可能想要使用 R 树、球树、覆盖树或类似树，因为 kd 树显然只适用于欧几里德距离，而不是半正弦。
我有一个适合你的 hacky 解决方案，如果你对大概的答案没有问题，它可能会奏效。
一般纬度经度会超过小数点后几位，如(12.9877949,77.6095064)。现在你可以 select 小数点后只有几位数字，而且通常在几公里以内。
比如 12.9877979、77.6095054 更接近 12.9877949、77.6095064，所以如果我只取小数点后 2 位，两者都将变为 12.98、77.60，现在我浏览列表并选择具有相同值的那些。
但是，如果您需要非常精确的计算，这将不起作用
我有一个包含 n 个位置的列表，每个位置都包含纬度、经度和时间戳。这些位置将固定在地图上。
但是，需要将靠近的位置分组，以最近更改的位置为中心，这样地图就不会被图钉淹没。
我最初的想法是：
- 按时间戳对位置进行排序
- Select最新位置
- 计算到 n-1 个位置的最新位置的距离
- Select 半径内的那些位置，比如 5 公里，然后将它们从列表中删除
- 重复步骤 2-4
此方法有效，但效率极低。最坏的情况是〜O（n ^ 2）。
是否有任何算法可以更好地执行？
要击败二次运行时间，请使用索引。
关于纬度和经度，您可能想要使用 R 树、球树、覆盖树或类似树，因为 kd 树显然只适用于欧几里德距离，而不是半正弦。
我有一个适合你的 hacky 解决方案，如果你对大概的答案没有问题，它可能会奏效。
一般纬度经度会超过小数点后几位，如(12.9877949,77.6095064)。现在你可以 select 小数点后只有几位数字，而且通常在几公里以内。
比如 12.9877979、77.6095054 更接近 12.9877949、77.6095064，所以如果我只取小数点后 2 位，两者都将变为 12.98、77.60，现在我浏览列表并选择具有相同值的那些。
但是，如果您需要非常精确的计算，这将不起作用