是否有用于递增生成希尔伯特点曲线的恒定时间算法？

Question

希尔伯特立方体上的 Wikipedia Article 包括 encode/decode 任意索引 to/from 希尔伯特曲线上任意点的函数。这些算法不是恒定时间的。是否有一个恒定时间算法，给定曲线上的一个实际点（可能还有一些所需的状态），生成下一个点（和下一个状态）？

形式上，我想要一个类型 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

如果您的意思是 "Is there an algorithm for generating the vertices of a Hilbert curve in sequence with O(1) cost per vertex?"，那么答案是肯定的。这是递归的标准练习。如果您有用于发射顶点的常用海龟图形基元，它看起来像这样：

-- 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;

用

启动递归

Hilbert(7, 90.0);

得到 7 阶曲线。

加法

由于您似乎对迭代器模式感兴趣，您可以使用上面的逻辑和一种语言（如 Python 或 Ruby）生成器，或者您可以自己实现生成器使用递归到迭代代码转换的常用技术。

是否有用于递增生成希尔伯特点曲线的恒定时间算法？

Is there a constant time algorithm for generating hilbert points curve incrementally?

algorithm

haskell

functional-programming

hilbert-curve