CODEWITHSUNDEEP
algorithmhaskellfunctional-programminghilbert-curve
MaiaVictor
MaiaVictor

Reputation: 53017

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

The Wikipedia Article on the Hilbert Cube includes functions that encode/decode arbitrary indices to/from arbitrary points on the Hilbert Curve. Those algorithms aren't constant-time. Is there a constant-time algorithm that, given an actual point on the curve (and, perhaps, some required state), generates the next point (and the next state)?

Formally, I want a type State, and a tuple (initialState, nextState) :: (State, State -> ((Nat, Nat), State), such that each application of nextState gives us the next point of the Hilbert curve, and such that that nextState is optimal, which is probably not the case for the algorithm presented on Wikipedia, since it possibly misses the opportunity for incremental computation that we have here. Illustration:

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

Upvotes: 2

Views: 624

Answers (1)

Gene
Gene

Reputation: 46980

If you mean "Is there an algorithm for generating the vertices of a Hilbert curve in sequence with O(1) cost per vertex?" the answer is yes. This is a standard exercise in recursion. If you have the usual turtle graphics primitives for emitting the vertices, it looks like this:

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

Initiate the recursion with 

Hilbert(7, 90.0);

to get a 7th order curve.

Addition

Since you seem to be interested in an iterator pattern, you can either use the logic above and a language (like Python or Ruby) with generators, or you can implement the generator yourself with the usual techniques for recursive to iterative code conversion.

Upvotes: 0

Related Questions