Сортировка по Гильберту с помощью алгоритма «разделяй и властвуй»?

Я пытаюсь отсортировать d-мерные векторы данных по их порядку Гильберта для массовой загрузки пространственного индекса.

Однако я не хочу явно вычислять значение Гильберта для каждой точки, что, в частности, требует установки определенной точности. В данных большой размерности это включает такую ​​точность, как 32 * d бит, что становится довольно запутанным для эффективного выполнения. Когда данные распределяются неравномерно, некоторые из этих вычислений не нужны, и необходима дополнительная точность для частей набора данных.

Вместо этого я пытаюсь применить метод разбиения на разделы. Когда вы смотрите на двумерную кривую Гильберта первого порядка

1   4
|   |
2---3

, я бы сначала разделил данные по оси x, так что первая часть (не обязательно содержащая половину объектов!) Будет состоять из 1 и 2 (еще не отсортировано), а во второй части будут только объекты из 3 и 4. Затем я бы снова разделил каждую половину по оси Y, но в обратном порядке на 3-4.

По сути, я хочу реализовать стратегию «разделяй и властвуй» (тесно связанную с QuickSort - для равномерно распределенных данных это должно быть даже оптимально!) И вычислять только необходимые «биты» индекса Гильберта по мере необходимости. Предполагая, что в «1» есть единственный объект, нет необходимости вычислять его полное представление; и если объекты распределены равномерно, размеры разделов быстро уменьшатся.

Я знаю обычный учебный подход к преобразованию в длинное серое кодирование с чередованием измерений. Это не то, что я ищу (существует множество примеров этого). Я явно хочу только ленивую сортировку «разделяй и властвуй» . К тому же мне нужно больше, чем 2D.

Кто-нибудь знает статью или алгоритм сортировки Гильберта, который работает таким образом? Или ключевая идея, как получить правильные "вращения", какое представление выбрать для этого? В частности, в более высоких размерностях ... в 2D это тривиально; 1 поворачивается на + y, + x, а 4 - на -y, -x (поворачивается и переворачивается). Но я полагаю, что в более высоких измерениях это становится более сложным.

(Результат, конечно, должен быть таким же, как при сортировке объектов по их гильбертовому порядку сразу с достаточно большой точностью; я просто пытаюсь сэкономить время, вычисляя полное представление, когда оно не нужно, и мне приходится управлять Многие люди хранят хэш-карту «объект для числа Гильберта», что довольно дорого.)

Подобные подходы должны быть возможны для кривых Пеано и Z-кривой, и, вероятно, их немного проще реализовать ... Я, вероятно, должен попробовать эти сначала (Z-кривая уже работает - она ​​действительно сводится к чему-то очень похожему на QuickSort, использующему соответствующее среднее значение / значение сетки в качестве виртуальной оси и циклически перебирая измерения для каждой итерации).

Редактировать : см. Ниже, как я решил это для Z и кривых Пеано. Он также уже работает для 2D кривых Гильберта. Но у меня пока нет правильных поворотов и инверсий для кривых Гильберта.