geo算法了解学习以及选择

手写的geo算法在时间效率上要远高于另外两种方法，空间占用略少于前两种；时间上的区别主要是因为手写的geo算法不需要通过网络，直接从内存中获取，而redis虽然也是从内存中获取数据，但是要经过网络传输进行计算，mysql无论计算还是获取数据都是通过网络，时间上最慢。空间上来说，前两种方法几乎一致，都是把事件读取到内存，别的都不消耗内存空间；而手写的geo需要把桩号也录入内存，比前两种空间占用略大，

ArmadaDK

324人浏览 · 2023-08-22 16:56:33

ArmadaDK · 2023-08-22 16:56:33 发布

需求：通过坐标了解到距离最近的桩号/建筑/景点

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，得到每对经纬度之间的距离。
取出最小距离。遍历所有计算得到的距离，找到最小值即可。