Определите / создайте геозону / ограничивающую рамку на лету

Question

У меня есть таблица MySQL по широте / долготе (вспомним школьный кампус или торговый центр).

В каждом месте (школе / торговом центре) могут храниться десятки позиций GPS, хранящихся в таблице.Все местоположения фиксируются с помощью мобильного приложения, и эти местоположения могут представлять все: от входов в определенные комнаты (конференции) до легко идентифицируемых местоположений, таких как лифты.

Пользователь отправляет запрос (т. Е. Очистка уборщика на острове 6) иМне нужно убедиться, что отправляемый запрос (очистка) находится в геозоне, установленной путем нахождения 4 точек, наиболее удаленных друг от друга для этого местоположения.

В настоящее время мы используем поиск Haversine, но мы хотим преобразоватьэто огороженная система.Чего мы не можем сделать, так это создать отдельную таблицу геозон.

Я погуглил и ничего не нашел (вероятно, я не использую правильные термины).Как мне построить этот запрос?

Answer 1

На первом уровне аппроксимации вы можете отсканировать ограничивающий прямоугольник.

Допустим, у вас есть таблица loc со столбцами loc_id, lat, lng.И скажем, у вашей кандидатской точки есть позиция @ptLat, @ptLng.

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

          SELECT loc_id, MAX(lat) north, MAX(lng) east, MIN(lat) south, MIN(lng) west
            FROM loc
           GROUP BY loc_id

Это быстро, если у вас есть индекс на (loc_id, lat, lng).Это также быстро, потому что вы можете избежать всех тригонометрических функций в вычислении Великого круга.

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

Тогда вы можетеdo

 SELECT loc_id
   FROM  (
          SELECT loc_id, MAX(lat) north, MAX(lng) east, MIN(lat) south, MIN(lng) west
            FROM loc
           GROUP BY loc_id
         ) box
   JOIN ( SELECT @ptLat ptLat, @ptLon, ptLon ) pt
        ON ptLat <= north
       AND ptLat >= south
       AND ptLon <= east
       AHD ptLon >= west

Это дает вам результирующий набор со значениями loc_id, совпадающими с вашей точкой-кандидатом.

Если ваши лат, lng-данные беспорядочные - если у них много точек выброса -это не будет работать очень хорошо.Это чувствительно к ошибкам.Например, если местоположение в Исландии имеет много точек рядом с ним, но одна точка в Гренландии неправильно закодирована, ограничивающая рамка будет нелепо большой.

Если она не достаточно точна для вас, вам следует исследовать выпуклые корпуса алгоритмы.Но это, скорее всего, выведет вас за пределы чистого SQL.