Как рассчитать и использовать значение Мортона (z-index) для индексации геоданных с помощью PHP / MySQL?

Question

У меня есть таблица записей MySQL, каждая из которых имеет координату широта / долгота. По этим данным проводится поиск на основе центральной точки и радиуса (возвращаются все записи в радиусе). Я использую сферический закон косинусов, чтобы вычислить расстояние в моем запросе. Моя проблема заключается в том, что индексирование геоданных ужасно неэффективно (значения широты / долготы хранятся как числа с плавающей запятой). Использование пространственных расширений MySQL не вариант. При наборе данных размером около 100 тыс. Для выполнения запроса требуется неоправданно много времени.

Я провел некоторое исследование, и похоже, что использование z-индекса, т. Е. Числа Мортона, может помочь. Я мог бы вычислить число Мортона для каждой записи при вставке, а затем вычислить высокое / низкое значение Мортона для ограничительной рамки на основе радиуса / центральной точки Земли / заданного радиуса поиска.

Я достаточно знаю об этом материале только для создания своего приложения, поэтому я не совсем уверен, сработает ли это, и я также не знаю, как вычислить число Мортона в PHP. Это будет побитовая операция?

Answer 1

Если ваш радиус мал по сравнению с размером Земли, то вы, вероятно, можете обойтись простым 2D-пифагором, а не дорогой трехмерной сферической геометрией. Это, вероятно, менее верно, чем ближе вы к полюсам, так что я надеюсь, что вы не наносите на карту пингвинов или белых медведей!

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

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

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