Talk:Hilbert curve

Hausdorff dimension

It seems doubtful to me whether the Hausdorff dimension of a space-filling curve is help- or meaningful in any sense. Shall we remove it? (Same situation with Sierpiński curve) — Nol Aders 16:02, 4 January 2006 (UTC)

I agree. And the recently added discussion of Fractal dimension makes the problem glaringly obvious. If we interpret “the curve” as being the image of the curve in the plane, then we are simply left with the unit square, which is two-dimensional by any reasonable definition. The parenthetical remark (in the limit $n\rightarrow \infty$) just adds an air of mystery. If we interpret “the curve” as the graph of the parametrized curve in three-dimensional space, then I am not really sure how to compute the fractal dimension, but I strongly suspect the answer is still 2. The remark on the fractal dimension being 1 seems nonsensical to me, since the four quarters of the curve are scaled-down versions of the full curve by a factor of 2, not 4 (it is the linear scaling factor that is relevant, not the area scaling factor). Hence the answer should again be 2. Hanche (talk) 17:19, 7 May 2009 (UTC)

Basic error about the factor. I undid revisions.Prokofiev2 (talk) 09:01, 10 May 2009 (UTC)

by the way, concerning the "meaning" of the Hausdorff dimension of a space-filling curve (Aders' remark): Yes, it is meaningful. The Hausdorff dimension is even meaningful for non-fractal objects, like a square, or a straight line. The Hausdorff measure is nothing more than the natural extension of euclidian measures (length, area, volume...). Prokofiev2 (talk) 09:31, 10 May 2009 (UTC)

Yes, of course it is meaningful. But is it meaningful in a non-trivial and/or interesting way? I think not, hence I think it should be removed. Hanche (talk) 15:01, 11 May 2009 (UTC)

We agree on the fact it is trivial. But they have their place on a list of fractals, could we discard important examples of curves because their dimension is "too simple" ?Prokofiev2 (talk) 21:59, 11 May 2009 (UTC)

Um, I never thought of discarding the curve (meaning the whole article, I presume). And the issue is not the simplicity of the dimension, it is the triviality of the reason for the dimension being what it is. The Sierpinski tetrahedron, for example (a misnomer but easily understandable) had fractal dimension 2, but that is still interesting. The image of the Hilbert curve, OTOH, is just a square, which is utterly boring. Hanche (talk) 16:04, 12 May 2009 (UTC)

I think the discussion of the Hausdorff dimension is useful here. Anyone who is interested in this curve and unaware of Hausdorff dimension would be well-served by the reference to it, and anyone who is already aware of it will be well-served to know in which sense of dimension the dimension is two. (I'm aware that under any reasonable definition, the dimension will be two, but I think it aids the reader to have a particular definition given, so they can verify it.) On the other hand, I think the phrase "in the limit $n\rightarrow \infty$" is confusing. The Hilbert curve is a particular curve, so there is no parameter to adjust, even if in one particular construction it is convenient to think of the curve as a limit of piecewise linear curves. I would have removed this phrase myself, if it wasn't already under discussion. Otherwise, a very nice article. 129.215.255.13 (talk) 20:34, 22 May 2009 (UTC)

There seems to be a consensus among everybody but me to keep the Hausdorff dimension comment. So I'll leave it alone; but I have removed the limit part of the sentence. Hanche (talk) 06:43, 26 May 2009 (UTC)

In fact, I agree with you. It seems to me that the Hausdorff dimension comment is not really relevant here; but if we want to keep it, then we have to make it clear whether we refer to the image or to the graph of H(t), otherwise it sounds mysterious or misleading (the Hausdorff measure and dimension are attached to a metric space, not to a function). I confirm that the 2-dimensional measure of the graph is still 1, as can be directly checked from the definition of Hausdorff measure. I've added a parenthesis, but I'm still not convinced of the relevance of it. --pma (talk) 16:53, 24 December 2009 (UTC)

Gray code

It looks like a z-order (curve) can be converted to a Hilbert curve by using a Gray code on the axes. Does that sound right? —Ben FrantzDale 13:04, 11 May 2007 (UTC)

Yup, sounds right. Not sure, though--try it! --Ihope127 20:52, 12 September 2007 (UTC)

I didn't say that clearly and now I forget what I meant... Part of the idea is that the Hilbert curve only has axis-aligned lines, corresponding to a Gray code having only one bit flip at a time. At the smallest scale, that flips the bottom of the "Z" of the z curve over to make a "]". Here's the beginning of it, I'll try to remember later. A simple way to assign 2D points a numerical order is to bitwise concatenate the x and y component so that the first bits correspond to the y axis and the rest to the x axis. For example:

     0    1    2    3
0 0000 0001 0010 0011      0   1   2   3
1 0100 0101 0110 0111      4   5   6   7 
2 1000 1001 1010 1011  =   8   9  10  11
3 1100 1101 1110 1111     12  13  14  15

The first two bits from the left correspond to the row; the second two bits correspond to the column. For a z-order curve, you interleave the bits, swapping bits 1 and 3 and leaving bits 0 and 2 giving you:

     0    1    2    3
0 0000 0001 0100 0101      0   1   4   5 
1 0010 0011 0110 0111      2   3   6   7
2 1000 1001 1100 1101  =   8   9  12  13
3 1010 1011 1110 1111     10  11  14  15

Now's where I forget what I meant, but the goal is to get from one of the above to the Hilbert curve:

     0    1    2    3
0 0000 0001 1110 1111      0   1  14  15
1 0011 0010 1101 1100      3   2  13  12
2 0100 0111 1000 1011  =   4   7   8  11
3 0101 0110 1001 1010      5   6   9  10

I'll try to remember what I meant. —Ben FrantzDale (talk) 12:10, 18 March 2008 (UTC)

I appeared to be mistaken. You can get an (x,y)->int mapping by taking the z-curve order and recursively applying the rules described in this page. That is, at each level you have a state (one of four shapes you are making). You take two bits of input, an x and y, and use the state to map that to a different number, 0–3. That number along with the state gives you a state at the next finest level. A quick-and-dirty implementation follows:

#include<iostream>
#include<bitset>
#include<cassert>
using namespace std;


enum shape {U, D, C, A};

const bitset<2> thisTwoBits(shape const& s, const bitset<2> xybits) {
  const unsigned char num = xybits.to_ulong();
  switch(s) {
  case U:
    switch(num) {
    case 0: return 0;
    case 1: return 3;
    case 2: return 1;
    case 3: return 2;
    }
  case D:
    switch(num) {
    case 0: return 0;
    case 1: return 1;
    case 2: return 3;
    case 3: return 2;
    }
  case C:
    switch(num) {
    case 0: return 2;
    case 1: return 3;
    case 2: return 1;
    case 3: return 0;
    }
  case A:
    switch(num) {
    case 0: return 2;
    case 1: return 1;
    case 2: return 3;
    case 3: return 0;
    }
  }
  assert(!"Should never get here!");
  return -1;
}


const
shape nextShape(shape const thisShape, bitset<2> const thisTwoBits) {
  if (thisTwoBits == 0) {
    return shape(static_cast<int>(thisShape) ^ 0x1); // U <-> D; C <-> A.
  }
  if (thisTwoBits == 1 || thisTwoBits == 2) 
    return thisShape;
  if (thisTwoBits == 3) {
    return shape((static_cast<int>(thisShape) + 2) % 4); // U <-> C, D <-> A.
  }
  assert(!"Should never get here!");
  return static_cast<shape>(-1);
}

unsigned int hilbert_order(short int const x, short int const y) {
  bitset<32> result;
  bitset<16> X(x), Y(y);

  shape Shape = U;
  for (size_t i = (8 * sizeof(x) - 1); i != size_t(-1); --i) {
    bitset<2> xybits; 
    xybits[0] = X[i];
    xybits[1] = Y[i];
    bitset<2> const bits = thisTwoBits(Shape, xybits);
    // Record those two bits
    result[2*i + 0] = bits[0];
    result[2*i + 1] = bits[1];
    Shape = nextShape(Shape, bits);
  }
  return result.to_ulong();
}


int main() {
  for (short int y = 0; y != 8; ++y) {
    for (short int x = 0; x != 8; ++x) {
	cout << hilbert_order(x, y) <<"  ";
    }
    cout << "\n";
  }
  return 0;
}

Below is my function that converts x, y to Hilbert order. It start with Z / Morton encoding and it ends with a Gray encoding, but the middle part works like this: If lead is not set in z, then it rotates the square by 90 degrees (swaps the x 's and y 's in the part of z below lead). If lead*2 is set and lead is unset, then it flips the square (complements the bits below lead). -- Nic Roets (talk) 13:08, 31 December 2010 (UTC)

unsigned hilbert_order (unsigned x, unsigned y)  
{ // Precondition: x < 0x10000 && y < 0x10000  
  x = (x & 0x000000ff) | ((x & 0x0000ff00) << 8);
  y = (y & 0x000000ff) | ((y & 0x0000ff00) << 8);
  x = (x & 0x000f000f) | ((x & 0x00f000f0) << 4);
  y = (y & 0x000f000f) | ((y & 0x00f000f0) << 4);
  x = (x & 0x03030303) | ((x & 0x0c0c0c0c) << 2);
  y = (y & 0x03030303) | ((y & 0x0c0c0c0c) << 2);
  x = (x & 0x11111111) | ((x & 0x22222222) << 1);
  y = (y & 0x11111111) | ((y & 0x22222222) << 1);
  int z = x + x + y, s = z ^ (x + y + y), lead;
  for (lead = 0x40000000; lead; lead >>= 2) {
    if (!(z & lead)) z ^= ((z & (lead << 1)) ? ~s : s) & (lead - 1);
  }
  return ((z & 0xaaaaaaaa) >> 1) ^ z;
}

Hilbert II curve?

Someone had added a link to Hilbert II curve under See Also. The article does not exist, and I certainly have no idea what it should cover. So I undid the edit. If the guy who did it does know, I think he should create the article first, then link to it. Does anyone else have an inkling as to what the Hilbert II curve might be? Hanche 17:59, 12 November 2007 (UTC)

Hilbert II is a similar curve that winds from one corner of a square to the opposite corner (as opposed to Hilbert I, which winds from one corner to an adjacent corner); Peitgens-Jürgens-Saupe (1992, pp. 390-1) also call it "S-shaped Peano Curve"; has L-system defns {X -> XFYFX+F+YFXFY-F-XFYFX, Y -> YFXFY-F-XFYFX+F+YFXFY}... Robertd (talk) 15:32, 10 May 2008 (UTC)

A sideways version of this, in fact: Robertd (talk) 15:39, 10 May 2008 (UTC)

Okay, then. This curve is in fact the original Peano curve, as described by Peano himself in 1890 (though his description is more complicated, being based on the manipulation of digits in the base 3 representation of numbers in [0,1]). Of course, the waters have been muddied somewhat by the Hilbert curve being called the Peano curve in the literature. I wonder, what is the basis for attaching Hilbert's name to the Peano, or “Hilbert II” curve? Hanche (talk) 08:56, 11 May 2008 (UTC)

Well, of course there is no basis. In fact, space filling curves are generally named "Peano curves". Notice that in his paper of 1890 on Math. Annalen, Peano also gives a short hint to make variations (including the successive Hilbert variant of his construction); but his aim was not to make a general theory, but rather, to exhibit a continuous curve filling the square, and describing it via digit expansion, rather than via geometrical constructions. The reason to avoid any appeal to visual intuition was not due to sadism towards the readers, but because the subject was a delicate matter about foundations of topology and geometry, in which the maximum rigour was needed. He choose the ternary option and not the binary because, indeed the digit description turns out to be simpler for odd basis. He made a picture of the curve in a tail tassellation in his bathroom, however. --pma (talk) 09:42, 23 December 2009 (UTC)

There isn't a strong consensus on how to display code in a language-agnostic way for Wikipedia. It's discussed here, but conclusions were generally down to preference. In academia, a standardized psuedocode like in Burrows-Wheeler Transform#Example often is used. As a reference, here is a pseudo code standard that explains how to make pseudo code in a very regimented way.Fletcher Porter (talk) 19:37, 23 February 2016 (UTC)

Informational

This might be trivial but informational. IPV4 Heatmap program uses Hilbert curve to map the Internet address space. --Oblivious (talk) 17:37, 17 March 2008 (UTC)

Oh, and that's actually based on xkcd's casual attempt. May be grounds for an "In Popular Culture". 65.96.201.130 (talk) 13:29, 18 October 2008 (UTC)

Is wikipedia a programming manual?

Regardless whether the article is about a mathematical object or about a computer programm I find the source code in ANY programming language not suitable for general reader encyclopedia. The average reader is neither a Java compiler, nor a Ruby interpretter, and ought to get the information in plain English. --91.92.29.19 (talk) 15:46, 25 May 2009 (UTC)

I tend to agree with this. Sample source code is fine in an article on a programming language, but is rarely (if ever) appropriate elsewhere. Hanche (talk) 06:48, 26 May 2009 (UTC)

Wikipedia is certainly not a programming manual. However, the inability of some of the readers to understand a simple computer program written in a general-purpose programming language obviously does not imply that wiping all the code from the article will make it better or easier to follow for an average reader. I am not a programmer by any means, but the code in this and connected articles (Sierpiński curve etc.) helped me a lot to understand how these curves are drawn.

If you really wanted to improve the article, why didn't you rewrite the part in plain English? For instance, it does not give any explanation at all on how to actually construct the curve. You can only learn this from the sample code or trying to interpret the psychedelic L-System definition. Therefore you could also have rewritten the drawing code in pseudo-code with exhaustive comments detailing what's currently being done here and there. Finally, you could have written a Simple English version of this article and linked it here. Instead you did neither of this, you just wiped all the code without considering how useful it is. This is what is called vandalism, I'm afraid.

Also for the sake of consistency you could have wiped the Sierpiński curve, Koch snowflake, Gosper curve and the other articles I didn't mention. Then could you have taken on some physics or chemistry articles wiping all the formulas, arguing that an average reader is not familiar with advanced maths...

I restored some of the code in the article and hopefully improved its structure. Any suggestions for improvements are welcome. --ZYV (talk) 13:19, 9 August 2009 (UTC)

I agree that the code examples are useful. OTOH, having more than one version and using esoteric languages (Tuga Turtle?) is distracting. I find Python-esque pseudocode to be the most clear... there's no point in using a language that's full of curly braces or "endif"s in an example. —Ben FrantzDale (talk) 16:49, 9 August 2009 (UTC)

Would you volunteer to rewrite this section? I kept the Tuga Turtle version because I find it easy to follow (walk, turn etc. are pretty natural) and the Java version because it can be directly useful (you can quickly translate it in any language you might need, like C / Pascal / whatever). I think that Python-like pseudo-code is a good idea, however it's nice to have something that you can instantly compile and trace instruction by instruction, so I'd say that keeping two versions (pseudo-code + Java) instead of four is the optimum for me. --ZYV (talk) 17:11, 9 August 2009 (UTC)

I've created and uploaded File:Hilbert1.gif and . The extra .gif was caused by the new upload wizard... I think. (talk) 22:36, 18 April 2011 (UTC)

I love to compare implementations of the same algorithm in different languages, as on RosettaCode, because it teaches you a lot. But I think this article needs far less implementations and quite more info about the curve, like its usage in databases and quantization, its locality properties, and so on. —Preceding unsigned comment added by 79.22.56.135 (talk) 09:10, 4 May 2011 (UTC)

I agree. 8 programs is far too many. I've just added a 9th one, but there's a reason for it. The 8 all drew a Hilbert curve on the screen. That's not very useful. In useful applications, you need to convert between an (x,y) coordinate pair and the distance d along the curve. And the conversion needs to go one way for some applications and the other way for other applications. I've added the algorithms for both directions, with a detailed explanation of how they work. It happens to be working code, but that's not the point. The point is to help the reader understand the two mapping algorithms and how they work. Especially in the more useful non-recursive form. If someone wants to delete some of the other 8 programs, that would be fine. But the article will be more useful if this new one is not deleted. — Preceding unsigned comment added by 109.171.137.224 (talk) 14:07, 11 June 2011 (UTC)

If anyone wants to move some implementations to Wikibooks, go ahead. I'll be bold and nuke it down to just Python, since that implementation is clearest. —Ben FrantzDale (talk) 23:07, 11 June 2011 (UTC)

Somebody replaced the python example with a buggy c example. I will try creating a simplified java example. 204.191.89.147 (talk) 08:32, 15 December 2012 (UTC)

OOps, it is actually not buggy. I have consequently lost interest in replacing it. Still, remember the purpose of wikipedia. Code repositories are for convenient algorithms. encyclopedias are for learning. That means no pointers, recursion where comprehension is enhanced (as is the case here). Simplified logic, (no true==1). And there is a wikibook for comparing different algorithms. 204.191.89.147 (talk) 08:59, 15 December 2012 (UTC)

It is buggy: xy2d(n, n-1, n-1) != n*n-1 134.191.220.76 (talk) 16:35, 22 June 2016 (UTC)

Hits every point or just close to every point?

I came to this article to satisfy my curiosity on a basic fact, but the article doesn't address this key question. Which is: Does the Hilbert curve hit every point in the unit square? Or does it merely come arbitrarily close to every point?

That would help the visualization and understanding immensely.

76.102.69.21 (talk) 23:29, 6 May 2012 (UTC) steve@your-mailbox.com

It hits every point, as it must by a compactness argument. The image of the curve is a compact subset of the unit square; in particular it is closed. So any point that is arbitrarily close to the curve is on the curve. And in fact, the second paragraph (the one mentioning the Hausdorff dimension) does say the image is the entire square. Hanche (talk) 13:20, 7 May 2012 (UTC)

But only for an infinite number of recursions. Otherwise you can never get any irrationals at all. And any one iteration will miss most of the rationals to boot. Remember the strange nature of infinity, you can never get there. 204.191.89.147 (talk) 09:17, 15 December 2012 (UTC)

The Hilbert curve IS the limit of those constructions, not any one of the discrete approximations. — Preceding unsigned comment added by 2003:69:CD0B:C001:2E81:58FF:FEFF:8F4B (talk) 09:00, 26 October 2013 (UTC)

Ikea

If you look at the floorplan of an Ikea store, they very often use a Hilbert curve as the route you have to follow to get from entrance to exit. The logic behind this is obvious from the space-filling nature of the curve...but leads me to remark to my wife that it also maximizes the distance you have to walk to find what you need. Anyway...if a reference could be found, thus would be a great addition to the Applications section of this page. SteveBaker (talk) 00:40, 13 August 2015 (UTC)

SteveBaker (talk) 00:40, 13 August 2015 (UTC)

recent image addition

I reverted the image added by Stfj, mainly because it didn't actually appear to be a Hilbert curve (or a step in the construction, of course). If there is some connection I'm not seeing, it should probably be explained in the caption – more than just a link to another article that doesn't seem relevant. If it does get re-added, it should also be along with the rest of the gallery, and not on its own on the right. –Deacon Vorbis (carbon • videos) 18:47, 7 February 2018 (UTC)

well done : it was a mistake but you saw it before i have time to make it disappear. --Stfj (talk) 18:59, 7 February 2018 (UTC)

Bottom/top-left convention

The introduction to the code sequence currently says:

"It assumes a square divided into n by n cells, for n a power of 2, with integer coordinates, with (0,0) in the lower left corner, (n − 1, n − 1) in the upper right corner, and a distance d that starts at 0 in the lower left corner and goes to {\displaystyle n^{2}-1} n^2-1 in the lower-right corner. This is different from the animation shown above where the curve starts from upper left corner and terminates at upper right corner."

I don't see anything in the code which defines whether it's using lower-left or top-left origin convention, and there are absolutely graphics APIs that use both - so I don't see why calling this out as "different from the animation" is necessary. Could we not just say something like:

"It assumes a square divided into n by n cells, for n a power of 2, with integer coordinates, and a distance d that starts at 0 at cell coordinate (0,0) and goes to {\displaystyle n^{2}-1} n^2-1 at cell coordinate (n - 1, 0)."

..? (Asking in case I'm missing something, rather than autocratically making an edit. Does Wikipedia have a house style for y direction?) Fluppeteer (talk) 11:49, 11 March 2019 (UTC)

Possibly useful but likely useless fact

The curve may be represented with emoji:

1:
⬆️⬆️
➡️⬅️

2:
⬆️⬆️⬆️⬆️
➡️⬅️➡️⬅️
⬇️➡️⬅️⬇️
⬆️➡️⬅️⬆️

3:
⬆️⬆️⬆️⬆️⬆️⬆️⬆️⬆️
➡️⬅️➡️⬅️➡️⬅️➡️⬅️
⬇️➡️⬅️⬇️⬇️➡️⬅️⬇️
⬆️➡️⬅️⬆️⬆️➡️⬅️⬆️
➡️⬅️⬇️➡️⬅️⬇️➡️⬅️
⬇️⬇️⬆️➡️⬅️⬆️⬇️⬇️
⬆️⬆️⬇️➡️⬅️⬇️⬆️⬆️
➡️⬅️⬆️➡️⬅️⬆️➡️⬅️

I made some code to write this for arbitrary sizes, and documented the creation process of the code here. This may be of some use for people writing about the curve here or elsewhere, although by itself it is not a Wikipedia-notable fact. Thiagovscoelho (talk) 02:39, 14 July 2023 (UTC)

Code

I think the example code in C should be replaced with more descriptive pseudocode, or at least something with comments and descriptive variable and function names. I might try to tackle that, but first I have to decode the C code. 🧐 Marcus erronius (talk) 22:50, 8 September 2023 (UTC)

I do see from above that this was a discussed topic, so I would be posting to talk to request dissenting opinions.Marcus erronius (talk) 23:01, 8 September 2023 (UTC)

While I agree that Wikipedia shouldn't be a programming manual, a task relevant to the subject of the Hilbert curve is converting from spatial dimensions to an index. The source code that was provided and, as of this writing, is no longer present, was useful and enlightening. I think pseudo-code for such a task would be optimal but, in lieu of that, source code in a common language, like C, JS or Python is adding more than it's detracting. Also, mathematical notation is freely used without being accused of being a "math textbook". Source code is, in some cases, a compact representation of an idea. Just as people can ignore the "mathmatiquese", so can they ignore source code that's not relevant to them. Abetusk (talk) 00:24, 6 February 2024 (UTC)

I agree that the code was valuable, I came here looking for the code because it was referenced as being the best approach in a 3rd party website. The value of the curve in many domains is as a reduction from a higher dimension, removing it removes practical value and meaning from the article. Cacoyi (talk) 03:27, 3 October 2024 (UTC)

Mismatched images

The animation on the right goes from top left to top right. Under "images", the diagrams of the first 3 orders go from top left to top right. Then (after production rules) there is a color-coded image going from top left to bottom left!

This is confusing. Someone looking for the end point on the top right will squint a long time before realizing the problem.

Interestingly, this image doesn't have any text on it, so it can be transposed very easily. Shall I go ahead and replace this image with a transposed version, to match the rest of the page, and in particular the other images right next to it? Remram44 (talk) 16:25, 31 May 2024 (UTC)

I have uploaded the transposed version as Hilbert-topleft-topright.png

If there are no objections, I will do the replacement soon. Note that this is the same situation for multiple languages. Remram44 (talk) 16:58, 5 June 2024 (UTC)