Поиск диапазона с индексом кривой Гильберта

Question

У меня есть индекс кривой Гильберта, основанный на этом алгоритме.Я беру от двух до четырех значений (широта, долгота, время в формате Unix и идентификационный код) и создаю 1-ю кривую Гильберта.

Я ищу способ использовать эти данные для создания запроса ограничительной рамки (т. Е. "Найти все идентификаторы в этом прямоугольнике).

Я ищу способ сделать этобез декодирования 1-го кода Гильберта обратно в его составные части. Кажется, проще сделать это с помощью кривой Мортона / Z-порядка, но меня интересует сохранение локальности.

Мой вопрос: создал ли ядиапазон 2-й кривой Гильберта (т. е. я преобразовал диапазон прямоугольника в кривую Гильберта, чтобы значения x1y1-> hilbert value1 и x2y2-> hilbertvalue2) все значения соответствующих значений 2d-гильберта попадали в их диапазон?

НапримерЕсли бы я преобразовал (1,2) и (20,30) в значения Гильберта, а затем искал все значения между hilbertvalue1 и hilbertvalue2, все декодированные мной значения попадали бы в пределы (1,2) и (20, 30),или мне придется выполнить дополнительные преобразования?

Дополнительная проблема заключается в создании диапазона, когда у вас более двух измерений. У меня есть возможность конвертировать в ииз кривых Гильберта, но как я могу убедиться, что даже 4d значения имеют широту и долготу, которые попадают в один и тот же прямоугольник / ограничивающий прямоугольник?

Спасибо.

Answer 1

Для 2-х измерений вы можете рассматривать кривую как число-4 (quadkey) и выполнять поиск слева направо.

Answer 2

Мой вопрос: если бы я создал 2-мерный диапазон кривой Гильберта (т.е. я преобразовал диапазон прямоугольника в кривую Гильберта, чтобы значения x1y1-> hilbert1 и x2y2-> hilbertvalue2) были бы всеми значениями соответствующего 2-го Гильбертазначения попадают в их диапазон?

Ответ - нет.Это часть проблемы использования индекса Гильберта.Ниже приведен пример кривой.Вы заметите, что у вас может быть точка на кривой с более высоким индексом, чем у вершин блока, содержащего эту точку.Голубой прямоугольник - это пример, где у вершин есть индексы 117, 122, 133, 138, но внутри (хотя на границе) есть значение 143.

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

ОБНОВЛЕНИЕ: я разработал что-то более элегантное, чем техника грубой силы, и детали (и библиотека Java) находятся вhttps://github.com/davidmoten/hilbert-curve. Короче говоря, конечные точки диапазонов, которые точно охватывают окно поиска, будут все по периметру региона.Если вы отсортируете все значения кривой Гильберта по периметру региона и начнете с наименьшего значения, вы можете затем спарить все диапазоны, выполнив тесты на предмет того, находится ли следующая точка кривой на периметре, выходит из поля или находится внутри.коробка.

Дополнительная проблема заключается в создании диапазона, когда у вас более двух измерений.У меня есть возможность конвертировать в и из кривых Гильберта, но как я могу убедиться, что даже 4d значения имеют широту и долготу, которые попадают в один и тот же прямоугольник / ограничивающий прямоугольник?

Метод периметра, описанный вышеработает для любого количества измерений (но, конечно, становится дороже!).