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

Question

我正在编写一个脚本，其中将业务量以纬度和经度加载到mySQL数据库中。然后，我向该脚本提供一个（最终用户的）经度纬度，并且该脚本必须计算从提供的经度/经度到它从数据库中获得的条目的EACH的距离，并按从最远到最远的顺序对其进行排序。

实际上，我实际上只需要大约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

选项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）并限制来减少需要计算的数量。根据该行（$ minLat和$ maxLat之间的纬度以及$ minLong和$
maxLong之间的经度）将这些行添加到您的条目子集。然后，MySQL只需要为该行子集执行距离计算。

进一步编辑 （作为先前编辑的解释）

如果仅使用Jonathon提供的SQL语句（或存储过程来计算距离），则SQL仍必须仔细检查数据库中的每个记录，并计算数据库中每个记录的距离，然后才能决定是返回还是丢弃该行。

由于计算的执行速度相对较慢，因此最好减少需要计算的行的集合，从而消除明显落在所需距离之外的行，因此我们仅对以下情况执行昂贵的计算：行数较少。

如果您认为自己所做的基本上是在地图上绘制一个以初始点为中心并具有一定距离半径的圆；那么该公式仅会确定哪些行属于该圆…但是它仍然必须检查每一行。

使用边界框就像先在地图上绘制一个正方形，然后将左，右，上和下边缘与我们的中心点保持适当的距离。然后，我们将在该框中绘制圆，使圆上的最北，最东，最南和最西点与框的边界接触。一些行将落在该框的外面，因此SQL甚至不必费心尝试计算这些行的距离。它仅计算落入边界框内的行的距离，以查看它们是否也落入圆内。

在PHP中，我们可以使用非常简单的计算方法，根据我们的距离计算出最小和最大纬度和经度，然后在SQL语句的WHERE子句中设置这些值。这实际上是我们的盒子，落在盒子外面的任何东西都会自动丢弃，而无需实际计算其距离。

在Movable Type网站上对此有很好的解释（带有PHP代码），对于打算用PHP进行任何GeoPositioning工作的任何人来说，这都是必不可少的阅读材料。