Существует ли алгоритм постоянного времени для генерации кривой гильбертовых точек пошагово?

Question

Wikipedia Article на гильбертовом кубе включает функции, которые кодируют/декодируют произвольные индексы в/из произвольных точек кривой Гильберта. Эти алгоритмы не являются постоянными. Существует ли алгоритм с постоянным временем, который, учитывая фактическую точку кривой (и, возможно, некоторое требуемое состояние), генерирует следующую точку (и следующее состояние)?

Формально я хочу тип State и кортеж (initialState, nextState) :: (State, State -> ((Nat, Nat), State), таким образом, что каждое применение nextState дает нам следующую точку кривой Гильберта, и таким образом, что, что nextState является оптимальным, что, вероятно, не относится к алгоритму представленный в Википедии, поскольку он, возможно, упускает возможность для инкрементных вычислений, которые мы имеем здесь. Иллюстрация:

data State = _ 

initialState :: State 
initialState = _ 

-- This must be optimal 
nextState :: State -> ((Nat, Nat), State) 
nextState = _ 

-- Returns the `nth point` of the hilbert curve 
hilbertPoint :: Nat -> (Nat, Nat) 
hilbertPoint n = iterate (snd.nextState) initialState !! n 

Answer 1

Если вы имеете в виду «? Есть ли алгоритм для генерации вершины кривой Гильберта в последовательности с O (1) затрат на вершине» ответ - да. Это стандартное упражнение в рекурсии. Если у вас есть обычные черепахи графических примитивов для излучающих вершин, это выглядит следующим образом:

-- Angle must be + or - 90.0 degrees. 
procedure Hilbert(Order : in Natural; 
        Angle : in Float) is 
    Step : constant Float := 1.0; -- length of base case edge 
begin 
    if Order > 0 then 
     Turn(Angle); 
     Hilbert(Order - 1, -Angle); 
     Walk(Step); 
     Turn(-Angle); 
     Hilbert(Order - 1, Angle); 
     Walk(Step); 
     Hilbert(Order - 1, Angle); 
     Turn(-Angle); 
     Walk(Step); 
     Hilbert(Order - 1, -Angle); 
     Turn(Angle); 
    end if; 
end Hilbert; 

Инициировать рекурсию с

, чтобы получить кривую 7-го порядка.

Добавление

Так как вы, кажется, заинтересованы в шаблоне итератора, вы можете использовать либо выше логику и язык (например, Python или Ruby) с генераторами, или вы можете реализовать генератор самостоятельно с обычные методы для рекурсивного преобразования итеративного кода.