![cover](https://img-blog.csdnimg.cn/img_convert/9e12ef54e34d401db3e084404e7205bd.png)
geo算法了解学习以及选择
手写的geo算法在时间效率上要远高于另外两种方法,空间占用略少于前两种;时间上的区别主要是因为手写的geo算法不需要通过网络,直接从内存中获取,而redis虽然也是从内存中获取数据,但是要经过网络传输进行计算,mysql无论计算还是获取数据都是通过网络,时间上最慢。空间上来说,前两种方法几乎一致,都是把事件读取到内存,别的都不消耗内存空间;而手写的geo需要把桩号也录入内存,比前两种空间占用略大,
需求:通过坐标了解到距离最近的桩号/建筑/景点
Mysql:
Sql语句:
SELECT id,
ST_Distance_Sphere(
POINT(${item.longitude}, ${item.latitude}),
POINT(longitude, latitude)
) AS distance
FROM carport
where carParkId = 66
ORDER BY distance
LIMIT 1 ;
原理:
-
创建空间索引:为了支持地理空间计算,需要在存储地理数据的表上创建合适的空间索引。索引可以使用R-Tree或者其他适合地理空间数据的索引结构。
-
转换为球面坐标:将经度和纬度转换为球面坐标系中的点。经度取值范围为-180到180,纬度取值范围为-90到90。
-
计算球面距离:使用球面三角学的公式来计算两个球面坐标点之间的物理距离。MySQL中的ST_Distance_Sphere函数采用Haversine公式来计算大圆距离。
-
返回结果:ST_Distance_Sphere函数将计算得到的距离作为结果返回,单位通常是米或千米,具体取决于输入的地理坐标单位。
Redis:
const result = await redis.georadius('locations', item.longitude, item.latitude, 200, 'km', 'ASC', 'COUNT', 1);
原理:
- 对于每个地理位置,通过经纬度信息将其编码为一个唯一的Geohash值。Geohash是一种将经纬度转换为字符串的编码方式,它能够将相邻的地理位置映射到相似的编码中。
- Redis使用有序集合的数据结构来存储地理位置,其中集合的成员是地理位置的名称或标识符,分数是对应的Geohash值。
- 当需要查询附近的地理位置时,通过指定经纬度和半径信息,在存储的有序集合中进行范围查询。Redis会根据Geohash值的顺序和距离计算,在给定半径范围内检索出符合条件的地理位置。
- 结果返回时,可以获取地理位置的经纬度、距离等详细信息,以满足具体业务需求。
手写geo算法:
// 转换经纬度为弧度
function toRadians(degrees) {
return degrees * (Math.PI / 180);
}
// 计算两个经纬度坐标之间的距离长度(单位:千米)
function calculateDistance(eventLoc, K) {
const R = 6371; // 地球的半径(单位:千米)
// 将经纬度转换为弧度
const radLat1 = toRadians(eventLoc.latitude);
const radLon1 = toRadians(eventLoc.longtitude);
const radLat2 = toRadians(K.latitude);
const radLon2 = toRadians(K.longtitude);
// 差值
const dLat = radLat2 - radLat1;
const dLon = radLon2 - radLon1;
// 应用Haversine公式计算距离
const a = Math.sin(dLat/2)**2 + Math.cos(radLat1) * Math.cos(radLat2) * Math.sin(dLon/2)**2;
const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
const distance = R * c;
return distance;
}
function executeQuery(location, K_Nos) {
let disMap = new Map()
for (Kitem of K_Nos) {
disMap.set(Kitem.id, calculateDistance(location, Kitem))
}
const keys = Array.from(disMap.keys());
const minKey = Math.min(...keys);
return minKey
}
原理:
-
将经纬度坐标转换为弧度制。将经度乘以π/180,将纬度乘以π/180,即可得到对应的弧度值。
-
使用Haversine公式计算两个点之间的球面距离。Haversine公式如下:
a = sin²((lat₂ - lat₁) / 2) + cos(lat₁) * cos(lat₂) * sin²((lon₂ - lon₁) / 2) c = 2 * atan2(√a, √(1 - a)).
distance = R * c.
-
其中,
lat₁
和lon₁
是第一个点的纬度和经度,lat₂
和lon₂
是第二个点的纬度和经度,R
是地球的半径(通常取平均半径约为6,371千米)。 -
重复计算步骤2,得到每对经纬度之间的距离。
-
取出最小距离。遍历所有计算得到的距离,找到最小值即可。
总结:
手写的geo算法在时间效率上要远高于另外两种方法,空间占用略少于前两种;
时间上的区别主要是因为手写的geo算法不需要通过网络,直接从内存中获取,而redis虽然也是从内存中获取数据,但是要经过网络传输进行计算,mysql无论计算还是获取数据都是通过网络,时间上最慢。
空间上来说,前两种方法几乎一致,都是把事件读取到内存,别的都不消耗内存空间;而手写的geo需要把桩号也录入内存,比前两种空间占用略大,这个大小差是桩号个数×12字节(桩号id,经纬度各四个字节)
持久化角度来说,数据库的持久化肯定是最好的;redis比手写geo要好一点,在不过期,不关机的情况下一般不会丢失数据;手写geo只能放在内存中,一旦程序关闭,数据就会丢失,持久化较差。
更多推荐
所有评论(0)