地图上的算法--位置分组
地图上的算法--位置分组
提问于 2017-09-17 06:27:42
我有一个n个位置的列表，每个位置包括一个纬度、经度和一个时间戳。这些地点将被钉在地图上。
然而，它需要分组的位置是接近的，最近改变的位置为中心，这样地图就不会被引脚淹没。
我最初的想法是：
- 按时间戳对位置进行排序
- 选择最新位置
- 计算n-1位置到最新位置的距离。
- 选择半径范围内的位置，例如5公里，然后将它们从列表中删除
- 重复步骤2-4
这种方法有效，但效率很低。最坏的情况是~O(n^2)。
有什么算法可以做得更好吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2017-09-17 13:51:51
若要击败二次运行时，请使用索引。
在纬度和经度上，您可能需要使用R树、球树、覆盖树或类似的树，因为kd树显然只适用于欧几里得距离，而不是haversine。
Stack Overflow用户
发布于 2017-09-17 19:16:11
我有一个麻烦的解决方案给你，如果你对大致的答案满意的话，它可能会有效。
通常，纬度经度超过几个小数点，如(12.9877949,77.6095064)。现在，你只能在小数点之后选择几个数字，这通常是在几公里之内。
和12.9877979,77.6095054类似，接近12.9877949,77.6095064，所以如果我只取两个小数点，两者都会变成12.98,77.60，现在我遍历这个列表，选择那些值相同的。
但是，如果您需要非常精确的计算，这将无法工作。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/46261332
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号