1

The Hilbert curve Wikipedia article includes some C code that shows how to map coordinates to the curve but it only works for two-dimensions. I'm having trouble finding any examples that work for N-dimensions (curve examples are plentiful but not the mapping function). Does someone have any code or the description of an algorithm for doing so that they can share?

I'm currently blocked on the rotation function. I can guess, but since I can't find any sort of paper or other description using language that I can understand I can't be confident of what I end-up with.

Note that I'd love to see something that's as simple as the Wikipedia version. It seems like the mutation that I'm going for should also be very simple. I found the SO post at Mapping N-dimensional value to a point on Hilbert curve but it's so complex and such a foreign design to the one I started with (even though both are non-recursive so it seems like they should be more similar) that it looks totally opaque to me.

Community
  • 1
  • 1
Dustin Oprea
  • 9,673
  • 13
  • 65
  • 105
  • So you didn't find this: http://stackoverflow.com/questions/499166/mapping-n-dimensional-value-to-a-point-on-hilbert-curve – Morrison Chang Jan 23 '17 at 04:40
  • Of course I did, but the algorithms are completely different with that one being considerably more complicated. Neither of them seems to be recursive (which I thought might be the only difference), but the Wikipedia version principally uses summing whereas that SO-post's version principally uses XORs. I'm assuming, as a lay-person, that the gray-encode at the end merely has to do with deterministic sorting and can be disposed of. Since the Wikipedia version is so simple, accounting for N-dimensions should also be simple. No need to introduce so much complexity (unless I'm driven to, anyway). – Dustin Oprea Jan 23 '17 at 04:50
  • I updated the post to cite that. – Dustin Oprea Jan 23 '17 at 04:55
  • I'm not sure what you mean by `gray-encode at the end merely has to do with deterministic sorting and can be disposed of` as that sounds like you are not getting the idea as stated in the Wikipedia article that `Hilbert curves in higher dimensions are an instance of a generalization of Gray codes` It may help to explain what you mean by 'rotation function'. – Morrison Chang Jan 23 '17 at 05:23
  • If you are trying to draw a Hilbert Curve in 3 dimensions (or more?) - have you looked at L-Systems http://math.stackexchange.com/questions/123642/representing-a-3d-hilbert-curve-as-an-l-system – Morrison Chang Jan 23 '17 at 05:38
  • @MorrisonChang I've seen a couple of places where stepping through the curve, I think it was, indicated that points (coordinates?) were returned in gray-code order (the only reference to GC that I've seen so far). I missed where it had mentioned gray-codes in the Wikipedia article. I hadn't read that particular article comprehensively. I'm not sure I would've known what to do with that information as the implementation in that very same article somehow performs its calculations without any gray-code mechanics. That makes its use in the C# implementation seem superfluous. No? – Dustin Oprea Jan 23 '17 at 05:55
  • Drawing is not the problem. I need to map coordinates on to the HC. – Dustin Oprea Jan 23 '17 at 05:58
  • IMO just copy and paste the table (it's hardwired):http://stackoverflow.com/questions/14519267/algorithm-for-generating-a-3d-hilbert-space-filling-curve-in-python. – Micromega Jan 23 '17 at 17:59

0 Answers0