问题描述
咳咳，是这样的，所有的好友都有个经纬度，我现在已知道自己的经纬度，想把5公里以内的好友列表全取出来，这个应该有个算法，大家是怎么搞的？在线等候给分，100分哦……，万分火急，加急………………………………
解决方案
解决方案二：
这个方法用于计算两个点之间的距离privatestaticdoubledistance(doublelon1,doublelat1,doublelon2,doublelat2){doublepi=0.0174532925199432944;//PI/180;doublet5=Math.sin(lat1*pi)*Math.sin(lat2*pi)+Math.cos(lat1*pi)*Math.cos(lat2*pi)*Math.cos((lon1-lon2)*pi);return(Math.atan(-t5/Math.sqrt(-t5*t5+1))+2*Math.atan(1))*3437.74677*1.1508*1.6093470878864446*1000;}
解决方案三：
引用1楼xie609的回复:
这个方法用于计算两个点之间的距离privatestaticdoubledistance(doublelon1,doublelat1,doublelon2,doublelat2){doublepi=0.0174532925199432944;//PI/180;doublet5=Math.sin(lat1*pi)*Math.sin(lat2*pi)+Math.cos(lat1*pi)*Math.cos(lat2*pi)*Math.cos((lon1-lon2)*pi);return(Math.atan(-t5/Math.sqrt(-t5*t5+1))+2*Math.atan(1))*3437.74677*1.1508*1.6093470878864446*1000;}
学习一下
解决方案四：
引用1楼xie609的回复:
这个方法用于计算两个点之间的距离privatestaticdoubledistance(doublelon1,doublelat1,doublelon2,doublelat2){doublepi=0.0174532925199432944;//PI/180;doublet5=Math.sin(lat1*pi)*Math.sin(lat2*pi)+Math.cos(lat1*pi)*Math.cos(lat2*pi)*Math.cos((lon1-lon2)*pi);return(Math.atan(-t5/Math.sqrt(-t5*t5+1))+2*Math.atan(1))*3437.74677*1.1508*1.6093470878864446*1000;}
我算的不是两个点，我是5公里以内的所有点
解决方案五：
知道两个点的距离怎么计算了，做一次对所有好友的迭代，一一计算距离不就出来了？或者说，你是考虑性能问题，好友太多，距离计算量太大？比如R-tree？
解决方案六：
引用4楼deltatang的回复:
知道两个点的距离怎么计算了，做一次对所有好友的迭代，一一计算距离不就出来了？或者说，你是考虑性能问题，好友太多，距离计算量太大？比如R-tree？
是的，好友太多，其实不是好友也得列出来，就是不可能把所有的人的距离都算出来再处理，因为速度确实慢。
解决方案七：
引用5楼tjcyjd的回复:
Quote: 引用4楼deltatang的回复:
知道两个点的距离怎么计算了，做一次对所有好友的迭代，一一计算距离不就出来了？或者说，你是考虑性能问题，好友太多，距离计算量太大？比如R-tree？是的，好友太多，其实不是好友也得列出来，就是不可能把所有的人的距离都算出来再处理，因为速度确实慢。
俺不是给你提示了么？R-Tree。。。或者gg一下高维检索空间划分虾米的这方面的paper是很多的
解决方案八：
引用3楼tjcyjd的回复:
Quote: 引用1楼xie609的回复:
这个方法用于计算两个点之间的距离privatestaticdoubledistance(doublelon1,doublelat1,doublelon2,doublelat2){doublepi=0.0174532925199432944;//PI/180;doublet5=Math.sin(lat1*pi)*Math.sin(lat2*pi)+Math.cos(lat1*pi)*Math.cos(lat2*pi)*Math.cos((lon1-lon2)*pi);return(Math.atan(-t5/Math.sqrt(-t5*t5+1))+2*Math.atan(1))*3437.74677*1.1508*1.6093470878864446*1000;}我算的不是两个点，我是5公里以内的所有点
可以先对数据进行一些简单的处理，比如先根据已知的经纬度和5公里这个距离，得出一个经度和纬度的边界值，也就是地图上的一个矩形范围，用这个边界值先过滤一遍好友列表，然后再计算距离进行过滤，这是简单的两步处理。其实即使是第二步，也不是所有的点都要计算的，比如假设已知点A经纬度分别为a1,a2你已经计算出一个点B(b1,b2)在这个范围内，如果有个点C(c1,c2)，满足a1<c1<b1且a2<c2<b2的话肯定也在这个范围内的（当然如果a1>b1的话前边的式子就得用>了，a2b2亦然）
解决方案九：
引用7楼xie609的回复:
Quote: 引用3楼tjcyjd的回复:
Quote: 引用1楼xie609的回复:
这个方法用于计算两个点之间的距离privatestaticdoubledistance(doublelon1,doublelat1,doublelon2,doublelat2){doublepi=0.0174532925199432944;//PI/180;doublet5=Math.sin(lat1*pi)*Math.sin(lat2*pi)+Math.cos(lat1*pi)*Math.cos(lat2*pi)*Math.cos((lon1-lon2)*pi);return(Math.atan(-t5/Math.sqrt(-t5*t5+1))+2*Math.atan(1))*3437.74677*1.1508*1.6093470878864446*1000;}我算的不是两个点，我是5公里以内的所有点
可以先对数据进行一些简单的处理，比如先根据已知的经纬度和5公里这个距离，得出一个经度和纬度的边界值，也就是地图上的一个矩形范围，用这个边界值先过滤一遍好友列表，然后再计算距离进行过滤，这是简单的两步处理。其实即使是第二步，也不是所有的点都要计算的，比如假设已知点A经纬度分别为a1,a2你已经计算出一个点B(b1,b2)在这个范围内，如果有个点C(c1,c2)，满足a1<c1<b1且a2<c2<b2的话肯定也在这个范围内的（当然如果a1>b1的话前边的式子就得用>了，a2b2亦然）
或者你也可以这样优化。如上图你已经计算出B点在5公里范围内了，可以根据B点和A点的经纬度差值，再构建一个矩形区域，那么在这个区域中的点都无需再计算了肯定都在这个范围内了。（当然你也可以直接计算5公里这个圆的内接正方形进行过滤，那么就只有少量的位于内接正方形以外的点需要计算距离了）
解决方案十：
引用8楼xie609的回复:
Quote: 引用7楼xie609的回复:
Quote: 引用3楼tjcyjd的回复:
Quote: 引用1楼xie609的回复:
这个方法用于计算两个点之间的距离privatestaticdoubledistance(doublelon1,doublelat1,doublelon2,doublelat2){doublepi=0.0174532925199432944;//PI/180;doublet5=Math.sin(lat1*pi)*Math.sin(lat2*pi)+Math.cos(lat1*pi)*Math.cos(lat2*pi)*Math.cos((lon1-lon2)*pi);return(Math.atan(-t5/Math.sqrt(-t5*t5+1))+2*Math.atan(1))*3437.74677*1.1508*1.6093470878864446*1000;}我算的不是两个点，我是5公里以内的所有点
可以先对数据进行一些简单的处理，比如先根据已知的经纬度和5公里这个距离，得出一个经度和纬度的边界值，也就是地图上的一个矩形范围，用这个边界值先过滤一遍好友列表，然后再计算距离进行过滤，这是简单的两步处理。其实即使是第二步，也不是所有的点都要计算的，比如假设已知点A经纬度分别为a1,a2你已经计算出一个点B(b1,b2)在这个范围内，如果有个点C(c1,c2)，满足a1<c1<b1且a2<c2<b2的话肯定也在这个范围内的（当然如果a1>b1的话前边的式子就得用>了，a2b2亦然）
或者你也可以这样优化。如上图你已经计算出B点在5公里范围内了，可以根据B点和A点的经纬度差值，再构建一个矩形区域，那么在这个区域中的点都无需再计算了肯定都在这个范围内了。（当然你也可以直接计算5公里这个圆的内接正方形进行过滤，那么就只有少量的位于内接正方形以外的点需要计算距离了）
嗯，非常不错的建议，还有没有其它的办法
解决方案十一：
利用GeoHash值做索引来实现快速查找和粗排序，在利用计算两点间距离实现精确距离计算和精确排序。实际上这里的问题主要是解决计算量大的问题，我们的解决方案是为了快速定位和减少计算，否则用户想查出5公里范围的好友如果需要很长时间，我想他早也没有心气看了。方案：使用redis做缓存，使用你的经纬度计算出来的的GeoHash的code值得前8、7、6、5位建立四个桶，你的好友或是其他用户如果登录系统也会用他们的经纬度计算出一个GeoHash的code，这些人都会按照8、7、6、5的顺序放入桶内，这样这些桶里就有你想要的人了，取桶的顺序是8、7、6、5依次来，当然一般用户在手机上能翻几页也就够了，所以一般8、7里面的数据就已经满足用户的翻页需求了，剩下的估计就是搜索了，那其实同样的逻辑。注意：8桶的人一定会在7桶里，一次类推，但是反过来就不成立，所以你要记得去重。希望这样简单的介绍对你有所帮助！