地理位置距离计算的优化

问题:给定1万个POI点,需要实现的功能:给定一个POI点,能够迅速寻找出其1000米以内的其他POI点。

解决此问题的关键是减少计算的复杂度,如果用最原始的方法,需要计算的次数为$n^2$。

常规方案:Geohash法

将所有经纬度转化为特定精度的GeoHash值,再对同一Geohash内的内进行两两比较,以此减少计算复杂度。

存在问题:GeoHash的划分方式导致了其必产生边界问题(相邻的两个POI被划分到了不同的区域)

解决方案:将Geohash内的POI与Geohash的另外8个邻居中的POI再进行两两计算。由于涉及网格间的计算,程序的复杂度也会相应增加

Hack方案:基于经纬度精度

在先前的经纬度精度的文章中,我们介绍了如下信息

在纬度相等的情况下:

  • 经度每隔0.00001度,距离相差约1米
  • 经度每隔0.0001度,距离相差约10米
  • 经度每隔0.001度,距离相差约100米
  • 经度每隔0.01度,距离相差约1000米
  • 经度每隔0.1度,距离相差约10000米

在经度相等的情况下:

  • 纬度每隔0.00001度,距离相差约1.1米
  • 纬度每隔0.0001度,距离相差约11米
  • 纬度每隔0.001度,距离相差约111米
  • 纬度每隔0.01度,距离相差约1113米
  • 纬度每隔0.1度,距离相差约11132米

由于以上数据,再结合1000米以内的需求。我们可以再笛卡尔积的基础上通过精度和纬度的差值过滤掉很大一部分数据。

Python实战

1、生成笛卡尔积

使用Pandas的merge函数即可实现,示例代码如下:

2、优化经纬度距离计算公式

常规经纬度距离计算方案:

由于要计算的距离范围非常的小,我们可以将球面上的经线和纬线看成是垂直的。如图:

想要计算AB两个点距离$D = \sqrt{\text{AM}^2+\text{BM}^2}$,转化为Python代码为:

3、计算经纬度距离

最终结果:

微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

分层时间记忆HTM学习笔记

分层时间记忆算法(Hierarchical Temporal Memory),全称HTM Cortical L

Expedia异常检测项目Adaptive Alerting

Adaptive Alerting(AA)是Expedia开源的异常检测项目,整个项目也是完整一套监控体系,包

格兰杰因果关系检验学习笔记

格兰杰因果关系检验简介 格兰杰因果关系检验(英语:Granger causality test)是一种假设检定

发表评论

电子邮件地址不会被公开。 必填项已用*标注