如何有效地找到给定位置附近的最近位置

Question

我正在制作一个脚本,其中一堆业务被加载到具有纬度和经度的mySQL数据库中.然后我提供该脚本的纬度和经度(最终用户),并且脚本必须计算从提供的lat/long到从数据库获得的每个条目的距离,并按最接近最远的顺序排序.

我实际上只需要大约10或20个"最近"的结果,但除了从数据库中获取所有结果并在每个结果上运行函数然后进行数组排序之外,我无法想到这样做.

这就是我已经拥有的:

<?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企业加载到数据库中,我担心它会在每次进入时运行速度极慢吗？你怎么看？

它不是我可以缓存的那种数据,因为两个用户具有相同纬度/经度的可能性非常罕见,因此无济于事.

我该怎么办？

感谢您的任何帮助和任何建议.他们都非常感激.

Answer 1

我认为你可以使用SQL中的Haversine公式更好地完成你想要实现的目标.Google有一个关于如何在MySQL数据库中获取最近位置的教程,但一般的想法是这个SQL:

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) )
  * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) 
  * sin( radians( lat ) ) ) ) AS distance
FROM markers
HAVING distance < 25
ORDER BY distance LIMIT 0 , 20;

然后,您需要完成的所有工作都是在数据库上完成的,因此您甚至无需在检查距离之前将所有业务拉入PHP脚本.

Answer 2

选项1:通过切换到支持GeoIP的数据库对数据库进行计算.

选项2:对数据库进行计算:您正在使用MySQL,因此以下存储过程应该有所帮助

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纬度BETWEEN $ minLat和$ maxLat以及经度BETWEEN $ minLong和$ maxLong).然后,MySQL只需要为该行子集执行距离计算.

进一步编辑(作为前一编辑的解释)

如果您只是使用Jonathon提供的SQL语句(或存储过程来计算距离),那么SQL仍然必须查看数据库中的每条记录,并在数据库决定之前计算数据库中每条记录的距离是否返回该行或丢弃它.

因为计算执行起来相对较慢,所以如果你可以减少需要计算的行集会更好,消除明显超出所需距离的行,这样我们只执行昂贵的计算行数较少.

如果你认为你正在做的事情基本上是在地图上绘制一个圆圈,以你的初始点为中心,并且距离的半径; 那么公式只是简单地确定哪些行落在那个圆圈内......但它仍然必须检查每一行.

使用边界框就像在地图上首先绘制一个正方形,左边,右边,顶边和底边与我们的中心点保持适当的距离.然后我们的圆圈将被绘制在该框内,圆圈上的最北端,最东端,最南端和最西端的点接触到框的边界.有些行会落在该框之外,因此SQL甚至不愿意尝试计算这些行的距离.它仅计算落在边界框内的那些行的距离,以查看它们是否也在圆圈内.

在PHP中,我们可以使用一个非常简单的计算,根据距离计算最小和最大纬度和经度,然后在SQL语句的WHERE子句中设置这些值.这实际上就是我们的盒子,任何不属于它的东西都会被自动丢弃,而不需要实际计算它的距离.

在Movable Type网站上有一个很好的解释(使用PHP代码),对于计划在PHP中进行任何GeoPositioning工作的人来说,这应该是必不可少的阅读.