如何有效地找到给定位置附近最近的位置 [英] How to efficiently find the closest locations nearby a given location
问题描述
我正在制作一个脚本，其中将大量业务加载到具有纬度和经度的 mySQL 数据库中.然后我为该脚本提供纬度和经度(最终用户的)，脚本必须计算从提供的纬度/经度到它从数据库中获取的每个条目的距离，并按照从最近到最远的顺序对它们进行排序.
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)来减少需要计算的计算次数，并将行限制为基于该条目的子集(WHERE latitude BETWEEN $minLat AND $maxLat AND longitude BETWEEN $minLong AND $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.
在 Movable 上有一个很好的解释(使用 PHP 代码)键入网站，对于任何计划使用 PHP 进行任何地理定位工作的人来说，这应该是必不可少的阅读材料.
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屋！
