Преобразование трехмерных координат в индекс кривой заполнения пространства (Пеано, Гильберт...)
Хотя преобразование трехмерных координат в кривую z-порядка было относительно простым ( Эффективное преобразование z-порядка в Фортране), у меня возникают трудности, чтобы обернуть голову вокруг математики для использования различных кривых заполнения пространства, например Пеано или Гильберта. Будем благодарны за любые подсказки о том, как может выглядеть реальный код для преобразования. Цель состоит в том, чтобы иметь подпрограмму, которая принимает координаты XYZ в качестве входных данных с любой необходимой нормализацией и возвращает индекс кривой заполнения пространства.
подпрограмма (x, y, z, space_filling_index)
И в связи с этим: я читал, что есть много способов определить кривые Гильберта в трехмерном пространстве, которые были бы лучшими с точки зрения локальности? Если есть определенный ответ на это...
Приложение будет переупорядочивать ячейки в декартовой вычислительной сетке с целью увеличения попаданий в кэш, когда ячейка получает доступ к соседним ячейкам.
1 ответ
Кривая Гильберта работает путем рекурсивного деления куба (для 3D), используя одну и ту же базовую форму на каждом шаге, поворачивая кривую так, чтобы точка выхода подкуба совпадала с точкой входа следующего куба.
Фантастический ресурс - технический отчет Компактных индексов Гильберта Ч. Гамильтона. В докладе также представлен компактный индекс Гильберта для некубических систем.
Обдумывая это, я написал сообщение в блоге в 2015 году: Понимание кривой Гильберта с образцом кода Python для индекса Гильберта и иллюстрация поворота гильбертовых "субкубов". Как часть кода моделирования молекулярной динамики на основе частиц, который я написал, я реализовал компактный индекс Гильберта в Фортране, см. Здесь.
Повторное подробное обсуждение деталей "выходит за рамки" ответа SO, я верю, но приведенные выше ресурсы должны вам очень помочь.