Подтвердить что ты не робот

Как эффективно находить ближайшие места поблизости от данного места

Я создаю script, где загрузка бизнеса загружается в базу данных mySQL с широтой и долготой. Затем я предоставляю script широту долготы (конечного пользователя), а script должен рассчитать расстояние от предоставленного lat/long до EACH из записей, которые он получает из базы данных, и упорядочить их по порядку ближайшего к дальнему.

Мне только реально нужно около 10 или 20 "ближайших" результатов, но я не могу думать о том, чтобы сделать это иначе, чем получить все результаты из базы данных и запустить функцию для каждого из них, а затем сортировать массив.

Это то, что у меня уже есть:

<?php

function getDistance($point1, $point2){

    $radius      = 3958;      // Earth 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";
?>

Теперь это выполняется достаточно быстро, только с двумя или тремя предприятиями в базе данных, но в настоящее время я загружаю 5 тыс. бизнес-данных в базу данных, и я волнуюсь, что это будет невероятно медленным для этого для КАЖДОЙ записи? Как вы думаете?

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

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

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

4b9b3361

Ответ 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), и ограничение строк на подмножество ваших записей на основе этого (WHERE широта BETWEEN $minLat AND $maxLat И долгота МЕЖДУ $minLong И $maxLong). Затем MySQL нужно выполнить расчет расстояния для этого подмножества строк.

ДАЛЬНЕЙШЕЕ ИЗОБРАЖЕНИЕ (как пояснение к предыдущему редактированию)

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

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

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

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

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

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

Существует намного более простой способ работать с этим.

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

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

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

Теперь нам нужно знать список всех zipcodes с 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 будет рассматривать только очень ограниченные ресурсы ресурсов сохранения.