Как эффективно найти ближайшие места поблизости от данного места - PullRequest
22 голосов
/ 13 октября 2010

Я делаю сценарий, в котором нагрузка на бизнес загружается в базу данных 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 предприятия в базе данных, но в настоящее время я загружаю в базу данных 5 000 предприятий, и я боюсь, что это будет невероятно медленно, запускать это для КАЖДОГО входа? Что ты думаешь?

Это не тот тип данных, который я мог бы кэшировать, так как вероятность того, что два пользователя будут иметь одинаковый lat / long, может быть невероятно редкой и поэтому не поможет.

Что я могу с этим поделать?

Спасибо за любую помощь и любые предложения. Они все очень ценятся.

Ответы [ 4 ]

22 голосов
/ 13 октября 2010

Я думаю, что вы пытаетесь достичь, можно было бы сделать лучше, используя формула Haversine в вашем SQL. У 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-скрипт, прежде чем вы даже проверите расстояние.

19 голосов
/ 13 октября 2010

Вариант 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//

EDIT

Если в вашей базе данных есть индекс широты и долготы, вы можете уменьшить количество вычислений, которые необходимо рассчитать, разработав начальный ограничивающий прямоугольник в PHP ($ minLat, $ maxLat, $ minLong и $ maxLong) и ограничение строк подмножеством ваших записей на основе этого (ГДЕ широта между $ minLat и $ maxLat И долгота между $ minLong И $ maxLong). Тогда MySQL нужно только выполнить расчет расстояния для этого подмножества строк.

ДОПОЛНИТЕЛЬНОЕ РЕДАКТИРОВАНИЕ (как пояснение к предыдущему редактированию)

Если вы просто используете оператор SQL, предоставленный Джонатоном (или хранимую процедуру для вычисления расстояния), тогда SQL все равно должен просмотреть каждую запись в вашей базе данных и рассчитать расстояние для каждой записи в вашей базе данных до того, как он может решить, возвращать ли эту строку или отбрасывать ее.

Поскольку вычисления выполняются относительно медленно, было бы лучше, если бы вы могли уменьшить набор строк, которые необходимо вычислить, исключив строки, которые явно выйдут за пределы требуемого расстояния, так что мы выполняем только дорогой расчет для меньшего количества рядов.

Если вы считаете, что в основном вы рисуете круг на карте с центром в начальной точке и с радиусом расстояния; тогда формула просто определяет, какие строки попадают в этот круг ... но все равно приходится проверять каждую строку.

Использование ограничивающей рамки похоже на то, чтобы сначала нарисовать квадрат на карте с левым, правым, верхним и нижним краями на соответствующем расстоянии от нашей центральной точки. Затем наш круг будет нарисован внутри этого прямоугольника, а самые северные, самые восточные, самые южные и самые западные точки на круге касаются границ прямоугольника. Некоторые строки будут выходить за рамки этого поля, поэтому SQL даже не пытается вычислить расстояние для этих строк. Он рассчитывает расстояние только для тех строк, которые попадают в ограничивающую рамку, чтобы увидеть, попадают ли они и в круг.

В PHP мы можем использовать очень простой расчет, который определяет минимальную и максимальную широту и долготу на основе нашего расстояния, а затем установить эти значения в предложении WHERE вашего оператора SQL. Это фактически наша коробка, и все, что выпадает за пределы этого, автоматически отбрасывается без необходимости фактически вычислять его расстояние.

На веб-сайте Movable Type есть хорошее объяснение этого (с кодом PHP), которое должно быть важным чтением для любого, кто планирует выполнять какую-либо работу с геопозицией в PHP.

1 голос
/ 13 октября 2010

Если у вас много точек, запросы с формулами расстояний будут очень медленными, потому что для поиска не используется индекс.Для эффективности вам придется либо использовать прямоугольную ограничивающую рамку, чтобы сделать это быстрее, либо использовать базу данных со встроенными функциями ГИС. PostGIS бесплатен, и вот статья о поиске ближайшего соседа:

http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_nearest_neighbor_generic

0 голосов
/ 30 мая 2015

Есть гораздо более простой способ решить эту проблему.

  1. Мы знаем, что разница в 0,1 по широте на одной и той же долготе равна расстоянию в 11,12 км. (1,0 в лате сделает это расстояние 111,2 км)

  2. Также с разницей в 0,1 по долготе и той же широте расстояние составляет 3,51 км (из-за 1,0 расстояние составит 85,18 км) (для пересчета в мили мы умножаем это на 1.60934)

ПРИМЕЧАНИЕ. Имейте в виду, что долгота изменяется от -180 до 180, поэтому разница между -180 и 179,9 составляет 0,1, что составляет 3,51 км.

Все, что нам нужно знать сейчас, это список всех почтовых индексов с lon и lat (у вас это уже есть)

Так что теперь, чтобы сузить поиск на 90%, вам нужно всего лишь вырезать все результаты, которые точно не будут находиться в пределах 100 километров, например. наши координаты $ lat1 и $ lon2 для 100 километров разница в 2 в широтах и ​​долготе будет более чем достаточной.

$lon=...;
$lat=...;
$dif=2;

SELECT zipcode from zipcode_table WHERE latitude>($lan-$dif) AND latitude<($lan+$dif) AND longitude>($lon-$dif) AND longitude<($lon+$dif)

Нечто подобное. Конечно, если вам нужно покрыть меньшую или большую область, вам нужно соответственно изменить $ dif.

Таким образом, Mysql будет рассматривать только очень ограниченные ресурсы для экономии ресурсов.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...