如何有效地找到给定位置附近的最近位置 [英] How to efficiently find the closest locations nearby a given location
问题描述
我正在编写一个脚本，其中将业务量以纬度和经度加载到mySQL数据库中.然后，我向该脚本提供(最终用户的)经度纬度，并且该脚本必须计算从数据库提供的条目中所提供的经度/经度到每个EACH的距离，并按从最远到最远的顺序对其进行排序.
I'm making a script where a load of business are loaded into a mySQL database with a latitude and longitude. Then I am supplying that script with a latitude an longitude (of the end user) and the script has to calculate the distance from the supplied lat/long to EACH of the entries it gets from the database and order them in order of nearest to furthest.
实际上，我实际上只需要大约10或20个最近"的结果，但是除了从数据库中获取所有结果并对每个结果运行函数然后进行数组排序外，我什么也想不做.
I only realistically need about 10 or 20 "nearest" results, but I can't think of anyway to do this other than to get all the results from the database and run the function on each of them and then array sort.
这是我已经拥有的:
<?php
function getDistance($point1, $point2){
$radius = 3958; // Earth's radius (miles)
$pi = 3.1415926;
$deg_per_rad = 57.29578; // Number of degrees/radian (for conversion)
$distance = ($radius * $pi * sqrt(
($point1['lat'] - $point2['lat'])
* ($point1['lat'] - $point2['lat'])
+ cos($point1['lat'] / $deg_per_rad) // Convert these to
* cos($point2['lat'] / $deg_per_rad) // radians for cos()
* ($point1['long'] - $point2['long'])
* ($point1['long'] - $point2['long'])
) / 180);
$distance = round($distance,1);
return $distance; // Returned using the units used for $radius.
}
include("../includes/application_top.php");
$lat = (is_numeric($_GET['lat'])) ? $_GET['lat'] : 0;
$long = (is_numeric($_GET['long'])) ? $_GET['long'] : 0;
$startPoint = array("lat"=>$lat,"long"=>$long);
$sql = "SELECT * FROM mellow_listings WHERE active=1";
$result = mysql_query($sql);
while($row = mysql_fetch_array($result)){
$thedistance = getDistance($startPoint,array("lat"=>$row['lat'],"long"=>$row['long']));
$data[] = array('id' => $row['id'],
'name' => $row['name'],
'description' => $row['description'],
'lat' => $row['lat'],
'long' => $row['long'],
'address1' => $row['address1'],
'address2' => $row['address2'],
'county' => $row['county'],
'postcode' => strtoupper($row['postcode']),
'phone' => $row['phone'],
'email' => $row['email'],
'web' => $row['web'],
'distance' => $thedistance);
}
// integrate google local search
$url = "http://ajax.googleapis.com/ajax/services/search/local?";
$url .= "q=Off+licence"; // query
$url .= "&v=1.0"; // version number
$url .= "&rsz=8"; // number of results
$url .= "&key=ABQIAAAAtG"
."Pcon1WB3b0oiqER"
."FZ-TRQgsWYVg721Z"
."IDPMPlc4-CwM9Xt"
."FBSTZxHDVqCffQ2"
."W6Lr4bm1_zXeYoQ"; // api key
$url .= "&sll=".$lat.",".$long;
// sendRequest
// note how referer is set manually
$ch = curl_init();
curl_setopt($ch, CURLOPT_URL, $url);
curl_setopt($ch, CURLOPT_RETURNTRANSFER, 1);
curl_setopt($ch, CURLOPT_REFERER, /* url */);
$body = curl_exec($ch);
curl_close($ch);
// now, process the JSON string
$json = json_decode($body, true);
foreach($json['responseData']['results'] as $array){
$thedistance = getDistance($startPoint,array("lat"=>$array['lat'],"long"=>$array['lng']));
$data[] = array('id' => '999',
'name' => $array['title'],
'description' => '',
'lat' => $array['lat'],
'long' => $array['lng'],
'address1' => $array['streetAddress'],
'address2' => $array['city'],
'county' => $array['region'],
'postcode' => '',
'phone' => $array['phoneNumbers'][0],
'email' => '',
'web' => $array['url'],
'distance' => $thedistance);
}
// sort the array
foreach ($data as $key => $row) {
$id[$key] = $row['id'];
$distance[$key] = $row['distance'];
}
array_multisort($distance, SORT_ASC, $data);
header("Content-type: text/xml");
echo '<?xml version="1.0" encoding="UTF-8"?>'."\n";
echo '<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">'."\n";
echo '<plist version="1.0">'."\n";
echo '<array>'."\n";
for($i = 0; isset($distance[$i]); $i++){
//echo $data[$i]['id']." -> ".$distance[$i]."<br />";
echo '<dict>'."\n";
foreach($data[$i] as $key => $val){
echo '<key><![CDATA['.$key.']]></key>'."\n";
echo '<string><![CDATA['.htmlspecialchars_decode($val, ENT_QUOTES).']]></string>'."\n";
}
echo '</dict>'."\n";
}
echo '</array>'."\n";
echo '</plist>'."\n";
?>
现在，它在数据库中只有2或3个业务的情况下运行得足够快，但是我目前正在将5k个业务加载到数据库中，并且我担心对于每次输入来说，运行此业务的速度会非常慢吗?你觉得呢?
Now, this runs fast enough with only 2 or 3 businesses in the database, but I'm currently loading 5k businesses into the database and I'm worried that its going to be incredibly slow running this for EACH entry? What do you think?
这也不是我可以缓存的数据，因为两个用户具有相同的经/纬度的可能性极少发生，因此无济于事.
Its not the kind of data I could cache either, as the likelihood of two users having the same lat/long is liable to be incredibly rare, and therefore wouldn't help.
对此我该怎么办?
感谢您的帮助和建议.他们都很感谢.
Thanks for any help and any suggestions. They're all much appreciated.
推荐答案
选项1: 切换到支持GeoIP的数据库，对数据库进行计算.
Option 1: Do the calculation on the database by switching to a database that supports GeoIP.
选项2: 在数据库上进行计算:您正在使用MySQL，因此以下存储过程应该有所帮助
Option 2: Do the calculation on the database: you're using MySQL, so the following stored procedure should help
CREATE FUNCTION distance (latA double, lonA double, latB double, LonB double)
RETURNS double DETERMINISTIC
BEGIN
SET @RlatA = radians(latA);
SET @RlonA = radians(lonA);
SET @RlatB = radians(latB);
SET @RlonB = radians(LonB);
SET @deltaLat = @RlatA - @RlatB;
SET @deltaLon = @RlonA - @RlonB;
SET @d = SIN(@deltaLat/2) * SIN(@deltaLat/2) +
COS(@RlatA) * COS(@RlatB) * SIN(@deltaLon/2)*SIN(@deltaLon/2);
RETURN 2 * ASIN(SQRT(@d)) * 6371.01;
END//
编辑
如果数据库中有一个关于纬度和经度的索引，则可以通过计算PHP的初始边界框($ minLat，$ maxLat，$ minLong和$ maxLong)来减少需要计算的数量，并根据该行将行限制为条目的子集($ minLat和$ maxLat之间的纬度以及$ minLong和$ maxLong之间的经度).然后，MySQL只需要为该行子集执行距离计算.
If you have an index on latitude and longitude in your database, you can reduce the number of calculations that need to be calculated by working out an initial bounding box in PHP ($minLat, $maxLat, $minLong and $maxLong), and limiting the rows to a subset of your entries based on that (WHERE latitude BETWEEN $minLat AND $maxLat AND longitude BETWEEN $minLong AND $maxLong). Then MySQL only needs to execute the distance calculation for that subset of rows.
进一步编辑(作为上一次编辑的说明)
FURTHER EDIT (as an explanation for the previous edit)
如果仅使用Jonathon提供的SQL语句(或存储过程来计算距离)，则SQL仍必须查看数据库中的每个记录，并在计算数据库中每个记录的距离之前它可以决定是返回还是丢弃该行.
If you're simply using the SQL statement provided by Jonathon (or a stored procedure to calculate the distance) then SQL still has to look through every record in your database, and to calculate the distance for every record in your database before it can decide whether to return that row or discard it.
由于计算的执行速度相对较慢，因此最好减少需要计算的行的集合，从而消除明显落在所需距离之外的行，以便我们仅执行较少的行数需要昂贵的计算.
Because the calculation is relatively slow to execute, it would be better if you could reduce the set of rows that need to be calculated, eliminating rows that will clearly fall outside of the required distance, so that we're only executing the expensive calculation for a smaller number of rows.
如果您认为自己的工作基本上是在地图上画一个以初始点为中心并具有一定距离半径的圆；那么公式可以简单地识别出哪些行属于该圆...但是它仍然必须检查每一行.
If you consider that what you're doing is basically drawing a circle on a map, centred on your initial point, and with a radius of distance; then the formula simply identifies which rows fall within that circle... but it still has to checking every single row.
使用包围盒就像先在地图上绘制一个正方形，然后将左，右，上和下边缘与我们的中心点保持适当的距离.然后，将在该框中绘制我们的圆，使圆上的最北，最东，最南和最西点与框的边界接触.一些行将落在该框的外面，因此SQL甚至不必费心尝试计算这些行的距离.它仅计算落入边界框内的行的距离，以查看它们是否也落入圆内.
Using a bounding box is like drawing a square on the map first with the left, right, top and bottom edges at the appropriate distance from our centre point. Our circle will then be drawn within that box, with the Northmost, Eastmost, Southmost and Westmost points on the circle touching the borders of the box. Some rows will fall outside that box, so SQL doesn't even bother trying to calculate the distance for those rows. It only calculates the distance for those rows that fall within the bounding box to see if they fall within the circle as well.
在PHP中，我们可以使用一个非常简单的计算方法，根据我们的距离计算出最小和最大纬度和经度，然后在SQL语句的WHERE子句中设置这些值.这实际上是我们的盒子，落在盒子外面的任何东西都会被自动丢弃，而无需实际计算其距离.
Within PHP, we can use a very simple calculation that works out the minimum and maximum latitude and longitude based on our distance, then set those values in the WHERE clause of your SQL statement. This is effectively our box, and anything that falls outside of that is automatically discarded without any need to actually calculate its distance.
可移动键入网站，这对于打算用PHP进行任何GeoPositioning工作的任何人来说都是必不可少的阅读内容.
There's a good explanation of this (with PHP code) on the Movable Type website that should be essential reading for anybody planning to do any GeoPositioning work in PHP.
这篇关于如何有效地找到给定位置附近的最近位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
