Гео-поиск (расстояние) в PHP/MySQL (производительность)

Ответ 1

Вычислить ограничивающий прямоугольник для выбора подмножества строк в предложении WHERE вашего SQL-запроса, так что вы выполняете только дорогостоящий расчет расстояния в этом подмножестве строк, а не против всех записей 200k в вашей таблице. Этот метод описан в статье о Movable Type (с примерами кода PHP). Затем вы можете включить вычисление Haversine в ваш запрос к этому подмножеству для вычисления фактических расстояний и коэффициент в предложении HAVING в этой точке.

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

ИЗМЕНИТЬ

Если вы не считаете, что haverine достаточно точен, тогда есть также формула Винченти.

//  Vincenty formula to calculate great circle distance between 2 locations expressed as Lat/Long in KM

function VincentyDistance($lat1,$lat2,$lon1,$lon2){
    $a = 6378137 - 21 * sin($lat1);
    $b = 6356752.3142;
    $f = 1/298.257223563;

    $p1_lat = $lat1/57.29577951;
    $p2_lat = $lat2/57.29577951;
    $p1_lon = $lon1/57.29577951;
    $p2_lon = $lon2/57.29577951;

    $L = $p2_lon - $p1_lon;

    $U1 = atan((1-$f) * tan($p1_lat));
    $U2 = atan((1-$f) * tan($p2_lat));

    $sinU1 = sin($U1);
    $cosU1 = cos($U1);
    $sinU2 = sin($U2);
    $cosU2 = cos($U2);

    $lambda = $L;
    $lambdaP = 2*M_PI;
    $iterLimit = 20;

    while(abs($lambda-$lambdaP) > 1e-12 && $iterLimit>0) {
        $sinLambda = sin($lambda);
        $cosLambda = cos($lambda);
        $sinSigma = sqrt(($cosU2*$sinLambda) * ($cosU2*$sinLambda) + ($cosU1*$sinU2-$sinU1*$cosU2*$cosLambda) * ($cosU1*$sinU2-$sinU1*$cosU2*$cosLambda));

        //if ($sinSigma==0){return 0;}  // co-incident points
        $cosSigma = $sinU1*$sinU2 + $cosU1*$cosU2*$cosLambda;
        $sigma = atan2($sinSigma, $cosSigma);
        $alpha = asin($cosU1 * $cosU2 * $sinLambda / $sinSigma);
        $cosSqAlpha = cos($alpha) * cos($alpha);
        $cos2SigmaM = $cosSigma - 2*$sinU1*$sinU2/$cosSqAlpha;
        $C = $f/16*$cosSqAlpha*(4+$f*(4-3*$cosSqAlpha));
        $lambdaP = $lambda;
        $lambda = $L + (1-$C) * $f * sin($alpha) * ($sigma + $C*$sinSigma*($cos2SigmaM+$C*$cosSigma*(-1+2*$cos2SigmaM*$cos2SigmaM)));
    }

    $uSq = $cosSqAlpha*($a*$a-$b*$b)/($b*$b);
    $A = 1 + $uSq/16384*(4096+$uSq*(-768+$uSq*(320-175*$uSq)));
    $B = $uSq/1024 * (256+$uSq*(-128+$uSq*(74-47*$uSq)));

    $deltaSigma = $B*$sinSigma*($cos2SigmaM+$B/4*($cosSigma*(-1+2*$cos2SigmaM*$cos2SigmaM)- $B/6*$cos2SigmaM*(-3+4*$sinSigma*$sinSigma)*(-3+4*$cos2SigmaM*$cos2SigmaM)));

    $s = $b*$A*($sigma-$deltaSigma);
    return $s/1000;
}


echo VincentyDistance($lat1,$lat2,$lon1,$lon2);

Ответ 2

Что, если вы подходите к проблеме под другим углом?

10 км по прямой:

• на широте равно ~ 1 '(минута)
• по долготе равна ~ 6 '(минут)

Используя это как основу, сделайте некоторую быструю математику и в своем запросе добавьте в предложение WHERE удаление любых местоположений, которые находятся за пределами поля, созданного добавлением буферной зоны с предположением 1 'lat и 6 'долгий

Работа с этим изображением:

• Местоположение GPS, которое вы ищете (34 ° 12 '34.0 ", -85 ° 1' 1.0" ) [34.2094444444, -85.0169444444]

• Вы найдете минимальную/максимальную широту/долготу

  2а. Мин. Широта - 34.1927777778, -85.0169444444

  2b. Min Долгота - 34.2094444444, -85.1169444444

  2в. Макс. Широта - 34.2261111111, -85.0169444444

  2d. Макс. Долгота - 34.2094444444, -84.9169444444

• Запустите свой запрос с помощью min и max каждого направления

  SELECT *
  
  FROM geoloc
  
  WHERE
  
  lat >= 34.1927777 AND
  
  lat <= 34.2261111 AND
  
  long >= -85.1169444 AND
  
  long <= -84.9169444;
  

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

Я использую следующую функцию для вычисления расстояния между двумя местоположениями US84 GPS. Два параметра передаются, каждый параметр представляет собой массив с первым элементом, который является широтой, а второй - долготой. Я считаю, что он имеет точность до нескольких футов, что должно быть достаточно для всех, кроме самых сложных GPS-афилов. Кроме того, я считаю, что это использует формулу расстояния Хаверсина.

$distance = calculateGPSDistance (массив (34.32343, -86.342343), массив (34.433223, -96.0032344));

function calculateGPSDistance($site1, $site2)
{
    $distance = 0;
    $earthMeanRadius = 2.0891 * pow(10, 7);

    $deltaLatitude = deg2rad($site2[0] - $site1[0]);
    $deltaLongitude = deg2rad($site2[1] - $site1[1]);
    $a = sin($deltaLatitude / 2) * sin($deltaLatitude / 2) + cos(deg2rad($site1[0])) * 
        cos(deg2rad($site2[0])) * sin($deltaLongitude / 2) * sin($deltaLongitude / 2);
    $c = 2 * atan2(sqrt($a), sqrt(1-$a));
    $distance = $earthMeanRadius * $c;

    return $distance;
}

UPDATE

Я забыл упомянуть, моя дистанционная функция вернет расстояние в футах.

Ответ 3

Вы можете попробовать quadkey. Это пространственный индекс и уменьшает размерность. Он подразделяет карту на плитки, но вы можете использовать ее для хранения очков. Вы можете загрузить мой php-класс hilbert-curve @phpclasses.org. Он также включает в себя z-кривую и морскую кривую. Важно знать, что он использует проекцию меркатора. Вы можете посмотреть плитки Bing. В нем объясняется, как использовать quadkey. Вам нужны координаты x, y и z (масштаб или глубина). Затем он дает вам четырехъядерную клавиатуру.

Ответ 4

То, что я делал до сих пор, так же, как @Mark описано выше. Я думаю, что жизнеспособное решение для небольших сайтов я считаю не лучшим для моего случая (200 тыс. Записей, локализованных внутри квадрата размером 100 х 100 кв. Км, сосредоточенного вокруг определенной точки. Я использовал этот же трюк Марка, но производительность слишком плохая. 5 пользователей/второй запрос для ближайших точек lat/lon в течение нескольких часов, а запросы начинаются с 10-15 секунд, и это происходит после того, как я скорректировал параметры mySQL в my.cnf. Даже не хочу думать о том, что произойдет, когда будет 2 миллиона записей по всему миру.

Итак, теперь время для шага 2: кривая Гильберта. Он должен решить проблему индекса B-дерева на (lat, lon) столбцах, который является расточительным (onrange scans, только одна часть индекса B-дерева используется), используя только один индекс для одного столбца (hilbert_number). hilbert_number - число, рассчитанное на основе точечных координат lat/lon на кривой Гильберта.

Но вторая проблема - проверка расстояния между неподвижной точкой и всем из предыдущего подмножества результатов по формуле Хаверсина остается. Эта часть может быть очень медленной. Поэтому я подумывал о том, чтобы как-то более тщательно тестировать дистанцию, помещая все на кривую Гильберта и применяя некоторую битмаску к этому подмножеству результатов вместо применения формулы Хаверсина. Я просто не знаю, как бы я это сделал...

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

Что мне нужно сделать сейчас, это переключиться на числа Гильберта и посмотреть, как он себя ведет. Но я сомневаюсь, что это увеличит производительность в 10 раз!