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

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

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

ИЗМЕНИТЬ

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

//  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);

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

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

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

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

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

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

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

   2а. Минимальная широта - 34.1927777778, -85.0169444444

   2б. Минимальная долгота - 34.2094444444, -85.1169444444

   2в. Максимальная широта - 34.2261111111, -85.0169444444

   2д. Максимальная долгота - 34.2094444444, -84.9169444444

3. Запустите запрос с минимальным и максимальным значением для каждого направления.

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

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

Я использую следующую функцию для расчета расстояния между двумя точками GPS US84. Передаются два параметра, каждый параметр представляет собой массив, первый элемент которого — широта, а второй — долгота. Я считаю, что его точность составляет несколько футов, чего должно быть достаточно для всех, кроме самых заядлых фанатов 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;
}

ОБНОВЛЕНИЕ

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

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

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

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

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

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

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