找到两个Lat/Long点之间距离的最快方法

我目前在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。如果你需要千米，使用6371代替3959。

218625 次浏览
小开
最佳答案

  • 使用MyISAM表中Geometry数据类型的Point值创建你的点。从Mysql 5.7.5开始，__ABC3表现在也支持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)内的所有点。

这实际上不是一个盒子，而是一个球面矩形:纬度和经度绑定的球面段。这可能与弗朗茨·约瑟夫·兰德上的普通矩形不同，但在大多数有人居住的地方非常接近。

  • 应用额外的过滤来选择圆内的所有内容(不是正方形)

  • 可能会应用额外的精细过滤来考虑大圆圈距离(对于大距离)

小开

不是MySql特有的答案，但它会提高sql语句的性能。

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

在你运行这个sql之前，你可以做的是创建四个点，在一边画一个20个单位的盒子，与你的点在中心，即。(x1,y1)。(x4, y4)，其中(x1,y1)为(给定long + 10个单位，给定lat + 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的点)，因此您仍然需要计算每个点的距离。然而，这同样会快得多，因为您已经极大地限制了测试框内的点的数量。

我把这个技巧叫做“在盒子里思考”:)

编辑:这可以放入一个SQL语句吗?

我不知道mySql或Php能做什么，抱歉。 我不知道构建这四个点的最佳位置，也不知道如何将它们传递给Php中的mySql查询。然而，一旦你掌握了这四点，就没有什么能阻止你把你自己的SQL语句和我的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的特定部分，请随意编辑这个答案。

小开

下面的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;
小开

一个快速，简单和准确的(对于较小的距离)近似可以用球面投影完成。至少在我的路由算法中，与正确的计算相比，我得到了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);
小开 
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

小开
这是一个非常详细的描述与MySQL地理距离搜索的解决方案，基于实现的Haversine公式到MySQL。完整的解决方案描述，包括理论、实现和进一步的性能优化。尽管空间优化部分在我的案例中没有正确工作。 http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL < / p >
小开 
   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;
小开

关于如何安装为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;
}
小开 
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中点与点之间的距离计算查询，我已经在一个长数据库中使用过它，它工作完美!注意:根据您的需求进行更改(数据库名称，表名称，列等)。

小开 
$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";
小开

读取地理距离搜索MySQL，解 基于Haversine公式对MySQL的实现。这是一个完整的解决方案 描述与理论，实现和进一步的性能优化。 尽管空间优化部分在我的案例中没有正常工作。< / p >

我发现其中有两个错误:

  1. 在p8的select语句中使用abs。我只是省略了abs，它工作。

  2. p27上的空间搜索距离函数不会转换为弧度或将经度乘以cos(latitude)，除非他的空间数据是考虑到这一点而加载的(不能从文章的上下文中判断)，但他在p26上的例子表明他的空间数据POINT没有加载弧度或度。

小开

一个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替换为您选择的单位中的地球半径。例如，km将是6371, miles将是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`
小开

如果你使用的是MySQL 5.7。*，然后你可以使用st_distance_sphere(点,点)。

Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance
小开

我需要解决类似的问题(从单点的距离过滤行)，并通过结合原始问题的答案和评论，我想出了解决方案，这对我来说完美的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字段快速选择矩形内的所有行，然后计算所有过滤的地方的实际距离，以排除矩形角落的地方，只留下圆内的地方。

这是我的结果的可视化:

map

灰色星形表示地图上的所有点，黄色星形表示MySQL查询返回的点。矩形内角(但圆形外)的灰色星星由MBRContains()选择，然后由HAVING子句取消选择。

小开

使用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用于避免null值作为https://stackoverflow.com/a/24372831/5155484上建议的注释

小开

我真的很喜欢@Māris kiseovs的解决方案，但我喜欢许多其他人可能有Lat和lng的POINTS从他的例子中反转。在概括它时，我想我会分享它。在我的情况下，我需要找到在end_point的一定半径内的所有start_points。

我希望这能帮助到一些人。

SELECT @LAT := ST_X(end_point), @LNG := ST_Y(end_point) FROM routes  WHERE route_ID = 280;
SELECT
*,
(6371e3 * ACOS(COS(RADIANS(@LAT)) * COS(RADIANS(ST_X(start_point)))
* COS(RADIANS(ST_Y(start_point)) - RADIANS(@LNG)) + SIN(RADIANS(@LAT))
* SIN(RADIANS(ST_X(start_point))))) AS distance
FROM routes
WHERE MBRContains
(
LineString
(
Point (
@LNG + 15 / (111.320 * COS(RADIANS(@LAT))),
@LAT + 15 / 111.133
),
Point (
@LNG - 15 / (111.320 * COS(RADIANS(@LAT))),
@LAT - 15 / 111.133
)
),
POINT(ST_Y(end_point),ST_X(end_point))
)
HAVING distance < 100
ORDER By distance;

提交答案