Поиск диапазона с индексом кривой Гильберта
У меня есть индекс кривой Гильберта, основанный на этом алгоритме. Я беру от двух до четырех значений (широта, долгота, время в формате Unix и идентификационный код) и создаю 1-ю кривую Гильберта.
Я ищу способ использовать эти данные для создания запроса ограничивающего прямоугольника (то есть "найти все идентификаторы в этом прямоугольнике).
Я ищу способ сделать это, не расшифровывая код 1d Гильберта обратно в его составные части. Кажется, легче сделать это с помощью кривой Мортона /Z-порядка, но меня интересует сохранение локальности.
Мой вопрос: если бы я создал 2-мерный диапазон кривой Гильберта (то есть я преобразовал диапазон прямоугольника в кривую Гильберта, чтобы значения x1y1-> hilbert1 и x2y2-> hilbertvalue2) все значения соответствующих 2-мерных значений Гильберта попадали в их диапазон?
Например, если бы я преобразовал (1,2) и (20,30) в значения Гильберта, а затем произвел поиск всех значений между hilbert value1 и hilbertvalue2, все ли декодируемые мной значения попадают в пределы (1,2) и (20, 30) или мне придется выполнять дополнительные преобразования?
Дополнительной проблемой является создание диапазона, когда у вас более двух измерений. У меня есть возможность конвертировать в и из кривых Гильберта, но как я могу убедиться, что даже 4d значения имеют широту и долготу, которые попадают в один и тот же прямоугольник / ограничивающий прямоугольник?
Благодарю.
0 ответов
Мой вопрос: если бы я создал 2-мерный диапазон кривой Гильберта (т.е. я преобразовал диапазон прямоугольника в кривую Гильберта, чтобы значения x1y1-> hilbert1 и x2y2-> hilbertvalue2) все значения соответствующих 2-мерных значений Гильберта попадали в их диапазон?
Ответ - нет. Это часть проблемы использования индекса Гильберта. Ниже приведен пример кривой. Вы заметите, что у вас может быть точка на кривой с более высоким индексом, чем у вершин блока, содержащего эту точку. Голубой прямоугольник является примером, в котором вершины имеют индексы 117, 122, 133, 138, но внутри (хотя на границе) находится значение 143.
Один простой подход - это грубая сила, когда вы посещаете каждую ячейку в области поиска и вычисляете индекс в этих ячейках. Затем вы составляете список диапазонов индексов, которые будут использоваться в запросе. Вы можете присоединиться к некоторым диапазонам и отфильтровать их позже в качестве оптимизации производительности на основе эталонных тестов (для большого количества запросов с небольшими диапазонами может потребоваться больше времени, чем для запроса меньшего количества больших диапазонов, за которым следует фильтр). Я хотел бы увидеть что-то более элегантное, чем это, но еще не видел это.
ОБНОВЛЕНИЕ: я разработал кое-что более изящное, чем техника грубой силы, и детали (и библиотека java) находятся по адресу https://github.com/davidmoten/hilbert-curve. Короче говоря, конечные точки диапазонов, которые точно охватывают окно поиска, будут находиться по периметру региона. Если вы отсортируете все значения кривой Гильберта по периметру региона и начнете с наименьшего значения, вы можете затем спарить все диапазоны, выполнив тесты на предмет того, находится ли следующая точка кривой на периметре, выходит из поля или находится внутри. коробка.
Дополнительной проблемой является создание диапазона, когда у вас более двух измерений. У меня есть возможность конвертировать в и из кривых Гильберта, но как я могу убедиться, что даже 4d значения имеют широту и долготу, которые попадают в один и тот же прямоугольник / ограничивающий прямоугольник?
Описанная выше техника периметра работает для любого количества измерений (но, конечно, становится дороже!).
Для 2-х измерений вы можете рассматривать кривую как число 4 (quadkey) и осуществлять поиск слева направо.