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

我目前在mysql数据库中只有一百万个位置,都有经度和纬度信息。

我试图通过查询find一个点和许多其他点之间的距离。 它不像我想要的那样快,特别是每秒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

  • 使用MyISAM表中的Geometry数据types的Point值创build你的点。 从Mysql 5.7.5开始, InnoDB也支持SPATIAL索引。

  • 在这些点上创build一个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 ) 

这将select框内的所有点(@lat +/- 10 km, @lon +/- 10km)

这实际上不是一个盒子,而是一个球形矩形:球体的经度和纬度边界部分。 这可能与Franz Joseph Land上的一个简单的矩形不同,但在大多数有人居住的地方非常接近。

  • 应用额外的过滤来select圈内的所有内容(而不是正方形)

  • 可能应用额外的精细过滤来解释大圆距(大距离)

不是MySql特定的答案,但它会提高你的SQL语句的性能。

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

在你运行这个sql之前你可以做的是创build四个点,在一边绘制一个20个单位的盒子,你的点在中心即。 (x1,y1)。 。 。 (x4,y4),其中(x1,y1)是(给定+10个单位,给定La + 10个单位)。 。 。 (给予长-10单位,给予-10单位)。 其实你只需要两个点,左上angular和右下angular分别叫(X1,Y1)和(X2,Y2)

现在,您的SQL语句使用这些点来排除绝对超过10u的行,它可以使用纬度和经度上的索引,因此比现在快得多。

例如

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

盒子的方法可以返回误报(你可以从盒子的angular落拿到距离给定点大于10u的点),所以你仍然需要计算每个点的距离。 然而,这又会更快,因为你已经大大限制了点的数量来testing框内的点。

我把这个技巧称为“盒子里面的思考”:)

编辑:这可以放在一个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我可以build立一个声明四个浮点数(X1,Y1,X2,Y2)的SQL语句,并在“主”select语句之前计算它们,就像我说的,我不知道这是否可以用MySQL的。 不过,我仍然倾向于在C#中构build四个点,并将它们作为parameter passing给SQL查询。

对不起,我不能有更多的帮助,如果任何人都可以回答MySQL和Php的特定部分,请随时编辑这个答案。

检查这个演示文稿是一个好的答案。 基本上,它显示了评论中显示的两种不同的方法,并详细解释了为什么/何时应该使用这两种方法,以及为什么“框内”计算可能非常有趣。

使用MySQL的地理距离search

在此博客文章中 , 发布了以下MySql函数。 我没有做太多的testing,但从我的post中可以看出 , 如果你的经纬度字段被编入索引 ,这可能对你有好处:

 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的经纬度表:

select距离地点distance_from_input的get_distance_in_miles_between_geo_locations(-34.017330,22.809500,纬度,经度)

都从这个post挂起

 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之间的距离计算查询点,我用它在一个很长的数据库,它工作完美! 注意:按照您的要求进行更改(数据库名称,表名,列等)。

 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); 

资源

有关如何安装为MySQL插件的完整代码在这里: https : //github.com/lucasepe/lib_mysqludf_haversine

我去年发表了这个评论。 由于亲切的@TylerCollierbuild议我作为答复发布,在这里。

另一种方法是编写一个自定义的UDF函数,该函数返回两个点之间的半正定距离。 这个function可以input:

 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公里的所有logging。 要么:

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

取距离小于25英尺的所有logging。

核心function是:

 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; } 

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

这里是一个非常详细的描述,用MySQL的地理距离search一个基于实现Haversine公式到MySQL的解决scheme。 完整的解决scheme描述与理论,实施和进一步的性能优化。 虽然空间优化部分在我的情况下不正确。 http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

  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的Geo距离search ,这是一个基于实现Haversine公式到MySQL的解决scheme。 这是一个完整的解决scheme描述与理论,实施和进一步的性能优化。 虽然空间优化部分在我的情况下不能正确工作。

我注意到这两个错误:

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

  2. 在p27上的空间search距离函数不会转换为弧度或乘以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 

要以不同格式返回值,请将函数中的6371000replace为6371000中的地球半径。 例如,公里将是6367英里将是3957

要使用这个函数,就像调用MySQL中的其他函数一样调用它。 例如,如果你有一个餐桌city ,你可以find每个城市到其他城市的距离:

 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(POINT,POINT)

 Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000 as distcance 
 $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";