找到两个纬度/长点之间距离的最快方法-Java 学习之路

210

我目前在mysql数据库中的位置不到一百万个，都有经度和纬度信息 .

我试图通过查询找到一个点和许多其他点之间的距离 . 它并不像我想要的那么快，特别是每秒100次点击 .

是否有更快的查询或可能比mysql更快的系统？我正在使用此查询：

SELECT 
  name, 
   ( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) ) 
   * cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763)) 
   * sin( radians(locations.lat)))) AS distance 
FROM locations 
WHERE active = 1 
HAVING distance < 10 
ORDER BY distance;

注意：提供的距离在 Miles 中 . 如果需要 Kilometers ，请使用 6371 而不是 3959 .

16 回答

SELECT * FROM (SELECT *,(((acos(sin((43.6980168*pi()/180)) * 
sin((latitude*pi()/180))+cos((43.6980168*pi()/180)) * 
cos((latitude*pi()/180)) * cos(((7.266903899999988- longitude)* 
pi()/180))))*180/pi())*60*1.1515 ) as distance 
FROM wp_users WHERE 1 GROUP BY ID limit 0,10) as X 
ORDER BY ID DESC

这是MySQL中的点之间的距离计算查询，我在一个长数据库中使用它，它工作得很完美！注意：根据您的要求进行更改（数据库名称，表名称，列等） .

回复于 2024-05-04T20:04:54+08:00

使用 MyISAM 表中 Geometry 数据类型的 Point 值创建点 . As of Mysql 5.7.5, InnoDB tables now also support SPATIAL indices.
在这些点上创建 SPATIAL 索引
使用 MBRContains() 查找值：

SELECT  *
FROM    table
WHERE   MBRContains(LineFromText(CONCAT(
        '('
        , @lon + 10 / ( 111.1 / cos(RADIANS(@lon)))
        , ' '
        , @lat + 10 / 111.1
        , ','
        , @lon - 10 / ( 111.1 / cos(RADIANS(@lat)))
        , ' '
        , @lat - 10 / 111.1 
        , ')' )
        ,mypoint)

，或者，在 MySQL 5.1 及以上：

SELECT  *
    FROM    table
    WHERE   MBRContains
                    (
                    LineString
                            (
                            Point (
                                    @lon + 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat + 10 / 111.1
                                  ),
                            Point (
                                    @lon - 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat - 10 / 111.1
                                  ) 
                            ),
                    mypoint
                    )

这将选择约 (@lat +/- 10 km, @lon +/- 10km) 框内的所有点 .

这实际上不是一个盒子，而是一个球形矩形：球体的纬度和经度束缚段 . 这可能与 Franz Joseph Land 上的普通矩形不同，但在大多数有人居住的地方都非常接近 .

应用其他过滤以选择圆内的所有内容（不是方形）
可能应用额外的精细过滤以考虑大圆距离（对于大距离）

回复于 2024-05-04T20:04:54+08:00

111
不是MySql特定的答案，但它会提高你的sql语句的性能 .

你有效地做的是计算到表中每个点的距离，看它是否在给定点的10个单位内 .

在运行这个sql之前你可以做的是创建四个点，在一侧绘制一个20个单位的框，你的点在中心，即..（x1，y1） . . . （x4，y4），其中（x1，y1）是（给定10个单位，给定10个单位） . . . （给定长 - 10个单位，给予-10个单位） . 实际上，你只需要两个点，左上角和右下角称它们（X1，Y1）和（X2，Y2）

现在你的SQL语句使用这些点从你的给定点排除肯定超过10u的行，它可以使用纬度和经度上的索引，因此将比你现有的快几个数量级 .

例如
```
select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;
```
框方法可以返回误报（您可以从框中获取距离给定点大于10u的点），因此您仍需要计算每个点的距离 . 然而，这将再次快得多，因为你已经大大限制了要测试的点数 .

我把这种技术称为“在盒子里面思考”:)

EDIT: 这可以放在一个SQL语句中吗？

我不知道mySql或Php能做什么，抱歉 . 我不知道最好的地方是 Build 四个点，或者如何将它们传递给Php中的mySql查询 . 但是，一旦获得了这四点，就没有什么能阻止你将自己的SQL语句与我的结合起来了 .
```
select name, 
       ( 3959 * acos( cos( radians(42.290763) ) 
              * cos( radians( locations.lat ) ) 
              * cos( radians( locations.lng ) - radians(-71.35368) ) 
              + sin( radians(42.290763) ) 
              * sin( radians( locations.lat ) ) ) ) AS distance 
from locations 
where active = 1 
and locations.lat between X1 and X2 
and locations.Long between y1 and y2
having distance < 10 ORDER BY distance;
```
我知道使用MS SQL我可以构建一个声明四个浮点数（X1，Y1，X2，Y2）并在“主”选择语句之前计算它们的SQL语句，就像我说的，我不知道这是否可以用MySQL的 . 但是我仍然倾向于在C＃中构建四个点并将它们作为参数传递给SQL查询 .

抱歉，我无法提供更多帮助，如果有人能够回答MySQL和Php的具体部分，请随时编辑此答案 .
回复于 2024-05-04T20:04:54+08:00
-1

查看此演示文稿以获得一个好的答案基本上它显示了评论中显示的两种不同的方法，详细解释了为什么/何时应该使用其中一种，以及为什么“在框中”计算可能非常有趣 .

Geo Distance Search with MySQL

回复于 2024-05-04T20:04:54+08:00

在this blog post上，发布了以下MySql函数 . 我没有对它进行过多次测试，但是根据我从帖子中收集到的内容，if your latitude and longitude fields are indexed，这可能对您有用：

DELIMITER $$

DROP FUNCTION IF EXISTS `get_distance_in_miles_between_geo_locations` $$
CREATE FUNCTION get_distance_in_miles_between_geo_locations(geo1_latitude decimal(10,6), geo1_longitude decimal(10,6), geo2_latitude decimal(10,6), geo2_longitude decimal(10,6)) 
returns decimal(10,3) DETERMINISTIC
BEGIN
  return ((ACOS(SIN(geo1_latitude * PI() / 180) * SIN(geo2_latitude * PI() / 180) + COS(geo1_latitude * PI() / 180) * COS(geo2_latitude * PI() / 180) * COS((geo1_longitude - geo2_longitude) * PI() / 180)) * 180 / PI()) * 60 * 1.1515);
END $$

DELIMITER ;

Sample usage: 假设一个名为Places的表格包含纬度和经度字段：

从地点选择get_distance_in_miles_between_geo_locations（-34.017330，22.809500，纬度，经度）作为distance_from_input;

所有snagged from this post

回复于 2024-05-04T20:04:54+08:00

set @latitude=53.754842;
set @longitude=-2.708077;
set @radius=20;

set @lng_min = @longitude - @radius/abs(cos(radians(@latitude))*69);
set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
set @lat_min = @latitude - (@radius/69);
set @lat_max = @latitude + (@radius/69);

SELECT * FROM postcode
WHERE (longitude BETWEEN @lng_min AND @lng_max)
AND (latitude BETWEEN @lat_min and @lat_max);

source

回复于 2024-05-04T20:04:54+08:00

16
如果你使用MySQL 5.7 . *，那么你可以使用 st_distance_sphere(POINT, POINT) .
```
Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance
```
回复于 2024-05-04T20:04:54+08:00

select
   (((acos(sin(('$latitude'*pi()/180)) * sin((`lat`*pi()/180))+cos(('$latitude'*pi()/180)) 
    * cos((`lat`*pi()/180)) * cos((('$longitude'- `lng`)*pi()/180))))*180/pi())*60*1.1515) 
    AS distance
    from table having distance<22;

回复于 2024-05-04T20:04:54+08:00

有关如何安装MySQL插件的详细信息的完整代码如下：https://github.com/lucasepe/lib_mysqludf_haversine

我去年发布了这篇评论 . 亲爱的@TylerCollier建议我发帖回答，这里是 .

另一种方法是编写一个自定义UDF函数，该函数返回两点的半径距离 . 这个功能可以输入：

lat1 (real), lng1 (real), lat2 (real), lng2 (real), type (string - optinal - 'km', 'ft', 'mi')

所以我们可以这样写：

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2) < 40;

获取距离小于40公里的所有记录 . 要么：

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2, 'ft') < 25;

获取距离小于25英尺的所有记录 .

核心功能是：

double
haversine_distance( UDF_INIT* initid, UDF_ARGS* args, char* is_null, char *error ) {
    double result = *(double*) initid->ptr;
    /*Earth Radius in Kilometers.*/ 
    double R = 6372.797560856;
    double DEG_TO_RAD = M_PI/180.0;
    double RAD_TO_DEG = 180.0/M_PI;
    double lat1 = *(double*) args->args[0];
    double lon1 = *(double*) args->args[1];
    double lat2 = *(double*) args->args[2];
    double lon2 = *(double*) args->args[3];
    double dlon = (lon2 - lon1) * DEG_TO_RAD;
    double dlat = (lat2 - lat1) * DEG_TO_RAD;
    double a = pow(sin(dlat * 0.5),2) + 
        cos(lat1*DEG_TO_RAD) * cos(lat2*DEG_TO_RAD) * pow(sin(dlon * 0.5),2);
    double c = 2.0 * atan2(sqrt(a), sqrt(1-a));
    result = ( R * c );
    /*
     * If we have a 5th distance type argument...
     */
    if (args->arg_count == 5) {
        str_to_lowercase(args->args[4]);
        if (strcmp(args->args[4], "ft") == 0) result *= 3280.8399;
        if (strcmp(args->args[4], "mi") == 0) result *= 0.621371192;
    }

    return result;
}

回复于 2024-05-04T20:04:54+08:00

使用spherical projection可以实现快速，简单和准确（对于较小距离）的近似 . 至少在我的路由算法中，与正确的计算相比，我获得了20％的提升 . 在Java代码中，它看起来像：

public double approxDistKm(double fromLat, double fromLon, double toLat, double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
    double dLon = Math.toRadians(toLon - fromLon);
    double tmp = Math.cos(Math.toRadians((fromLat + toLat) / 2)) * dLon;
    double d = dLat * dLat + tmp * tmp;
    return R * Math.sqrt(d);
}

不确定MySQL（对不起！） .

确保你知道这个限制（assertEquals的第三个参数意味着以千米为单位的精度）：

float lat = 24.235f;
    float lon = 47.234f;
    CalcDistance dist = new CalcDistance();
    double res = 15.051;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);

    res = 150.748;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 1, lon + 1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 1, lon + 1), 1e-2);

    res = 1527.919;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 10, lon + 10), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 10, lon + 10), 10);

回复于 2024-05-04T20:04:54+08:00

9

以下是使用MySQL进行地理距离搜索的详细说明，该解决方案基于对mysql实施Haversine公式 . 完整的解决方案描述包括理论，实施和进一步的性能优化 . 虽然空间优化部分在我的情况下不正确 . http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

回复于 2024-05-04T20:04:54+08:00
3
阅读Geo Distance Search with MySQL，这是一个基于对Haversine Formula实现MySQL的解决方案 . 这是一个包含理论，实现和进一步性能优化的完整解决方案描述 . 虽然空间优化部分在我的情况下不能正常工作 .

我发现了两个错误：
- 在p8的select语句中使用 abs . 我刚刚省略 abs 并且它有效 .
- p27上的空间搜索距离函数不会被 cos(latitude) 转换为弧度或乘以经度，除非他的空间数据被考虑加载（无法从文章的上下文中得知），但他在p26上的示例表明他的空间数据 POINT 是没有加载弧度或度数 .
回复于 2024-05-04T20:04:54+08:00

一个MySQL函数，它返回两个坐标之间的米数：

CREATE FUNCTION DISTANCE_BETWEEN (lat1 DOUBLE, lon1 DOUBLE, lat2 DOUBLE, lon2 DOUBLE)
RETURNS DOUBLE DETERMINISTIC
RETURN ACOS( SIN(lat1*PI()/180)*SIN(lat2*PI()/180) + COS(lat1*PI()/180)*COS(lat2*PI()/180)*COS(lon2*PI()/180-lon1*PI()/180) ) * 6371000

要以不同的格式返回值，请将函数中的 6371000 替换为您选择的单位中的地球半径 . 例如，公里数为 6371 ，里程数为 3959 .

要使用该函数，只需像调用MySQL中的任何其他函数一样调用它 . 例如，如果您有一个表 city ，您可以找到每个城市与其他城市之间的距离：

SELECT
    `city1`.`name`,
    `city2`.`name`,
    ROUND(DISTANCE_BETWEEN(`city1`.`latitude`, `city1`.`longitude`, `city2`.`latitude`, `city2`.`longitude`)) AS `distance`
FROM
    `city` AS `city1`
JOIN
    `city` AS `city2`

回复于 2024-05-04T20:04:54+08:00

3
我需要解决类似的问题（通过距单点距离过滤行）并通过将原始问题与答案和注释相结合，我想出了解决方案，它在MySQL 5.6和5.7上都非常适合我 .
```
SELECT 
    *,
    (6371 * ACOS(COS(RADIANS(56.946285)) * COS(RADIANS(Y(coordinates))) 
    * COS(RADIANS(X(coordinates)) - RADIANS(24.105078)) + SIN(RADIANS(56.946285))
    * SIN(RADIANS(Y(coordinates))))) AS distance
FROM places
WHERE MBRContains
    (
    LineString
        (
        Point (
            24.105078 + 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 + 15 / 111.133
        ),
        Point (
            24.105078 - 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 - 15 / 111.133
        )
    ),
    coordinates
    )
HAVING distance < 15
ORDER By distance
```
coordinates 是类型为 POINT 且具有 SPATIAL 索引的字段
6371 用于计算以千米为单位的距离
56.946285 是中心点的纬度
24.105078 是中心点的经度
10 是以千米为单位的最大距离

在我的测试中，MySQL使用 coordinates 字段上的SPATIAL索引来快速选择矩形内的所有行，然后计算所有过滤位置的实际距离，以从矩形角中排除位置，并仅将位置留在圆内 .

这是我的结果的可视化：

灰色星形可视化 Map 上的所有点，黄色星形是MySQL查询返回的 . 矩形角（但外圆）内的灰色星由 MBRContains() 选择，然后由 HAVING 子句取消选择 .
回复于 2024-05-04T20:04:54+08:00

使用mysql

SET @orig_lon = 1.027125;
SET @dest_lon = 1.027125;

SET @orig_lat = 2.398441;
SET @dest_lat = 2.398441;

SET @kmormiles = 6371;-- for distance in miles set to : 3956

SELECT @kmormiles * ACOS(LEAST(COS(RADIANS(@orig_lat)) * 
 COS(RADIANS(@dest_lat)) * COS(RADIANS(@orig_lon - @dest_lon)) + 
 SIN(RADIANS(@orig_lat)) * SIN(RADIANS(@dest_lat)),1.0)) as distance;

见：https://andrew.hedges.name/experiments/haversine/

见：https://stackoverflow.com/a/24372831/5155484

见：http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

注意： LEAST 用于避免空值作为https://stackoverflow.com/a/24372831/5155484上建议的注释

回复于 2024-05-04T20:04:54+08:00

$objectQuery = "SELECT table_master.*, ((acos(sin((" . $latitude . "*pi()/180)) * sin((`latitude`*pi()/180))+cos((" . $latitude . "*pi()/180)) * cos((`latitude`*pi()/180)) * cos(((" . $longitude . "- `longtude`)* pi()/180))))*180/pi())*60*1.1515  as distance FROM `table_post_broadcasts` JOIN table_master ON table_post_broadcasts.master_id = table_master.id WHERE table_master.type_of_post ='type' HAVING distance <='" . $Radius . "' ORDER BY distance asc";

回复于 2024-05-04T20:04:54+08:00

找到两个纬度/长点之间距离的最快方法

16 回答

相关问题