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

Вычислите ограничивающий прямоугольник, чтобы выбрать подмножество строк в предложении WHERE вашего SQL-запроса, так что вы выполняете только дорогостоящий расчет расстояния на этом подмножестве строк, а не на все 200 тыс. Записей в таблице. Метод описан в этой статье о 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); 

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

10 км по прямой линии:

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

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

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

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

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

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

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

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

   2d. Макс. Долгота – 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 тыс. Записей, локализованных внутри квадрата размером 100х100 кв. Км, сосредоточенного вокруг определенного момента. Я использовал этот трюк у Марка, но производительность слишком плохая. 5 пользователей / второй запрос для ближайших точек lat / lon в течение нескольких часов, а запросы начинаются с 10-15 секунд, и это происходит после того, как я скорректировал параметры mySQL в my.cnf. Даже не хочу думать о том, что произойдет, когда будет составлять 2 миллиона записей по всему миру.

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

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

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

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

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