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

Question

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

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

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

Answer 1

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

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

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

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