寻找两个经纬度点之间距离的最快方法

Question

我目前在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;

注意：提供的距离单位为英里。如果您需要公里，请使用6371而不是3959。

- Ryan Detzel

---

您给出的公式似乎有很多是常量。是否可以预先计算数据并将这些值存储在您的数据库中？例如，3959 * acos(cos(radians(42.290763)))是一个常量，但其中有4个主要计算。相反，您可以只存储6696.7837吗？ - Peter M

@Peter M 看起来任何像样的 SQL 数据库都会进行优化，以便只计算一次。 - mhenry1384

对于那些想知道的人，42.290763是要计算距离的点的纬度，而-71.35368是经度。 - user276648

另一种方法是使用UDF，几年前我遇到了同样的问题，并编写了这个lib_mysqludf_haversine...也许对其他人有用。 - Luca Sepe

请注意，使用此公式计算的距离单位为英里，而非公里。请将 3959 替换为 6371，以便以公里为单位计算结果。 - Sahil

Answer 1

• 使用 MyISAM 表中 Geometry 数据类型的 Point 值来创建你的点。自 Mysql 5.7.5 起，InnoDB 表现在也支持 SPATIAL 索引。

• 在这些点上创建一个 SPATIAL 索引

• 使用 MBRContains() 来查找这些值:

  SELECT  *
  FROM    table
  WHERE   MBRContains(LineFromText(CONCAT(
          '('
          , @lon + 10 / ( 111.1 / cos(RADIANS(@lat)))
          , ' '
          , @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)。

实际上，这不是一个矩形，而是一个球体矩形：经度和纬度边界段。这可能与弗朗茨·约瑟夫地上的普通矩形不同，但在大多数有人居住的地方相当接近。

• 应用额外的过滤器以选择圆形内的所有内容（而不是方形）

• 可能需要应用额外的细微过滤以考虑大圆距离（对于大距离）

- Quassnoi

---

一些更正：你可能需要交换坐标顺序为纬度、经度。此外，经度距离与 纬度 的余弦成正比，而不是经度。 你需要将乘法改为除法，所以你的第一个坐标将被更正为 @lon - 10 / ( 111.1 / cos(@lat))（一旦一切正确后，它将成为一对中的第二个坐标）。 - M. Dave Auayan

警告：答案的内容未经过与M. Dave Auayan所做的非常有效的评论相符的编辑。此外，需要注意的是，如果感兴趣的圆（a）包含一个极点或（b）被经度+/-180度子午线穿过，则该方法将失败。而且使用cos(lon)只对较小距离准确。参见http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates。 - John Machin

我们能否了解一下这些常数（10，111.11，@lat，@lon，mypoint）代表什么？我猜想10代表公里距离，@lat和@lon代表给定的纬度和经度，但是在这个例子中111.11和mypoint代表什么呢？ - ashays

@ashays说，每一纬度大约相当于111.(1)公里。"mypoint"是存储坐标的表中的字段。 - Quassnoi

@R_User：即使在5.7版本中，InnoDB仍不支持空间索引http://dev.mysql.com/doc/refman/5.7/en/optimizing-spatial-analysis.html MyISAM支持SPATIAL和非SPATIAL两种类型的索引。其他存储引擎支持非SPATIAL索引，如第13.1.11节“CREATE INDEX Syntax”所述。您可以在InnoDB中创建一个空间类型，但您无法对其进行索引。 - Quassnoi

Answer 2

这不是特定于MySql的答案，但它将改善您的SQL语句的性能。

实际上，您正在计算到表中每个点的距离，以查看它是否在给定点的10个单位范围内。

在运行此SQL之前，您可以创建四个点，绘制一个边长为20个单位的正方形，使您的点位于中心位置，即 (x1,y1) ... (x4, y4)，其中(x1,y1)为(givenlong + 10 units, givenLat + 10units)...(givenLong - 10units, givenLat -10 units)。实际上，您只需要两个点，左上角和右下角称为(X1，Y1)和(X2，Y2）

现在，您的SQL语句可以使用这些点来排除与给定点距离肯定超过10个单位的行，它可以使用纬度和经度上的索引，因此比当前的查询速度快得多。

例如：

select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;

盒子方法可能会出现误报（您可以在距离给定点大于10u的盒子角落捕捉到点），因此仍然需要计算每个点的距离。但是，由于您已经大大限制了要测试的点的数量为盒子内的点，因此这将会更快。

我称这种技术为“盒中思考” :)

编辑：这可以放入一个SQL语句吗？

我不知道mySql或Php能够做什么，很抱歉。 我不知道构建四个点的最佳位置在哪里，或者它们如何通过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中，我可以构建一个SQL语句来声明四个浮点数（X1，Y1，X2，Y2），并在“主”选择语句之前计算它们。就像我说的，我不知道这是否可以在MySQL中实现。不过，我还是倾向于在C#中构建这四个点，并将它们作为参数传递给SQL查询。

很抱歉我不能提供更多帮助，如果有人能回答MySQL和PHP特定部分，请随意编辑此答案以提供帮助。

- Binary Worrier

---

您可以在此演示文稿中找到使用MySQL进行此方法的存储过程：http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL - Lucia

使用公里而不是英里进行搜索，请将3959替换为6371。 - ErichBSchulz

+1，很棒的选择；添加这个框将我的查询时间从平均4秒减少到0.03秒。 - Jerod Venema

尽管看起来很合理，但您为此解决方案获得了奖励！在200万条记录的数据库上，查询时间从16秒降至0.06秒。注意： 如果将距离计算从查询中剔除，并在程序代码中进行距离计算，则对于大型表格而言，速度会更快！ - NLAnaconda

@Binary Worrier：根据这里给出的示例：http://blog.fedecarg.com/2009/02/08/geo-proximity-search-the-haversine-equation/，X1、X2、Y1和Y2将分别是经度最小值、经度最大值、纬度最小值和纬度最大值，请指教。 - Prabhat

Answer 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是中心点的经度。
15是最大距离（以公里为单位）。

在我的测试中，MySQL使用coordinates字段上的SPATIAL索引快速选择所有在矩形内的行，并针对所有筛选出来的地点计算实际距离，以排除矩形角落外的地点，只留下圆形内部的地点。

以下是我的结果可视化：

灰色星标显示地图上的所有点，黄色星标是MySQL查询返回的点。在矩形角落内的灰色星标（但在圆形外部）由MBRContains()选中，然后由HAVING子句取消选中。

- Māris Kiseļovs

---

无法点赞此问题足够多。使用此方法搜索具有约500万条记录和空间索引的表时，搜索时间在旧的A8处理器上为0.005秒。我知道可以用3959替换6371以获得英里的结果，但是111.133和111.320的值需要进行调整还是普遍恒定的呢？ - Wranorn

很棒的解决方案。 - SeaBiscuit

如何创建一个点，是POINT(lat, lng)还是POINT(lng, lat)？ - user606669

@user606669 这是一个点（经度，纬度）。 - Māris Kiseļovs

111.133和111.320可以用69.06和69.17英里来替换。 - Daniel

Answer 4

以下MySQL函数是发布在这篇博客文章上的。我没有进行过太多测试，但根据文章中的信息，如果你的纬度和经度字段被索引，那么这可能对你很有效：

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 ;

使用示例：

假设有一张名为places的表，其中包含字段latitude和longitude：

SELECT get_distance_in_miles_between_geo_locations(-34.017330, 22.809500,
latitude, longitude) AS distance_from_input FROM places;

- Brad Parks

---

我已经尝试过这个方法，它完美地工作了，但不知为什么它不允许我根据 distance_from_input 来放置 WHERE 语句。有什么想法吗？ - Chris Visser

你可以将其作为子查询来执行：select * from (...) as t where distance_from_input > 5; - Brad Parks

选择*从地方，其中get_distance_in_miles_between_geo_locations（-34.017330，22.809500，纬度，经度）> 5000; - Brad Parks

返回米数： SELECT ROUND(((ACOS(SIN(lat1 * PI() / 180) * SIN(lat2 * PI() / 180) + COS(lat1 * PI() / 180) * COS(lat2 * PI() / 180) * COS((lnt1 - lnt2) * PI() / 180)) * 180 / PI()) * 60 * 1.1515) * 1.609344 * 1000) AS distance - Mohammad

Answer 5

如果你正在使用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

- alriyami

---

这是一个非常好的且易于阅读的替代方案。请记住，POINT()函数的参数顺序是(lng,lat)，否则你可能会得到与其他方法“接近”但仍然非常不同的结果。参见：https://dev59.com/D5Tfa4cB1Zd3GeqPYPl8 - Andy P

Answer 6

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中两个点之间距离计算的查询语句，我在一个大型数据库中使用它，它运行得非常完美！注意：根据您的需求更改（数据库名称、表名、列等）。

- Sanni Poriya

---

值1.1515代表什么？我之前看过类似的公式，但是它使用了1.75而不是1.1515。 - TryHarder

回答自己的问题，我认为答案可能在这里：https://dev59.com/j3RC5IYBdhLWcg3wK9yV#389251。 - TryHarder

Answer 7

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

- Abhigyan

---

请列出你的参考资料。这篇文章来自于：http://blog.fedecarg.com/2009/02/08/geo-proximity-search-the-haversine-equation/ - redburn

这种情况下的69是什么？如果我们有地球半径的话，该如何处理？ - CodeRunner

1纬度的距离为111公里。 1纬度的距离为69英里。 而69英里等于111公里。因此我们在转换中使用了这些参数。 - CodeRunner

我一直在寻找这个，没想到它可以这么简单。非常感谢。 - Vikas

这样做是否不正确？因为lng_min / lng_max需要在半径计算中使用lat_min和lat_max。 - Ben

Answer 8

   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;

- user3113927

Answer 9

一个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`

- Robert

Answer 10

完整的代码及如何安装为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;
}

- Luca Sepe