Talk:Hilbert curve
From Wikipedia, the free encyclopedia
 |
|||||
| Systems rating: | Start Class | Mid importance | Field: Chaos theory | ||
| Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article. | |||||
Contents |
[edit] 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)
[edit] 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:
- I'll try to remember what I meant. —Ben FrantzDale (talk) 12:10, 18 March 2008 (UTC)
#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; }
[edit] 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)
-
- 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)
[edit] 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)
