两种高效计算 两个经纬度之间距离的方法--解决Haversine 公式性能慢的问题

发布时间:2024年01月04日

目录

前言? ??

Haversine

原理

实现代码

优化后的距离计算

原理

代码

性能及精度对比


前言? ??

?最新开发的业务中,涉及到计算两个经纬度之间的距离。已知A点和B点的 经纬度,计算A点到B点之间的距离。最开始使用的是Haversine公式来进行计算,但上线后出现严重的性能问题,主要原因是业务数据量太大,每天PB级的数据量。

因此,需要研究一个更高效便捷的计算方法,下面将介绍Haversine公式和实现代码,以及新的计算公式&代码,并对他们的性能及精度进行分析。

Haversine

原理

Haversine 公式是一种用于计算球面上两个坐标点之间距离的数学公式,特别适用于地球上的球面距离计算。该公式基于球面三角学,利用球面上两点间的弧长来计算它们之间的距离。这个公式的形式如下:

总的来说,Haversine 公式通过计算球面上两点间的弧长,提供了一种相对精确的球面距离计算方法。这种方法在小球面(如地球)上非常常见,并在航海、导航等领域广泛应用。

实现代码

public class DistanceCalculator {

    // 地球半径,单位为千米
    private static final double EARTH_RADIUS = 6371.0;

    // 将角度转换为弧度
    private static double toRadians(double degree) {
        return degree * Math.PI / 180.0;
    }

    // 计算两个经纬度之间的距离,返回结果单位为千米
    public static double calculateDistance(double lat1, double lon1, double lat2, double lon2) {
        double dLat = toRadians(lat2 - lat1);
        double dLon = toRadians(lon2 - lon1);

        double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) +
                Math.cos(toRadians(lat1)) * Math.cos(toRadians(lat2)) *
                        Math.sin(dLon / 2) * Math.sin(dLon / 2);

        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

        return EARTH_RADIUS * c;
    }

    public static void main(String[] args) {
        // 示例坐标:纬度 Latitude 1: 40.748817, 经度 Longitude 1: -73.985428
        // 示例坐标:纬度 Latitude 2: 34.052235, 经度 Longitude 2: -118.243683
        double distance = calculateDistance(40.748817, -73.985428, 34.052235, -118.243683);

        System.out.println("Distance between the two coordinates: " + distance + " km");
    }
}

如果对计算性能不是特别严苛,可以优先使用Haversine 公式来进行计算。但是对于TB级或者PB量级的数据业务来说,这个公式由于计算过于复杂,存在比较大的性能问题。

通过火焰图分析,主要是Math.atan2() 函数的计算开销比较大。

优化后的距离计算

原理

使用弧度计算的简单直线距离计算公式:

由于地球的半径很大,在一个很小的区域内(公里级)可以近似成一个平面,这里直接采用勾股定理来计算直线距离。虽然精度可能会略有降低,但是由于计算公式很简单,性能会有极大提升。

代码

public class SimpleDistanceCalculator {

    // 将角度转换为弧度
    private static double toRadians(double degree) {
        return degree * Math.PI / 180.0;
    }

    // 计算两个经纬度之间的简易直线距离,返回结果单位为千米
    public static double calculateSimpleDistance(double lat1, double lon1, double lat2, double lon2) {
        double dLat = toRadians(lat2 - lat1);
        double dLon = toRadians(lon2 - lon1);

        // 使用简化的直线距离公式
        double distance = Math.sqrt(dLat * dLat + dLon * dLon) * 60 * 1.852;

        return distance;
    }

    public static void main(String[] args) {
        // 示例坐标:纬度 Latitude 1: 40.748817, 经度 Longitude 1: -73.985428
        // 示例坐标:纬度 Latitude 2: 34.052235, 经度 Longitude 2: -118.243683
        double simpleDistance = calculateSimpleDistance(40.748817, -73.985428, 34.052235, -118.243683);

        System.out.println("Simple distance between the two coordinates: " + simpleDistance + " km");
    }
}

性能及精度对比

前者计算1千万次使用的时间为:4462ms

优化后计算1千万次使用的时间为:244ms

优化后耗时为原来的 5.4%。

精度上,在短距离(例如 5 公里以内),Haversine 公式和等矩形投影(简化后的方法)之间的精度差异可能不会很大。在这个范围内,球面和平面的差异相对较小,因此简化的方法通常能够提供足够的精度。

然而,具体的精度差异会受到多个因素的影响,包括具体的坐标位置、所使用的地球半径,以及计算时是否考虑了地球的椭球形状等。因此,很难给出一个具体的数字来表示它们之间的精度差异。

为了获取更准确的精度比较,最好的方法是使用实际的测试数据,并比较两种方法得到的结果。你可以选择一些已知距离的坐标点,分别使用 Haversine 公式和等矩形投影计算它们之间的距离,然后比较计算结果。

本人的一个实际路测,在5公里范围内,大约存在5%到15% 之间的差异。

文章来源:https://blog.csdn.net/samur2/article/details/135378818
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。